0

I have this question: Find natural numbers $n$ so that $n^n+1$ and $(2n)^{2n}+1$ are all primes. My idea is that we consider:

  • $n=1 \Rightarrow n^n+1=2$ and $(2n)^{2n}+1=5$ (correct)
  • $n=2 \Rightarrow n^n+1=5$ and $(2n)^{2n}+1=257$ (correct)

And then, we prove that, with all natural numbers $n$ is greater than $2$, we don't get any primes like above. I mean the solution of problem is $n=1$ or $n=2$. But i don't know to prove that.

Did
  • 279,727
N.Paul
  • 19
  • Note: if $n$ has an odd factor, say $n=2^km$ where $m>1$ is odd, then $x^n+1=\left(x^{2^k}+1\right)\left(x^{n-2^k}-x^{n-2^{k-1}}+\cdots+1\right)$ – lulu Nov 06 '16 at 13:09
  • Do you mean: "Find all natural numbers $n$..."? If so, this is an open problem $-$ see lulu's answer. – TonyK Nov 06 '16 at 13:30
  • Oh yes. I mean all natural numbers n – N.Paul Nov 06 '16 at 13:37

2 Answers2

1

It's easy to prove it for odd $n$ ($n > 1$). In this case, $n^{n}+1$ is even, so it can't be prime.

Alvaro B
  • 69
1

If $n$ has a non-trivial odd factor, say $n=2^km$ where $m>1$ is odd, then $$x^n+1=\left(x^{2^k}+1\right)\left(x^{n-2^k}-x^{n-2^{k-1}}+\cdots+1\right)$$

This, for example, $x^{96}+1=\left(x^{32}+1\right)\left(x^{64}-x^{32}+1\right)$

It follows that, in this case, neither of your terms are prime.

That only leaves the case in which $n$ is a power of $2$. Your expressions would be examples of Fermat primes and little is known about these in general. Indeed, the largest known prime of the form $2^k+1$ is $2^{16}+1=65537$ and it is possible that there are none larger. Certainly none have been found despite extensive searching. Still, though, nothing general has been established.

lulu
  • 70,402