Take the 2-minute tour ×
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|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.

4  
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
2  
I don't know why this question was downvoted. It's a valid, genuine question. –  ajay Sep 7 '13 at 17:04
2  
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|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|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|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|improve this answer

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

share|improve this answer

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