\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{quadratic reciprocity law}

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{statement}{Statement}\dotfill \pageref*{statement} \linebreak
\noindent\hyperlink{sample_classroom_application}{Sample classroom application}\dotfill \pageref*{sample_classroom_application} \linebreak
\noindent\hyperlink{proofs}{Proofs}\dotfill \pageref*{proofs} \linebreak
\noindent\hyperlink{proof_via_gauss_sums}{Proof via Gauss sums}\dotfill \pageref*{proof_via_gauss_sums} \linebreak
\noindent\hyperlink{zolotarevs_proof}{Zolotarev's proof}\dotfill \pageref*{zolotarevs_proof} \linebreak
\noindent\hyperlink{other_reciprocity_laws}{Other reciprocity laws}\dotfill \pageref*{other_reciprocity_laws} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

In [[number theory]], the quadratic reciprocity law determines a precise relationship between the truth of $p R q$ and the truth of $q R p$, where $p R q$ is this [[binary relation]] on odd [[prime numbers]]: ``$p$ is a square [[modular arithmetic|modulo]] $q$''.

The law of quadratic reciprocity is a celebrated result due to [[Gauss]]; the ideas required to prove it helped to inaugurate modern [[number theory]]. It is today largely considered within the context of [[class field theory]], involving how [[prime number|primes]] decompose in [[Galois extension|abelian extensions]] of [[number fields]].

\hypertarget{statement}{}\subsection*{{Statement}}\label{statement}

For $p \geq 1$ an odd [[prime number]], and for any [[integer]] $a$, define the \textbf{Legendre symbol} (or \emph{quadratic reciprocity symbol}) $\left(\frac{a}{p}\right)$ to be the unique element in $\{-1, 0, 1\}$ for which

\begin{displaymath}
\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \; mod \; p
\end{displaymath}
Notice that the Legendre symbol defines a surjective [[homomorphism]] on a [[cyclic group]]

\begin{displaymath}
(\mathbb{Z}/p)^\ast \cong C_{p-1} \to \{-1, 1\}
\end{displaymath}
whose [[kernel]] is the set of squares in the multiplicative group $(\mathbb{Z}/p)^\ast$, so that $\left(\frac{a}{p}\right) = 1$ means $a$ is a square modulo $p$, and $\left(\frac{a}{p}\right) = -1$ means $a$ is a non-square modulo $p$.

\begin{theorem}
\label{}\hypertarget{}{}
For $p$, $q$ distinct odd primes,

\begin{displaymath}
\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}.
\end{displaymath}
\begin{displaymath}
\,
\end{displaymath}
\begin{displaymath}
\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}
\end{displaymath}
i.e., $2$ is a square modulo $p$ if and only if $p \equiv \pm 1 \; mod \; 8$.

\end{theorem}
The case for odd primes $p$, $q$ can be restated as:

\begin{itemize}%
\item if $p,q$ are odd and $p \equiv 1 \; mod \; 4$, then $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$


\item if $p,q \equiv 3 \; mod \; 4$ then $\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$



\end{itemize}
The law of quadratic reciprocity was first fully proven by \hyperlink{Gauss}{Gauss}, although special cases were proven by [[Fermat]] (who effectively realized when $-1$ was a square modulo $p$ based on his [[two squares theorem]] -- well before Legendre introduced his eponymous symbol), and [[Euler]] (who proved the case for $q = 2$).

None of these early authors were in full possession of modern notations such as the congruence symbol or the Legendre symbol, which greatly economize the amount of thought needed to prove this theorem. Recognition of quadratic reciprocity was likely rooted in empirical observations, for example the study of periods of expansions of $1/q$ in base $p$ (source?).

\hypertarget{sample_classroom_application}{}\subsection*{{Sample classroom application}}\label{sample_classroom_application}

Consider the problem of computing the length of the period of $1/65537$ in its decimal expansion. This period is the same as the least positive exponent $n$ such that $10^n \equiv 1 \; mod \; 65537$, and is a divisor of $65536$ (thus, a power of $2$). Indeed, $65537$ is a [[Fermat prime]]: $2^{2^4} + 1$.

The period is a proper divisor of $65536$ if and only if $10$ is a square modulo $p = 65537$, leading one to contemplate

\begin{displaymath}
\left(\frac{10}{p}\right) = \left(\frac{2}{p}\right) \left(\frac{5}{p}\right)
\end{displaymath}
where the first factor is pretty clearly $1$ (already $2^{32} \equiv 1 \; mod \; p$, so certainly $2^{\frac{p-1}{2}} \equiv 1 \; mod \; p$). The other factor is

\begin{displaymath}
\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) = \left(\frac{2}{5}\right) = -1
\end{displaymath}
and we therefore conclude $10$ is a non-square modulo $65537$, or in other words that the length of the period of $1/65537$ is $65536$.

\hypertarget{proofs}{}\subsection*{{Proofs}}\label{proofs}

There are today several hundred published proofs of the quadratic reciprocity laws; it is rightly regarded as a capstone result in introductions to number theory. We give two proofs here.

\hypertarget{proof_via_gauss_sums}{}\subsubsection*{{Proof via Gauss sums}}\label{proof_via_gauss_sums}

This proof, following \hyperlink{Lang}{Lang} (pp. 76--78), is middling in sophistication but at least indicates the relevance of [[cyclotomic extension]]s of the rationals $\mathbb{Q}$ and [[quadratic extension]]s therein. Let $p$ be a fixed odd prime, and let $\zeta$ be a primitive $p^{th}$ [[root of unity]]. Using the Legendre symbol, we introduce a particular [[character]] sum called a \textbf{[[Gauss sum]]},

\begin{displaymath}
S \coloneqq \sum_a \left(\frac{a}{p}\right) \zeta^a,
\end{displaymath}
where the sum is over non-zero elements $a$ of $\mathbb{Z}/p$.

\begin{lemma}
\label{}\hypertarget{}{}
$S^2 = \left(\frac{-1}{p}\right) p$.

\end{lemma}
\begin{proof}
We have $S^2 = \sum_{a, b} \left(\frac{a b}{p}\right) \zeta^{a + b}$. For any fixed non-zero $a$, as $b$ ranges over all non-zero residue classes, so does $a b$. We may therefore replace $b$ by $a b$ to get

\begin{displaymath}
\itexarray{
S^2 & = & \sum_{a, b} \left(\frac{a^2 b}{p}\right) \zeta^{a + a b} \\ 
 & = & \sum_{a, b} \left(\frac{b}{p}\right) \zeta^{a(1 + b)} \\ 
 & = & \sum_a \left(\frac{-1}{p}\right) \zeta^0 + \sum_{b \neq -1} \left(\frac{b}{p}\right) \sum_a \zeta^{a(1 + b)}
}.
\end{displaymath}
Now, for $b \neq -1$, the character sum $\sum_a \zeta^{a(1+b)}$ evaluates to $-1$ since $1 + \zeta + \ldots + \zeta^{p-1} = 0$. Thus the calculation continues:

\begin{displaymath}
\itexarray{
S^2 & = & \left(\frac{-1}{p}\right) (p-1) + (-1)\sum_{b \neq -1} \left(\frac{b}{p}\right) \\ 
 & = & \left(\frac{-1}{p}\right) p - \sum_b \left(\frac{b}{p}\right) \\ 
 & = & \left(\frac{-1}{p}\right) p
}
\end{displaymath}
which completes the proof.

\end{proof}
Thus $S$ belongs to a quadratic extension of $\mathbb{Q}$, either $\mathbb{Q}(\sqrt{p})$ or $\mathbb{Q}(\sqrt{-p})$ depending on the Legendre symbol. In particular, the prime $p$ is [[ramification|ramified]] in $\mathbb{Q}(\zeta)$.

\begin{proof}
First let $p$, $q$ be two distinct odd primes. With $S$ defined as above, we calculate $S^q \; mod \; q$, where $mod \; q$ indicates the quotient of the [[ideal]] generated by $q$ in the above-mentioned quadratic extension of $\mathbb{Q}$, in two ways.

On the one hand, by the preceding lemma,

\begin{displaymath}
\itexarray{
S^q & = & S(S^2)^{\frac{q-1}{2}} \\
 & = & S\left(\frac{-1}{p}\right)^{\frac{q-1}{2}} p^{\frac{q-1}{2}} \\ 
 & = & S(-1)^{\frac{p-1}{2}\frac{q-1}{2}} p^{\frac{q-1}{2}} \\ 
 & \equiv & S (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \left(\frac{p}{q}\right) \; mod \; q
.}
\end{displaymath}
On the other hand, since raising to the power $q$ is an [[isomorphism|automorphism]] on the [[quotient]] [[ring]] obtained modulo $q$ (either $\mathbb{F}_q \times \mathbb{F}_q$ or $\mathbb{F}_{q^2}$, depending on whether $p$ is a square modulo $q$ or not), we have

\begin{displaymath}
\itexarray{ 
S^q & \equiv & \sum_a \left(\frac{a}{p}\right) \zeta^{a q} \; mod \; q \\ 
 & \equiv & \left(\frac{q}{p}\right) \sum_a \left(\frac{a q}{p}\right) \zeta^{a q} \; mod \; q \\
 & \equiv & \left(\frac{q}{p}\right) S \; mod \; q
}
\end{displaymath}
and now we can cancel $S$ (which is invertible modulo $q$, since $S^2$ is) to arrive at

\begin{displaymath}
\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \left(\frac{p}{q}\right)
\end{displaymath}
which gives the first clause of the reciprocity law.

As for the second clause, we can give a similar analysis. The prime $q = 2$ is ramified in the cyclotomic extension $\mathbb{Q}[i]$ since $(1 + i)^2 = 2 i$, and for any prime $p$ we may calculate $(1 + i)^p \; mod \; p$ in two ways. On the one hand,

\begin{displaymath}
\itexarray{
(1 + i)^p & = & (1+i)(2 i)^{\frac{p-1}{2}} \\ 
 & \equiv & (1+i)i^{\frac{p-1}{2}} \left(\frac{2}{p}\right) \; mod \; p
}
\end{displaymath}
and on the other hand,

\begin{displaymath}
\itexarray{
(1+i)^p & \equiv & 1^p + i^p \; mod \; p
}
\end{displaymath}
and by examining the cases $p \equiv 1, 3, 5, 7 \; mod \; 8$ separately, we easily deduce the second clause.

\end{proof}
\hypertarget{zolotarevs_proof}{}\subsubsection*{{Zolotarev's proof}}\label{zolotarevs_proof}

The (in hindsight obvious!) structural meaning of the Legendre symbol was first given by \hyperlink{Zolotarev}{Zolotarev}:

\begin{lemma}
\label{}\hypertarget{}{}
For $p$ an odd prime and $a$ relatively prime to $p$, $\left(\frac{a}{p}\right)$ is the sign or [[signature of a permutation]] on $(\mathbb{Z}/p)^\ast$ given by multiplying by $a$.

\end{lemma}
\begin{proof}
Both the Legendre symbol $\left(\frac{ }{p}\right) \colon (\mathbb{Z}/p)^\ast \to \{-1, 1\}$ and

\begin{displaymath}
(\mathbb{Z}/p)^\ast \stackrel{Cayley}{\to} Perm((\mathbb{Z}/p)^\ast) \stackrel{sign}{\to} \{-1, 1\}
\end{displaymath}
are homomorphisms \href{http://ncatlab.org/nlab/show/root#roots_of_unity_in_fields_11}{whose domain is a cyclic group}, so it suffices to show they agree on a generator $g$. But $Cayley(g)$ is a cyclic [[permutation]] on $p-1$ elements, hence has sign $(-1)^{p-2} = -1$, which agrees with $\left(\frac{g}{p}\right)$.

\end{proof}
We turn now to Zolotarev's proof of the ``hard'' case of quadratic reciprocity where $p$ and $q$ are distinct odd primes. What is interesting is that from this point forward, we don't use primality of $p$ and $q$ at all, i.e., the remainder of the argument carries over if $p$ and $q$ are replaced by odd, relatively prime integers $m$ and $n$, and we simply define $\left(\frac{a}{n}\right)$ as a sign of a permutation of multiplying by $a$ on $(\mathbb{Z}/n)^\ast$. Indeed, one often defines the \textbf{Jacobi symbol} by

\begin{displaymath}
\left(\frac{a}{n}\right) \coloneqq \prod_{i} \left(\frac{a}{p_i}\right)
\end{displaymath}
where $n = p_1 \ldots p_r$ is the prime factorization of an odd integer, and what we really do is generalize quadratic reciprocity from the Legendre symbol to the Jacobi symbol. Thus, the primality assumption is concentrated purely in the preceding lemma.

\begin{proof}
For $m \gt 1$ an odd number, we consider the set $\mathbb{Z}/m = \{0, 1, \ldots, m-1\}$ as carrying on the one hand a ring structure, and on the other as carrying a structure of linear order (no compatibility between these structures!). Now suppose $m$ and $n$ are odd and relatively prime; then by the [[Chinese remainder theorem]], there is a unique ring isomorphism

\begin{displaymath}
\mathbb{Z}/m n \to \mathbb{Z}/m \times \mathbb{Z}/n.
\end{displaymath}
If we endow $\mathbb{Z}/m \times \mathbb{Z}/n$ with the dictionary or [[lexicographic order]], then there is also a unique isomorphism of linear or [[total orders]]

\begin{displaymath}
(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict} \to \mathbb{Z}/m n
\end{displaymath}
which takes an element $(x, y) \in \mathbb{Z}/m \times \mathbb{Z}/n$ to $n x + y \in \{0, 1, \ldots, m n - 1\}$. (Intuitively, imagine assembling a rectangular array of cards, with $m$ columns and $n$ cards in each column, into a single stack of $m n$ cards, by gathering up the first column, followed by gathering up the second column and placing it underneath, etc.)

The composite $\alpha$ of the functions

\begin{displaymath}
(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict} \stackrel{ord \cong}{\to} \mathbb{Z}/m n \stackrel{ring \cong}{\to} \mathbb{Z}/m \times \mathbb{Z}/n
\end{displaymath}
is thus $(x, y) \mapsto n x + y \mapsto (n x + y, y)$. The composite is thus a juxtaposition of $n$ row permutations, one for each fixed $y$, where $x$ in row $y$ is taken to $n x + y$ in row $y$. The sign of such a permutation $x \mapsto n x + y$ is

\begin{displaymath}
sign((-) + y) \cdot sign(n(-)) = sign(n(-)) = \left(\frac{n}{m}\right)
\end{displaymath}
(since the permutation $(-) + y$ is a cyclic permutation on an odd number of elements, hence is even). Thus

\begin{displaymath}
sign(\alpha) = \left(\frac{n}{m}\right)^n = \left(\frac{n}{m}\right)
\end{displaymath}
where the second equation follows since $n$ is odd.

Similarly, consider $\mathbb{Z}/m \times \mathbb{Z}/n$ with the \emph{reverse} dictionary order, where $(x, y) \lt (x', y')$ if $y \lt y'$ or $y = y'$ and $x \lt x'$. We again have a unique order isomorphism and unique ring isomorphism, and we can analyze their composition $\beta$,

\begin{displaymath}
(\mathbb{Z}/m \times \mathbb{Z}/n)_{RevDict} \stackrel{ord \cong}{\to} \mathbb{Z}/m n \stackrel{ring \cong}{\to} \mathbb{Z}/m \times \mathbb{Z}/n,
\end{displaymath}
as taking $(x, y) \mapsto (x, x + m y)$. We similarly calculate

\begin{displaymath}
sign(\beta) = \left(\frac{m}{n}\right).
\end{displaymath}
Finally, $\beta^{-1} \circ \alpha$ is the unique order-preserving isomorphism

\begin{displaymath}
(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict} \to (\mathbb{Z}/m \times \mathbb{Z}/n)_{RevDict}
\end{displaymath}
which gives a permutation on the underlying set $\mathbb{Z}/m \times \mathbb{Z}/n$, and it remains to show that its sign is $(-1)^{\frac{m-1}{2}\frac{n-1}{2}}$.

But this is easy to see. Recall that given a permutation $\sigma$ on a linearly ordered set (such as $(\mathbb{Z}/m \times \mathbb{Z}/n)_{Dict}$), an \emph{inversion} is a pair $(x \lt y)$ such that $\sigma(x) \gt \sigma(y)$, and if $I(\sigma)$ is the total number of inversions, then

\begin{displaymath}
\sign(\sigma) = (-1)^{I(\sigma)}.
\end{displaymath}
In the present case $\sigma = \beta^{-1} \alpha$, we see $I(\sigma)$ counts pairs of pairs $(i, j)$, $(i', j')$ where $(i, j) \lt (i', j')$ in dictionary order but $(i, j) \gt (i', j')$ in reverse dictionary order; in other words when $i \lt i'$ but $j' \lt j$. The number of such occurrences is

\begin{displaymath}
I(\sigma) = \frac{m(m-1)}{2} \frac{n(n-1)}{2}
\end{displaymath}
whence (again since $m, n$ are odd)

\begin{displaymath}
(-1)^{I(\sigma)} = (-1)^{\frac{m-1}{2}\frac{n-1}{2}}
\end{displaymath}
which completes the proof.

\end{proof}
\hypertarget{other_reciprocity_laws}{}\subsection*{{Other reciprocity laws}}\label{other_reciprocity_laws}

As mentioned earlier, quadratic reciprocity law is due to Gauss and is the first of a number of reciprocity laws in number theory. The Wikipedia article lists a bevy of reciprocity laws, gradually increasing in modernity and abstraction (and power), and culminating in [[Artin reciprocity]], a capstone of the classical [[class field theory]].

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item \href{Jacobi+theta+function#FunctionalEquation}{Jacobi theta function -- Functional equation and Reciprocity}

\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

\begin{itemize}%
\item wikipedia: \href{http://en.wikipedia.org/wiki/Reciprocity_law_%28mathematics%29}{reciprocity laws (mathematics)}


\item Serge Lang, \emph{Algebraic number theory}, Addison-Wesley (1970).



\end{itemize}
\begin{itemize}%
\item [[Carl Friedrich Gauss]], \emph{Disquisitiones arithmeticae} (1801), Article IV.


\item E.I. Zolotareff, \emph{Nouvelle d\'e{}monstration de la loi de de r\'e{}ciprocit\'e{} de Legendre}, Nouvelles Annales de Math\'e{}matiques. 2e s\'e{}rie 11 (1872) 354--362.



\end{itemize}
[[!redirects quadratic reciprocity]] [[!redirects quadratic reciprocity law]] [[!redirects Legendre symbol]] [[!redirects Legendre symbols]]



\end{document}