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$.

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.