Consider the number $N= 2^{2^{k}}-1$ for $k\geq 1$. Then is it true that for all $k \in \mathbb{N}$, $N$ has exactly one prime divisor which is $3 \pmod{4}$ and that being $3$.

Some examples which I considered:

  • For $k=1$, we have $N=3$.

  • For $k=2$, we have $N=15 = 3 \times 5$.

  • For $k=3$ we have $N=255 = 3 \times 5 \times 17$.

  • For $k=4$, we have $N=2^{16}-1 = 3 \times 5 \times 17 \times 257$.

  • For $k=5$ we have $N=2^{32}-1 = 3 \times 5 \times 17 \times 257 \times 65537$

Note that all primes appearing in the factorization of $N$ except $3$ are primes which are congruent to $1 \pmod{4}$.


Use mathematical induction. Note that from Fermat's theorem on the sum of two squares, we have that numbers of the form $x^2+1$ has only prime factors that are of the form $1 \pmod 4 $.

Now, you have already proved the base cases. Assume that it is true for $k-1$. $$2^{2^{k}}-1=(2^{2^{k-1}}-1)(2^{2^{k-1}}+1)$$$2^{2^{k-1}}+1$ has no prime factors that are $3 \pmod 4$ following from the aforementioned theorem, and $2^{2^{k-1}}-1$ has only one prime factor that is $3 \pmod 4$ via inductive argument. We are done.

  • $\begingroup$ Ahh. This was easy. I missed the trick. Thanks :) $\endgroup$ – crskhr May 10 '16 at 11:17

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.