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

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.

• We can show there are atleast $n$ distinct prime divisors. Using the gcd =1. Commented May 15, 2019 at 6:14
• @taritgoswami Yes, thanks, it makes the task wider. Commented May 15, 2019 at 6:16

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