Problem 57: Prime factorization

Posts: 312
Joined: Mar 10, 2015

by henderson, Jan 4, 2017, 2:32 PM

${\color{red}\bf{Problem \ 57}}$ Prove that for every nonnegative integer $n,$ the number $7^{7^{n}}+1$ is the product of at least $2n+3$ (not necessarily distinct) primes.
(USAMO 2007)
${\color{red}\bf{Solution}}$ Let's apply induction.

$\boxed{\color{blue}{1}}$ The base case is $n=0,$ which is $8=2^3,$ so it has $2n+3$ prime factors.

$\boxed{\color{blue}{2}}$ Now, assume that $7^{7^{n}}+1$ is the product of $2n+3$ primes.

$\boxed{\color{blue}{3}}$ We wish to prove that $7^{7^{n+1}}+1$ is the product of $2(n+1)+3=2n+5$ primes.
Let $x = 7^{7^{n}}.$ $\quad$ $x+1$ is the product of $2n+3$ primes, so we want to show that $x^7+1$ is the product of $2n+5$ primes.

Note that $x^7+1 = (x+1)(x^6-x^5+x^4-x^3+x^2-x+1).$ By the inductive hypothesis, we know that $x+1$ is the product of $2n+3$ primes, so it suffices to show that $x^6-x^5+x^4-x^3+x^2-x+1$ is composite.

Since $x^6-x^5+x^4-x^3+x^2-x+1=(x+1)^6 - 7x(x^2+x+1)^2$ and $x=7^{7^{n}}$ , $x^6-x^5+x^4-x^3+x^2-x+1$ is the difference of two squares, therefore is composite.

Thus, $7^{7^{n+1}}+1$ is the product of at least $(2n+3)+2=2n+5$ primes, and we are done. $\square$