Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to find out for which natural numbers $n$, does $9^n + 1$ have all of its prime factors less than $40$. If I can provide a positive answer to my title question, then I will have a proof that only $n = 1$ causes $9^n + 1$ to have all of its prime factors less than $40$. Thank you for any help.

share|cite|improve this question

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!

share|cite|improve this answer
Neat! Btw, your post gives the impression that 37 is congruent to 1 modulo 8. ;) – damiano Aug 25 '10 at 1:23
@damiano: Right! I have edited to remove 37 and added the complete proof. – Aryabhata Aug 25 '10 at 1:41
Very nice! I already gave you my vote, though... – damiano Aug 25 '10 at 1:46
@damiano: Yeah, I guessed :-) – Aryabhata Aug 25 '10 at 1:54
Very nice. But how do you know $3$ is a primitive root without doing the computation? – Eric Naslund Mar 16 '12 at 12:12

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.