# Professor Halfbrain and the prime numbers

Professor Halfbrain has spent the last few days (and sleepless nights) with analyzing integer numbers of the form $~N_x(n):=n^x+x~$. The professor computed and analyzed thousands and thousands of these numbers, and made a number of fascinating observations:

• For $x=1$, the number $N_1(6)=6^1+1=~7$ is prime.
• For $x=2$, the number $N_2(3)=3^2+2=11$ is prime.
• For $x=3$, the number $N_3(4)=4^3+3=67$ is prime.
• For $x=4$, the number $N_4(1)=1^4+4=~5$ is prime.
• For $x=5$, the number $N_5(2)=2^5+5=37$ is prime.

And so on. And so on. Finally, the professor detected the following extremely deep theorem.

Professor Halfbrain's theorem:
For every positive integer $x$, there exists a positive integer $n$ so that $N_x(n)$ is prime.

This puzzle asks you to decide the correctness of this theorem. If it is correct, then provide a convincing argument for it. If it is incorrect, then state the smallest positive integer $x$ for which the statement is violated.

For $x=27$ and any $n$, there is a factorization $$N_{27}(n)=(n^9+3)(n^{18}-3n^9+9)$$ as a product of two integers bigger than $1$, so $N_{27}(n)$ can never be prime.
More generally, whenever $k\geq 3$ is odd, there is a factorization $$N_{k^k}(n)=\left(n^{k^{k-1}}+k\right)\left(\sum_{i=0}^{k-1} (-k)^{k-1-i}n^{i k^{k-1}}\right),$$ so $N_{k^k}(n)$ is never prime.
A computer search determined that $N_x$ does take a prime value for $x=6,7,\ldots,26$, so $x=27$ is the smallest counterexample. The first prime values are: \begin{align*} N_{6}(1)&=7\\N_{7}(16)&=268435463\\N_{8}(3)&=6569\\N_{9}(2)&=521\\N_{\ 10}(1)&=11\\N_{11}(32)&=36028797018963979\\N_{12}(1)&=13\\N_{13}(118)&\ =859935929762876868984659981\\N_{14}(417)&=\ 4807339234680508004200143948920808143\\N_{15}(2)&=32783\\N_{16}(1)&=\ 17\\N_{17}(14)&=30491346729331195921\\N_{18}(1)&=19\\N_{19}(22)&=\ 32064977213018365645815827\\N_{20}(81)&=\ 147808829414345923316083210206383297621\\N_{21}(76)&=\ 3141126580731587340586460636236874776597\\N_{22}(1)&=23\\N_{23}(12)&=\ 6624737266949237011120151\\N_{24}(55)&=\ 587089817274070447368135511875152587890649\\N_{25}(28)&=\ 1509909033949224437981629384719597593\\N_{26}(15)&=\ 3787675244106352329254150390651\\ \end{align*}
• Wow, that was quick. Is $x=27$ the smallest positive integer for which the statement is violated? – Gamow Mar 5 '16 at 14:52
• I'm not sure. For $x=4$ there is a factorization $N_4(n)=(n^2+2n+2)(n^2-2n+2)$, which is only prime for $n=1$. Mathematica did not find a factorization of $N_x(n)$ (as a polynomial) for any other $x<27$. It is conjectured that an integer polynomial takes infinitely many prime values provided that (1) the polynomial is irreducible, and (2) there is no $p$ for which every value of the polynomial is divisible by $p$. The second condition can be checked for the $N_x$, so if Mathematica's factorizations are correct, there should be a prime value of $N_x$ for each $x<27$. I'll try computer a search – Julian Rosen Mar 5 '16 at 15:23
• Yes, $N_x$ takes a prime value for every $x\leq 26$ (the first prime value for $x=14$ happens for $n=417$, so this would be hard to check by hand). – Julian Rosen Mar 5 '16 at 15:31