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