Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/