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

Algebra.Com
Question 408264: Show 5n+3 and 7n+4 are relatively prime for all n
Found 3 solutions by richard1234, Edwin McCravy, robertb:
Answer by richard1234(7193)   (Show Source): You can put this solution on YOUR website!
Suppose that there exists some k such that 5n + 3 ≡ 7n + 4 ≡ 0 (mod k). If this is the case, then the difference between 7n + 4 and 5n + 3 must also be 0 mod k, i.e.

2n + 1 ≡ 5n + 3 (mod k), in addition (5n + 3) - (2n + 1) ≡ 0, so

3n + 2 ≡ 0 (mod k)

6n + 4 ≡ 0 (mod k)

This implies 6n + 4 ≡ 7n + 4 ≡ 0 (mod k) so n ≡ 0 (mod k). However, if n ≡ 0 (mod k), then 5n + 3 ≡ 3 (mod k) and 7n + 4 ≡ 4 (mod k) so this implies that 3 ≡ 4 (mod k), contradiction (unless k = 1). Hence, 5n + 3 and 7n + 4 are relatively prime (for all integers n).

I kinda feel like there's a shorter way to prove this...care to find another solution?



Answer by Edwin McCravy(20062)   (Show Source): You can put this solution on YOUR website!

You could use Euclid's algorithm:

Euclid's algorithm for gcd states if a and b are positive 
integers and all qi and ri are non-negative integers then if

 a = q0b + r0 
 b = q1r0 + r1 
r0 = q2r1 + r2 
r1 = q3r2 + r3
...
rk-3 = qk-1rk-2 + rk-1
rk-2 = qkrk-1 + rk

where if rk = 0 then gcd(a,b) = rk-1.

7n+4 = 1(5n+3) + (2n+1)
5n+3 = 2(2n+1) + (n+1)
2n+1 = 1(n+1) + 1
 n+1 = 1(n+1) + 0

So gcd(7n+4,5n+3) = 1

Edwin
Answer by robertb(5830)   (Show Source): You can put this solution on YOUR website!
As a corollary to Euclid's algorithm, there are integers s and t such that as + bt = gcd(a,b). Hence if we're able to find integers s,t, such that
s(5n + 3) + t(7n + 4) = 1,
then we've shown that 5n + 3, 7n + 4 are relatively prime for all n.
==> (5s + 7t)n + (3s + 4t) = 1.
It's enough to see if the system
5s + 7t = 0
3s + 4t = 1
has integer solutions.
Indeed, the solutions are s = 7, and t = -5.
Therefore 5n + 3, 7n + 4 are relatively prime for all n.
RELATED QUESTIONS

Show that 5n+3 and 7n+ 4 are relatively prime for all... (answered by khwang)
Show that 83,154,367 and 4 are relatively... (answered by ikleyn)
Show that 165,342,985 and 13 are relatively... (answered by vleith)
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)
how to show that a is relatively prime to... (answered by KMST)
3-8(7-5n) 35n-1+46 -2(7-n)+4... (answered by lynnlo)
Let a and b be relatively prime intergers and let k be any integer. Show that b and a+bk... (answered by richard1234)
7n+4>5n-8 (answered by jim_thompson5910)