8
$\begingroup$

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.

  • 0
    Another minor point: $\gcd(m, n)$ by typing `$\gcd(m, n)$`2015-04-22

3 Answers 3

8

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

  • 0
    @EricNaslund,@Chan: What about the case of$a$is even?2013-06-29
7

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

  • 0
    @Moron: Thank you. I will think mor$e$ about it.2011-03-01
1

Hint $\ \ \ (A\!+\!1, A^{2K}\!\!+1)\,=\, (A\!+\!1,\ (-1)^{2K}\!+1)\, =\, (A\!+\!1,2).\ $ Put $\ A = a^{\large 2^{\Large N}}\!$ (wlog $\ N < M)$

using $\,\ \ (A\!-\!n,\ \ F(A)\ )\, = \, (A\!-\!n,\ \ F(n) )\ $ for all polynomials $\ F(X)\in \mathbb Z[X],\ A,n\in \mathbb Z$

by $\!\bmod A\!-\!n\!:\ A\equiv n\,\Rightarrow\, F(A)\equiv F(n)\ $ by the Polynomial Congruence Rule, and

also by $\ (B,\ C)\ =\ (B,\ C \bmod B),\, $ modular property of GCD (used in Euclidean algorithm)

Remark $ $ For the general case $\ (a^m+1,a^n+1)\ $ see this answer.

  • 4
    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.2011-02-28