2007 USAMO Problems/Problem 5

Problem

Prove that for every nonnegative integer $n$ , the number $7^{7^n}+1$ is the product of at least $\displaystyle 2n+3$ (not necessarily distinct) primes.

We proceed by induction.

Let ${a_{n}}$ be $7^{7^{n}}+1$ . The result holds for ${n=0}$ because ${a_0 = 2^3}$ is the product of $3$ primes.

Now we assume the result holds for ${n}$ . Note that ${a_{n}}$ satisfies the recursion

${a_{n+1}= (a_{n}-1)^{7}+1} = a_{n}\left(a_{n}^{6}-7(a_{n}-1)(a_{n}^{2}-a_{n}+1)^{2}\right)$ .

Since ${a_n - 1}$ is an odd power of ${7}$ , ${7(a_n-1)}$ is a perfect square. Therefore ${a_{n}^{6}-7(a_{n}-1)(a_{n}^{2}-a_{n}+1)^{2}}$ is a difference of squares and thus composite, i.e. it is divisible by ${2}$ primes. By assumption, ${a_n}$ is divisible by ${2n + 3}$ primes. Thus ${a_{n+1}}$ is divisible by ${2+ (2n + 3) = 2(n+1) + 3}$ primes as desired.

Let $x=7^{7^{k}}$ . The expression becomes

$\frac{7^{7^{k+1}}+1}{7^{7^{k}}+1} = \frac{x^7 + 1}{x + 1}$

Since $x$ is an odd power of $7$ , $7x$ is a perfect square, and so we can factor this by difference of squares. Therefore, it is composite.

2007 USAMO (Problems • Resources: AoPS \| ML)
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6