# Showing $7n + 4$ and $5n + 3$ are coprime for all $n$

I am trying to show that $7n + 4$ and $5n + 3$ are coprime for all $n \in \mathbb Z$ but I'm stuck.

Please could someone tell me how to show this?

What I tried:

My first attempt was to use that two numbers are coprime iff their $\gcd$ is $1$. So assume that there are integers $k,q$ such that $1 = 7kn + 4k + 5qn + 3q$.

And this is where my first attempt ended as I did not see a way to proceed from there.

My second attempt was to use that if $b> a$ then $\gcd(a,b) = \gcd(b, b-a)$ so

$$\gcd (7n + 4, 5n + 3) = \gcd (5n + 3, 2n + 1)$$

but this idea also seems to lead nowhere as I don't see how to show that $\gcd (5n + 3, 2n + 1)=1$.

• You only started. Repeat the dose! $$(5n+3)-(2n+1)=3n+2,\ldots$$ Soon this may turn into full blown Euclid's algorithm :-) – Jyrki Lahtonen Aug 23 '15 at 6:47
• As Jyrki said. Also, \gcd gets the upright version. – user21820 Aug 23 '15 at 6:52

Using the fact that if $b>a$, then $\gcd(a,b) = \gcd(b, b-a)$, we have:
$\gcd (7n + 4, 5n + 3) = \gcd (5n + 3, 2n + 1)=\gcd (2n+1, 3n+2) = \gcd (3n+2, n+1)=\gcd (n+1, 2n+1) = \gcd (2n+1, n)= \gcd(n,n+1) = \gcd(n+1,1)$
A quick way is to eliminate $n$, noting that $7(5n+3)-5(7n+4)=1$.
Let $d$ be the $\gcd$. Then, $d|(5n+3-2n-1)=(3n+2), d|(3n+2-2n-1)=(n+1),d|(2n+1-2(n+1))=-1$ and so $d=1$.
You can find $a,b$ such that: $a(7n+4) + b(5n+3) = 1\to 7a+5b=0, 4a+3b=1\to -21a-15b=0, 20a+15b=5\to a = -5, b = 7$. This means $\gcd(7n+4,5n+3) = 1$.