2
$\begingroup$

I am working on the following exercsie:

If $p$ divides $2^{2^n}+1$, then $p \equiv 1 \pmod {2^{n+1}}$. Conclude that for all $n \ge 2$ exist infinitely many primes $p \equiv 1 \pmod {2^n}$.

I have shown that $p \equiv 1 \pmod {2^{n+1}}$. But I do not get how I should show that ther are "infinitely many primes $p \equiv 1 \pmod {2^n}$". Could you help me?

$\endgroup$
1
  • 6
    $\begingroup$ Hint: show that distinct Fermat numbers are relatively prime. $\endgroup$
    – lulu
    Oct 22 '19 at 0:28
3
$\begingroup$

Taking lulu's advice, you can merely show the Fermat numbers (numbers of the form $2^{2^n}+1$) are mutually coprime.

Let $n\neq m$. Without loss of generality, we can assume $n>m$. We wish to show $\gcd(2^{2^n}+1, 2^{2^m}+1)=1$. Notice that by factoring with difference of squares, we have

$$2^{2^n}-1=(2^{2^0}-1)(2^{2^0}+1)(2^{2^1}+1)(2^{2^2}+1)\ldots(2^{2^{n-1}}+1)$$

and thus, $2^{2^m}+1|2^{2^n}-1$. In particular, we have $\gcd(2^{2^n}+1, 2^{2^m}+1)\leq \gcd(2^{2^n}+1, 2^{2^n}-1)=\gcd(2^{2^n}-1, 2)=1$, so Fermat numbers are coprime.

Given that they are coprime, if $p_n$ is a prime divisor of $2^{2^n}+1$ for each $n$, then all these primes must be distinct. Therefore, the sequence ${p_n}$ must contain infinitely many primes. By your observation, $p_n \equiv 1 \mod 2^{n+1}$, and so in particular, $p_n \equiv 1 \mod 2^k$ for all $k$, $1\leq k \leq n+1$. The claim follows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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