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 (http://planetmath.org/IntegralBinaryQuadraticForms) 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

n2-n+41402-40+41<412

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

(2n-1)2-4qc=4n2-4n+1-4(n2-n+41)=-163

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 (http://planetmath.org/IntegralBinaryQuadraticForms) 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