Show that $5n+3$ and $7n+4$ are relatively prime for all $n$. Show that $5n+3$ and $7n+4$ are relatively prime for all $n$.
 A: If $p$ is a prime divisor of $5n+3$ and $7n+4$ then $$5n+3 \equiv 0 \pmod p$$ and $$7n+4 \equiv 0 \pmod p.$$  At least one of these is not satisfied when $p \in \{5,7\}$.  Otherwise, $7$ and $5$ are invertible modulo $p$ and we can rearrange these equations as $$\frac{-4}{7} \equiv n \equiv \frac{-3}{5} \pmod p.$$  This implies $-20 \equiv -21 \pmod p$, giving a contradiction, since $p \geq 2$.
A: Since $7(5n+3) - 5(7n+4)=1$ the greatest common divisor is $5n+3$ and $7n+4$ is $1$ (by Bezout's identity). 
A: Bezout's Lemma states that for if and only if $a$ and $b$ are comprime numbers then the following equation has integer solutions:
$$ax + by = 1$$
Now let $a=5n+3$ and $b=7n+4$. Now we get:
$$(5n+3)x + (7n+4)y = 1$$
Now apply the extended Euclidean Algorithm:
$$(7n+4) = (5n+3) + (2n+1)$$
$$(5n+3) = 2\times(2n+1) + (n+1)$$
$$(2n+1) = (n+1) + n$$
$$(n+1) = n + 1$$
We now just go back:
$$1 = (n+1) - n$$
$$1 = (n+1) - ((2n+1) - (n+1))$$
$$1 = 2(n+1) - (2n+1)$$
$$1 = 2((5n+3) - 2(2n+1)) - (2n+1)$$
$$1 = 2(5n+3) - 5(2n+1)$$
$$1 = 2(5n+3) - 5((7n+4) - (5n+3)$$
$$1 = 7(5n+3) - 5(7n+4)$$
We just obtained one solution $(x,y) = (7,5)$, but it's enough to prove that $7n+4$ and $5n+3$ are comprime numbers.
A: Hint: 
$$7n+4=(5n+3)+2n+1$$
$$5n+3=2(2n+1)+1$$
A: Hint:  $\gcd(5n+3,7n+4)=\gcd(35n+21,35n+20)$, why? 
Once you can verify my question, all that remains is to show that consecutive integers are coprime.
