-1
$\begingroup$

Let a be a nonzero integer, $m>n>0, m,n\in \mathbb{Z}$.

(1)Prove that $\gcd(a^{2^m}+1, a^{2^n}+1)$ is either $1$ or $2$.

(2)Use this fact to prove that there are infinite number of primes.

My attempt on (1): the problem can be splitted into two cases.

If $a$ is an even number, then we only need to prove $\gcd(a^{2^m}+1,a^{2^n}+1)$ equals $1$ since odd numbers cannot have $2$ as divisor.

If $a$ is an odd number, then we only need to prove $\gcd(a^{2^m}+1, a^{2^n}+1)$ equals $2$ since $a^{2^m}+1$ and $a^{2^n}+1$ are both even.

Any hints would be appreciated!

$\endgroup$

marked as duplicate by Robert Z, lulu, Vinyl_cape_jawa, Bill Dubuque elementary-number-theory Feb 25 at 16:08

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.

0
$\begingroup$

If $m > n$ then $a^{2^n} +1$ divides $a^{2^m} - 1.$ Because

$$(a^{2^n} + 1) \cdot (a^{2^n} -1) = (a^{2^{n+1}} - 1)$$ and So $a^{2^n} +1 \mid a^{2^{n+1}} - 1$ and since $m > n$ by similar reasoning we should also have $a^{2^{n+1}} - 1 \mid a^{2^m} - 1.$ So for $m > n$ we have $a^{2^n} +1 \mid a^{2^m} - 1,$ as claimed.

Also note that if $c \mid a$ then $\text {gcd} (a+b,c) = \text {gcd}(b,c).$

Therefore we have $$\begin{align} \text {gcd} (a^{2^m} + 1 , a^{2^n} + 1) & = \text {gcd} ((a^{2^m} - 1)+2 , a^{2^n} + 1). \\ & = \text {gcd} (2 , a^{2^n} + 1). \\ & = 1\ \text {or}\ 2. \end{align}$$

QED

$\endgroup$

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