This question already has an answer here:

Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd.

I solve the problem in the following way: I assume that $m>n$ then $$a^{2^m}+1=a^{2^m}-1+2$$ With this expression if I take a divisor prime $p$ of $a^{2^n}+1$ then if $p|a^{2^m}+1$ this prime must divide 2 and the result follows.

But, how can I prove this statement without use of primes? This exercise appears before the concept of prime is introduced then I prefer do not use it.

Any idea?



marked as duplicate by lab bhattacharjee elementary-number-theory Aug 27 '15 at 16:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ There's an $m \neq n$ constraint missing. $\endgroup$ – Daniel Fischer Aug 27 '15 at 14:09
  • $\begingroup$ If $m≠n$ then it is true. Do you have any idea about Fermat numbers? $\endgroup$ – tatan Aug 27 '15 at 14:11

If we have $n < m$, then

$$(a^{2^n} + 1)\cdot (a^{2^n} - 1) = a^{2^{n+1}} - 1$$

shows $(a^{2^n}+1) \mid (a^{2^{n+1}}-1)$. Then

$$(a^{2^k}-1)\cdot(a^{2^k}+1) = a^{2^{k+1}}-1$$

shows $(a^{2^{n+1}}-1) \mid (a^{2^m}-1)$, and thus

$$\gcd(a^{2^m}+1, a^{2^n}+1) = \gcd((a^{2^m}-1)+2,a^{2^n}+1) = \gcd(2, a^{2^n}+1).$$

  • $\begingroup$ Jmmm... If $a|c$ then $gcd(a+b,c)=gcd(b,c)$? Thanks! $\endgroup$ – YTS Aug 27 '15 at 14:23
  • 1
    $\begingroup$ If $c\mid a$, not if $a\mid c$. If we write $a = k\cdot c$, it becomes $\gcd(a+b,c) = \gcd(a+b-kc,c) = \gcd(b,c)$. $\endgroup$ – Daniel Fischer Aug 27 '15 at 14:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.