Quadratic congruences are much more complex than linear congruences. If you’re interested in the details, see these notes on quadratic congruences.
When I started looking into this, I thought my number theory class years ago covered the details but that I’d forgotten them. Looking back, I see that my instructor and my textbook neglected some cases. Then I looked at a few other references and saw that they also left out some cases. I put together some notes by pulling together information from several incomplete but complementary references.
{ 2 comments… read them below or add one }
Alasdair McAndrew 01.05.11 at 14:18
This post just got tweeted as as an “Algebra Fact”. The last line should read “if a= 1 (mod 4) there is no analogous formula.” That’s true, but in that case you would use the Shanks-Tonelli algorithm. Maybe you should provide a link to it!
Just my two cents.
Otherwise a nice, complete and informative post – as your always are. I enjoy them.
cheers,
Alasdair
John 01.06.11 at 20:54
Alasdair: Thanks! I’ve updated the page.