Prove that for any integer n gcd3n 2 4n 5 is either 1 or 7

Prove that for any integer n, gcd(3n + 2, 4n + 5) is either 1 or 7.

Solution

Apply the rule gcd(a,b) = gcd(b, a-b) repeatedly.

or do this by

By Euclid theorem
a(3n+2) + b(4n+5)= gcd
(3a + 4b)n + 2a+5b = gcd
so 3a+4b (coefficient of \"n\") must be zero
=> 3a+4b=0
=> 3a = -4b
=> a/b = -4/3
so a=-4 & b=3

0 + 2a+5b = gcd
2*(-4) + 5*(3) = gcd
7=gcd

so One and only possible gcd is 7 (obviously except 1)