proof that $n^{2}-n+41$ is prime for $0\leq n\leq 40$

We show that for $0\leq n\leq 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 $p<41$. 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\leq 40$. Then

 $n^{2}-n+41\leq 40^{2}-40+41<41^{2}$

and thus $n^{2}-n+41$ has a prime factor $q<41$. Write $n^{2}-n+41=qc$; then $qx^{2}+(2n-1)xy+cy^{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$, $qx^{2}+(2n-1)xy+cy^{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 $<41$, so cannot represent $q$. Contradiction. So $n^{2}-n+41$ is prime for $n\leq 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$.

Title proof that $n^{2}-n+41$ is prime for $0\leq n\leq 40$ ProofThatN2n41IsPrimeFor0leqNleq40 2013-03-22 16:55:48 2013-03-22 16:55:48 rm50 (10146) rm50 (10146) 7 rm50 (10146) Proof msc 11A41