# The Sign of the Quadratic Gauss Sum and Quadratic Reciprocity

Today marks the birthday of Karl Friedrich Gauss, the “Prince of Mathematicians”, who was born on April 30, 1777.  In honor of Gauss’s 238th birthday, I thought I would blog about one of Gauss’s favorite theorems — the Law of Quadratic Reciprocity — and its relation to the sign of the quadratic Gauss sum, which we will determine using the Discrete Fourier Transform.  Our exposition mostly follows this paper by Ram Murty.  Regarding the sign of the quadratic Gauss sum, Gauss conjectured the correct answer in his diary in May 1801, but it took more than four years until he was able to find a proof in August 1805. Gauss wrote to his friend W. Olbers that seldom had a week passed for four years that he had not tried in vain to prove his conjecture.  Then:

Finally, two days ago, I succeeded – not on account of my hard efforts, but by the grace of the Lord. Like a sudden flash of lightning, the riddle was solved. I am unable to say what was the conducting thread that connected what I previously knew with what made my success possible.

# Quadratic reciprocity and Zolotarev’s Lemma

I want to explain a beautiful proof of the Law of Quadratic Reciprocity from c. 1874 due to Egor Ivanovich Zolotarev (1847-1878). Some time ago I reformulated Zolotarev’s argument (as presented here) in terms of dealing cards and I posted a little note about it on my web page. After reading my write-up (which was unfortunately opaque in a couple of spots), Jerry Shurman was inspired to rework the argument and he came up with this elegant formulation which I think may be a “proof from the book”.  The following exposition is my own take on Jerry’s argument.  The proof requires some basic facts about permutations, all of which are proved in this handout.

Let $m$ and $n$ be odd relatively prime positive integers.  You have a stack of $mn$ playing cards numbered 0 through $mn-1$ and you want to deal them onto the table in an $m \times n$ rectangular array.  Consider the following three ways of doing this:

Row deal ($\rho$) : Deal the cards into rows, going left to right and top to bottom.