# Only one prime factor of $2^{2^{k}}-1$ of the form $3\pmod{4}$

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

## 1 Answer

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.

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