GCD Even/Odd Proof

Date: 10/26/2001 at 04:37:33
From: paras
Subject: Perfect square

Hello Dr. Maths,

Please help me in solving the following question:

If m > n and a,m,n are positive, with m not equal to n, prove that the 
greatest common denominator of (a^2^m+1, a^2^n+1) = 1 if a is even,
and 2 if a is odd.

Thanks for the help.

Date: 10/26/2001 at 14:31:12
From: Doctor Rob
Subject: Re: Perfect square

Thanks for writing to Ask Dr. Math, Paras.

Suppose that d > 0 divides both a^(2^m) + 1 and a^(2^n) + 1.
Then GCD(d,a) = 1.  Then d divides their difference,

   d | a^(2^m) + 1 - [a^(2^n) + 1],
   d | a^(2^n)*[a^(2^m-2^n) - 1],

because m > n, so 2^m > 2^n.  Since GCD(d,a) = 1,

   d | a^(2^m-2^n) - 1.

But since d divides a^(2^n) + 1,

   d | a^(2^[n+1]) - 1.

That implies that

   d | GCD[a^(2^m-2^n) - 1, a^(2^[n+1]) - 1].

Then it is fairly easy to see that this implies

   d | a^GCD[2^m-2^n, 2^(n+1)] - 1.

Now

   GCD[2^m-2^n, 2^(n+1)] = 2^n,

because m > n, and so 2^(m-n) - 1 is odd.  Thus

   d | [a^(2^n) + 1] - [a^(2^n) - 1] = 2.

Thus d = 1 or 2.

I think you can fill in the details and reasons, and finish from
here.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/