8
$\begingroup$

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.

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

2 Answers 2

5
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Aurifeuillean_factorization $\endgroup$ Commented May 15, 2019 at 5:57
  • $\begingroup$ Cf. this answer $\endgroup$ Commented May 15, 2019 at 6:02
  • $\begingroup$ Thank you. Never heard about this. $\endgroup$
    – Evgeny
    Commented May 15, 2019 at 6:13
  • $\begingroup$ Examples of the link you left for the two terms, how to get the factorization for the three? $\endgroup$
    – Evgeny
    Commented May 15, 2019 at 6:26
  • $\begingroup$ I'm not sure I understand your question; does this link explain it? $\endgroup$ Commented May 15, 2019 at 6:38
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .