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.

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

Alasdair: Thanks! I’ve updated the page.