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,

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search