proof that n2-n+41 is prime for 0n40

We show that for 0n40, n2-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 ( integral binary quadratic form of discriminantPlanetmathPlanetmath -163; that form is x2+xy+41y2. The smallest prime that is represented by that form is 41. For suppose p=x2+xy+41y2 and p<41. Then obviously y=0, so p=x2, which is impossible. Since equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath forms represent the same set of integers, it follows that any form of discriminant -163 represents no primes less than 41.

Now suppose n2-n+41 is composite for some n40. Then


and thus n2-n+41 has a prime factorMathworldPlanetmath q<41. Write n2-n+41=qc; then qx2+(2n-1)xy+cy2 represents q (x=1,y=0); its discriminant is


Since there is only one equivalence classMathworldPlanetmath of forms with discriminant -163, qx2+(2n-1)xy+cy2 is equivalent to x2+xy+41y2 and thus represents the same integers. But we know that x2+xy+41y2 cannot represent any prime <41, so cannot represent q. ContradictionMathworldPlanetmathPlanetmath. So n2-n+41 is prime for n40.

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 ( of the appropriate discriminant, which is 1-4p.

Title proof that n2-n+41 is prime for 0n40
Canonical name ProofThatN2n41IsPrimeFor0leqNleq40
Date of creation 2013-03-22 16:55:48
Last modified on 2013-03-22 16:55:48
Owner rm50 (10146)
Last modified by rm50 (10146)
Numerical id 7
Author rm50 (10146)
Entry type Proof
Classification msc 11A41