# Prove that two distinct number of the form $a^{2^{n}} + 1$ and $a^{2^{m}} + 1$ are relatively prime if $a$ is even and have $gcd=2$ if $a$ is odd

Prove that two distinct number of the form $a^{2^{n}} + 1$ and $a^{2^{m}} + 1$ are relatively prime if a is even and have $gcd=2$ if a is odd

My attempt:
If $a$ is even, let $a = 2^{s}k$ for some integers $k, s$
Then, $$a^{2^{n}} + 1 = 2^{2^{n}s}\times k^{2^n} + 1$$ and $$a^{2^{m}} + 1 = 2^{2^{m}s}\times k^{2^m} + 1$$ To prove that they're relatively prime, we need to show that their gcd = 1. And I was stuck here, how could I prove that gcd of two numbers is $1$?

A hint would be sufficient. Thanks.

-
 You don't need to sign your posts; your name/signature is automatically added to the post. – Arturo Magidin Feb 28 '11 at 2:57 @Arturo Magidin: Thanks, I will next time. – Chan Feb 28 '11 at 2:59

Hint:

Consider the following proof when $a=2$: http://planetmath.org/encyclopedia/FermatNumbersAreCoprime.html

Try adapting it to work for all $a$.

Hint 2: Factor $a^{2^n}-1$.

-
@Eric Naslund: Thank you. – Chan Feb 28 '11 at 3:03
I don't get it. Why voted down? – Eric Feb 28 '11 at 3:08
+1: No idea why one would downvote this. – Aryabhata Feb 28 '11 at 3:09
@Moron: Funny, someone didn't like either answer! – Eric Feb 28 '11 at 3:13
@Chan: Ok, so we need to do a little more, you are correct. It suffices to consider $$a^{2^n}+1$$ modulo $4$. Since $$a^{2^n}$$ is a square, it is congruent to 0 or 1, and hence is congruent to 1 when $a$ is odd. Then we see $$a^{2^n}+1\equiv 1\pmod{4}$$ so that each term is divisible by 2 but not 4. That is where the $2$ in the $\gcd$ comes from. Use the previous method to show that other primes cannot divide it. – Eric Mar 1 '11 at 6:17

If $x = -1 \mod p$, then $x^{2^n} = 1 \mod p$.

Assume $n \gt m$. So if $p$ divides $x + 1 = a^{2^m} + 1$, then, $a^{2^n} + 1 = x^{2^{n-m}} + 1 = 1 + 1 = 2 \mod p$.

-
 I don't see what this tells us. What am I missing? – Eric♦ Feb 28 '11 at 3:05 @Eric: I have edited the answer. – Aryabhata Feb 28 '11 at 3:08 @Moron: Thanks, that makes it clear. +1 for the edit. – Eric♦ Feb 28 '11 at 3:12 @Moron: What's $p$ in your hint? I tried understand your hint, but I felt lost :(. Thanks. – Chan Feb 28 '11 at 23:40 @Chan: $p$ is any prime which divides $x+1$. Basically we are showing that if $p$ divides $a^{2^m} + 1$, then $p$ cannot possibly also divide $a^{2^n} + 1$, unless $p=2$. – Aryabhata Mar 1 '11 at 0:09
HINT $\rm\ \: (A+1,\ A^{2\:K}+1)\ =\ (A+1,\ (-1)^{2\:K}+1)\ =\ (A+1,\:2\:)\:.\:$ Put $\rm\ A = a^{2^{N}}\$ (wlog $\rm\ N < M\:)\:.$
$\$ using $\rm\ \ (A+I,\ \ F(A)\ )\ \ \ =\ \ \: (A+I,\ \ F(-I)\ )\ \$ for all polynomials $\rm\ F(X)\in \mathbb Z[X],\ \ A,\:I\in \mathbb Z$
$\ \ \$ i.e. $\rm\ \ \ \ \ A\ \equiv\: -I\ \ \ \Rightarrow\ \ \ F(A)\ \equiv\ F(-I)\ \ \ \ (mod\ D)\:,\$ if $\rm\ D\ |\ A+I$
$\ \ \$ i.e. $\rm\ \ \ (B,\ C)\ =\ (B,\ C\ mod\ B)\ \$ -- $\:$ the modular property of GCDs.