Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|cite|improve this question

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

5 Answers 5

up vote 4 down vote accepted

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.

share|cite|improve this answer
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?

share|cite|improve this answer
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$.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.