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