Prove that the number $3^{3^n} + 1$ has at least $2n + 1$ prime factors.

Question

For any natural $n,$ prove that $3^{3^n} + 1$ has at least $2n + 1$ prime factors.

My idea was to use induction:

• for $n = 1$: $$f(1) = 3^3 + 1 = 28 = 7*2^2$$
• let it be true for $n = k$, then for $n = k + 1$: $$f(k + 1) = 3^{3^{k + 1}} + 1 = 3^{3*3^k} + 1 = (3^{3^k} + 1)(3^{2*3^k} - 3^{3^k} + 1) = f(k)\times(3^{2*3^k} - 3^{3^k} + 1)$$

Now I have a problem: how to prove that $(3^{2*3^k} - 3^{3^k} + 1)$ is not a prime number?

Or, if it is harder than solving the original problem, please give a hint where I turned the wrong way.

Answer 1

$$\large(3^{2\times3^k} - 3^{3^k} + 1) = (3^{3^k}-3^{(3^k+1)/2}+1)(3^{3^k}+3^ {(3^k+1)/2}+1)$$

Answer 2

We have: $$3^{2\cdot3^k} - 3^{3^k} + 1=(3^{3^k}+3^{\frac{3^k+1}{2}}+1)(3^{3^k}-3^{\frac{3^k+1}{2}}+1)$$ And for $k>0$ both factors are greater than one. This factorization can be deduced from the fact that $f(2)=387400807=19441\cdot19927$ and that both factors are close to each other.