# 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

## 3 Answers

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 Naslund 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 Naslund 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 Naslund 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 Naslund 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 Naslund 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.

-
Someone is downvoting all the answers on this thread. +1. This is a more generally applicable answer. –  Aryabhata Feb 28 '11 at 5:18
At this point, I think you under evaluate a very important part of mathematics. That is the ability to communicate it to other people. Every answer you down voted was one where I was much clearer to someone wanting to understand the basics. Each answer you write isn't even written in English nicely, is unclear, and not at the level the OP wanted. Having said that, do I think they are bad answers that deserve to be down voted? No, that I reserve for actual things that do not contribute at all mathematically. –  Eric Naslund Feb 28 '11 at 16:20
At the very least, if you do not like my answers, and think they need to be pushed in a certain direction, please comment and tell me. Whenever you down vote a message box comes up asking you to do so. It is impossible for me understand your reasoning when you do not tell me. I do not see at all what was wrong with most of these answers, and I honestly have no problem with downvotes that are explained, because then whatever problem there is can be improved. As is it resembles that you just do not like the fact that mine are accepted over yours, which is childish. –  Eric Naslund Feb 28 '11 at 16:28