<s>[INST] Number Theory: Prove that $7^{7^n}+1$ can be shown as product of at least $2n+3$ prime numbers Prove that for each natural number $n$, $7^{7^n}+1$ can be represented as product of at least $2n+3$ prime numbers. (Prime numbers are not necessarily different)
Any hints how to start the proof?
 [/INST] Aurifeuillean factorization gives
$$7^{14k+7} + 1 = (7^{2k+1}+1)\cdot(C-D)(C+D)$$
with $$C,D=(7^{6k+3} + 3\cdot 7^{4k+2} + 3\cdot 7^{2k+1} + 1),(7^{5k + 3} + 7^{3k+2} + 7^{k+1})$$ 
so for $14k+7=7^{n+1}$:
$$\begin{align*}7^{7^{n+1}} + 1 \;= &\;\;(7^{7^n}+1)\\
&\cdot\left[(7^{3\cdot7^n} + 3\cdot 7^{2\cdot7^n} + 3\cdot 7^{7^n} + 1)+(7^{(5\cdot7^n+1)/2} + 7^{(3\cdot7^n+1)/2} + 7^{(7^n+1)/2})\right]\\
&\cdot\left[(7^{3\cdot7^n} + 3\cdot 7^{2\cdot7^n} + 3\cdot 7^{7^n} + 1)-(7^{(5\cdot7^n+1)/2} + 7^{(3\cdot7^n+1)/2} + 7^{(7^n+1)/2})\right]\end{align*}$$ 
For $n=0$ this gives $$7^{7^1}+1=2^3\cdot \text{ two factors}$$
So by induction $7^{7^n}+1$ is a product at least $2n+3$ factors $>1$.
</s>