PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: Very high
[parent] proof that $n^2-n+41$ is prime for $0\leq n\leq 40$ (Proof)

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 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

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



"proof that $n^2-n+41$ is prime for $0\leq n\leq 40$" is owned by rm50.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: parent, contradiction, equivalence class, prime factor, composite, integers, represent, equivalent, discriminant, integral binary quadratic form, prime

This is version 4 of proof that $n^2-n+41$ is prime for $0\leq n\leq 40$, born on 2007-04-15, modified 2007-04-15.
Object id is 9195, canonical name is ProofThatN2N41IsPrimeFor0leqNleq39.
Accessed 1313 times total.

Classification:
AMS MSC: 11A41 (Number theory :: Elementary number theory :: Primes)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy
Rating: excellent! by CompositeFan on 2007-04-16 11:59:32
This is an excellent entry! Most popularizers might only go as far as listing each of the primes, while most lexicographers usually stop at saying that Q sqrt(1 - 4p) has to have class number 1. Here rm50 goes above and beyond both of these by connecting the specific case of 41 to the applicable quadratic field and using it prove why it gives primes and not composites in the range specified. Very well done!
[ reply | up ]
40 Works Right? by azdbacks4234 on 2007-04-15 17:07:38
Isn't x^2-x+41 also prime when x=40?
[ reply | up ]
Interact
post | correct | update request | add example | add (any)