Euler's Formula for Primes

Question

Is there any way to prove that the Euler's Formula for Primes $n^2+n+41=41^2$ is valid? How would you even start to prove that a number is prime? If you could prove that a certain number is prime, it maybe possible to do a proof by induction, but since n is limited to $[-40,40)$, induction should theoretically fail (unless you do a modulo 41 <-- oh wait does that give any ideas? except that it's the value of $k=41$). I really don't even know where to start...

Answer 1

Euler's Prime Generating Polynomial is the polynomial $$f(n):=n^2-n+41.$$ It has a pretty property that $f(n)$ is prime for $-39 \leq n \leq 40$.

Of course, $f(41)$ is divisible by $41$, as will be $f(n)$ for any $n \equiv 0 \pmod {41}$. Except for when $n=0$, these cases will all be composite (since $41$ will be a proper divisor). We also observe that other composites arise, such as $f(42)=1763=41 \times 43$ and $f(45)=43 \times 47$.

Calling it a prime generating polynomial is somewhat misleading: it "generates" infinitely many composites too.

It will therefore not be possible to prove by induction that it generates primes, since it doesn't generate primes for all $n \geq 1$.