# Show that $5n+3$ and $7n+4$ are relatively prime for all $n$. [closed]

Show that $5n+3$ and $7n+4$ are relatively prime for all $n$.

-

## closed as off-topic by YACP, T. Bongers, dfeuer, Thomas Andrews, Danny Cheuk Sep 16 '13 at 4:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Homework questions must seek to understand the concepts being taught, not just demand a solution. For help writing a good homework question, see: How to ask a homework question?." – Community, Community, dfeuer, Thomas Andrews, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

Do you know how to use the Euclidean algorithm? All of your previous questions are variants on it. You should learn how to use this basic technique. – Calvin Lin Sep 7 '13 at 16:53
I don't know why this question was downvoted. It's a valid, genuine question. – ajay Sep 7 '13 at 17:04
Calculate $(5n+3,7n+4)=(5n+3,2n+1)=(n+1,2n+1)=(n+1,1)=1$ via iterating the relations $(a,b)=(a,b-ma)=(a-mb,b)$ to reduce the coefficient of $n$ each step. Here $(a,b)$ stands for gcd. This is the Euclidean algorithm. – anon Sep 7 '13 at 17:12

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.

-
This is very thorough and understandable. Thank you very much! – SamHaim Sep 7 '13 at 17:09
Did you really mean $7n+4+5n+3$ at the end? I think you mean the middle $+$ to be an '&' character, or just write "and." – Thomas Andrews Sep 7 '13 at 21:25

Hint: $\gcd(5n+3,7n+4)=\gcd(35n+21,35n+20)$, why?

-
Great Rustyn (+1) – Mahdi Khosravi Sep 7 '13 at 17:02

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

-

Since $7(5n+3) - 5(7n+4)=1$ the greatest common divisor is $5n+3$ and $7n+4$ is $1$ (by Bezout's identity).

-

Hint: $$7n+4=(5n+3)+2n+1$$ $$5n+3=2(2n+1)+1$$

-