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

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) (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

RELATED QUESTIONS
given d|n+1 and d|n^2+1 and d|2 prove that if n is odd then gcd(n+1,n^2+1) =... (answered by ikleyn)

Help with a proof, please. Here is the example and solution: Q: Show that if n is an... (answered by richard1234)

proof by contradiction if 3n+1 is odd then n is also... (answered by fcabanski)

If n represents an odd number, which of these is an even number? a)4n + 1 b) (answered by checkley77)

If 3(m+n) is even, then which of the following is also even? a. m+n b. m c. n d.... (answered by reviewermath)

How to prove that all integers n, if n^3+5 is odd then n is... (answered by greenestamps)

Prove: The probability that two diagonals in a convex polygon with n sides will... (answered by robertb)

If g(n) = 3n - 2, then what is the value of... (answered by MathLover1)

Prove: if 4 divides mn, then m is even or n is even. i saw that this was p implies q... (answered by richard1234)