Does $9^{2^n} + 1$ always have a prime factor larger than $40$?

Solution 1:

Here is a proof with very few computations involved.

It is well known that

If $\displaystyle x^2 + 1 = 0 (\mod p)$ for some prime $\displaystyle p$, then $\displaystyle p = 1 (\mod 4)$.

Perhaps a little less well known than the above is that

If $\displaystyle x^4 + 1 = 0 (\mod p)$ for some prime $\displaystyle p$, then $\displaystyle p = 1 (\mod 8)$.

Since $\displaystyle 9^{2^n}+1 = (3^{2^{n-1}})^4 + 1$ we must have that the only possible prime < 40 which is a candidate is $\displaystyle 17$.

Thus we need to check the residues only for $\displaystyle 17$.

Now since $\displaystyle 3$ is a primitive root of $\displaystyle 17$, we have that $\displaystyle 3^{8} + 1 = 0 (\mod 17)$. Since $\displaystyle 3^{2^3} = -1 ( \mod 17)$, we have that $\displaystyle 3^{2^n} + 1 = 2 (\mod 17)$ for all $\displaystyle n > 3$.

Thus we only need to check $\displaystyle 3^{2^3} +1 = 9^{2^2} + 1 = 2×17×193$, which has a factor $\displaystyle > 40$ and we are done.

Interestingly, for any number $N$, we can show that at most a finite number of numbers of the form $\displaystyle 9^{2^n}+1$ have all their prime factors < $\displaystyle N$.

This is because for $\displaystyle m$ < $\displaystyle n$, $\displaystyle 9^{2^m}-1$ divides $\displaystyle 9^{2^n}-1$ which implies that $\displaystyle (9^{2^n} + 1, 9^{2^m} + 1) = 2$.

i.e. any two numbers in the sequence have a gcd of $\displaystyle 2$.

Thus the number of numbers with all prime factors < $\displaystyle N$ is finite.

(Another proof of the same fact is that if $\displaystyle 9^{2^m}+1 = 0 (\mod p)$ then $\displaystyle 9^{2^n}+1 = 2 (\mod p)$ for $n > m$)

In fact, this is a different proof that the number of primes is infinite!

Solution 2:

Let $\displaystyle a_n:=9^{2^n}+1$; reducing $\displaystyle a_n$ modulo the primes in the interval $\displaystyle [2,40]$, it is easy to find that the only times we get zero is when either the prime is 2 and $\displaystyle n$ is arbitrary, or when the prime is 17 and $\displaystyle n$ is 2. Thus, for $\displaystyle n>2$, the number $\displaystyle a_n$ has prime factors larger than 2 (and hence larger than 40) provided it is not a power of 2 itself. Since $\displaystyle a_n \equiv 2 \pmod{4}$, we see that $\displaystyle a_n$ is never a power of two. Finally, $\displaystyle a_1=82=2 \cdot 41$ and $\displaystyle a_2=6562=2 \cdot 17 \cdot 193$, and we conclude that $\displaystyle a_n$ has a prime factor larger than 40 for $\displaystyle n \geq 1$.