SOLUTION: Show that 5n+3 and 7n+ 4 are relatively prime for all n

Question 4726: Show that 5n+3 and 7n+ 4 are relatively prime for all n
Answer by khwang(438) (Show Source): You can put this solution on YOUR website!
Use the fact about gcd:
d=(a,b) if and only if there exist integer p, q such that
pa + qb = d.
Hence, (a,b) = 1 if and only if there exist integer p, q such that
pa + qb = 1.
Now, 3(5n+3)-2(7n+ 4) = 15n + 9 -14n- 8 = 1
So, (5n+3, 7n+ 4) = 1 ie (5n+3 ) and (7n+ 4) are relative prime for all n.
Another way of proof:
if d =(5n+3, 7n+4), consider 7(5n+3)-5(7n+4) = 1,
since d is a divisor of 7(5n+3)-5(7n+4),
d must be 1 and so (5n+3 ) and (7n+ 4)are relative prime.
Kenny
RELATED QUESTIONS
Show 5n+3 and 7n+4 are relatively prime for all... (answered by richard1234,Edwin McCravy,robertb)

Show that 83,154,367 and 4 are relatively... (answered by ikleyn)

Show that 165,342,985 and 13 are relatively... (answered by vleith)

how to show that a is relatively prime to... (answered by KMST)

Let a and b be relatively prime intergers and let k be any integer. Show that b and a+bk... (answered by richard1234)

Add the polynomial -5n(n to the second power)+7n-9 and -5n-4 (answered by stanbon)

Two positive integers M and N are defined to be relatively prime if GCF(M, N) = 1.... (answered by consc198,math_iz_hard)

Hi. I'm teaching myself Algebra for the GRE because I somehow missed all the math in... (answered by ewatrrr)

Let a not equal 0, b and c be integers with a and b relatively prime. Show that if a|b*c (answered by venugopalramana)