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.