proof that $n^2-n+41$ is prime for $0\le n\le 40$

We show that for $0\le n\le 40$, $n^2-n+41$ is prime. Of course, this can easily be seen by considering the $41$ cases, but the proof given here is illustrative of why the statement is true.

Recall that there is only one reduced (http://planetmath.org/IntegralBinaryQuadraticForms) integral binary quadratic form of discriminant $-163$; that form is $x^2+xy+41y^2$. The smallest prime that is represented by that form is $41$. For suppose $p=x^2+xy+41y^2$ and . Then obviously $y=0$, so $p=x^2$, which is impossible. Since equivalent forms represent the same set of integers, it follows that any form of discriminant $-163$ represents no primes less than $41$.

Now suppose $n^2-n+41$ is composite for some $n\le 40$. Then

and thus $n^2-n+41$ has a prime factor . Write $n^2-n+41=qc$; then $q{x}^2+(2n-1)xy+c{y}^2$ represents $q$ ($x=1,y=0$); its discriminant is

$${(2n-1)}^2-4qc=4n^2-4n+1-4(n^2-n+41)=-163$$

Since there is only one equivalence class of forms with discriminant $-163$, $q{x}^2+(2n-1)xy+c{y}^2$ is equivalent to $x^2+xy+41y^2$ and thus represents the same integers. But we know that $x^2+xy+41y^2$ cannot represent any prime , so cannot represent $q$. Contradiction. So $n^2-n+41$ is prime for $n\le 40$.

This proof works equally well for the other cases mentioned in the parent article, since for each of those cases, there is only one reduced form (http://planetmath.org/IntegralBinaryQuadraticForms) of the appropriate discriminant, which is $1-4p$.