SOLUTION: 3. Prove that if n is odd, then gcd(3n; 3n + 2) = 1. What if n is even?

Algebra ->  Rational-functions -> SOLUTION: 3. Prove that if n is odd, then gcd(3n; 3n + 2) = 1. What if n is even?      Log On


   

Question 849358: 3. Prove that if n is odd, then gcd(3n; 3n + 2) = 1. What if n is even?
Answer by Edwin McCravy(20056) About Me  (Show Source):
You can put this solution on YOUR website!
3. Prove that if n is odd, then gcd(3n; 3n + 2) = 1
Let gcd(3n; 3n + 2) = d

Since n is odd, n=2p-1 for some positive integer p

3n = 3(2p-1) = 6p-3 = ad for some positive integer a 

3n+2 = 6p-3+2 = 6p-1 = bd for some positive integer b,  b > a

6p = ad+3 = bd+1

bd-ad = 2

d(b-a) = 2

d = 2/(b-a), so b-a is either 1 or 2 

b-a = 2,  since the common divisor of two odd numbers cannot be even.

Thus d = 2/2 = 1

-----------------------------

What if n is even?
Let gcd(3n; 3n + 2) = d

Since n is even, n=2a for some positive integer p

3n = 3(2p) = 6p = ad for some positive integer a 

3n+2 = 6p+2 = bd for some positive integer b,  b > a

6p = ad = bd-2

bd-ad = 2

d(b-a) = 2

d = 2/(b-a), so b-a is either 1 or 2 

b-a = 1,  since the common divisor of two even numbers must be even.

Thus d = 2/1 = 2

Edwin