\usepackage{palatino} %what a beautiful font!

        \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Number Theory }
        \hbox to \textwidth { {\Large \hfill #5  \hfill} }
        \hbox to \textwidth { {\em #3 \hfill #4} }

\newcommand{\lecture}[4]{\handout{#1}{#2}{Instructor: #3}{Scribe:
    #4}{Lecture #1}}


% my custom commands
\newcommand{\inparen}[1]{\left(#1\right)}             %\inparen{x+y}  is (x+y)
\newcommand{\inbrace}[1]{\left\{#1\right\}}           %\inbrace{x+y}  is {x+y}
\newcommand{\insquar}[1]{\left[#1\right]}             %\insquar{x+y}  is [x+y]
\newcommand{\inangle}[1]{\left\langle#1\right\rangle} %\inangle{A}    is <A>
\newcommand{\abs}[1]{\left|#1\right|}                 %\abs{x}        is |x|
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}        %\norm{x}       is ||x||
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\newcommand{\gpidx}[2]{\insquar{#1 : #2}}             %\gpidx{H}{K}   is [H : K]
\newcommand{\gpigs}[2]{\gpidx{\super{G}{#1}}{\super{G}{#2}}} %Group index of g super ...
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}

% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

%for algorithms

% Problems we look at
\newcommand{\GIso}{\lang{Graph\text{-}Iso}} %Without \text, ugly minus instead of hyphen.

%for Quantum computing

\lecture{19: Quadratic Reciprocity (contd.)}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi}


Last class we proved one part of the Quadratic Reciprocity
Theorem. We shall first finish the proof of the other part and then
get to a generalization of the Legendre symbol -  the Jacobi symbol. 

\section{Proof of Reciprocity Theorem (contd.)}

Recall the statement of the theorem. If $p\neq q$ are odd primes, then
\legendre{p}{q}\legendre{q}{p} = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}

The idea of the proof is just the same. We choses $\tau = 1+i$ last
time and we got a $2^{\frac{p-1}{2}}$ term while computing $\tau^p.$
It would be the same here as well. 

Let $\zeta$ be a principle $q$-th root of unity. We shall work with
the field $\F_p(\zeta).$ Let 
\tau = \sum_{a\in \F_q^\star}\legendre{a}{q}\zeta^a
Just as before, we compute $\tau^2.$ 
\tau^2 & =
& \inparen{\sum_{a\in \F_q^\star}\legendre{a}{q}\zeta^a}\inparen{\sum_{b\in \F_q^\star}\legendre{b}{q}\zeta^b}\\
  & = & \sum_{a,b\in \F_q^\star}\legendre{a}{q}\legendre{b}{q}\zeta^{a+b} \\
  & = & \sum_{a,b\in \F_q^\star}\legendre{a}{q}\legendre{b^{-1}}{q}\zeta^{a+b}\\
  & = & \sum_{a,b\in \F_q^\star}\legendre{ab^{-1}}{q}\zeta^{a+b}
Let us do a change of variable, by putting $c = ab^{-1}$
\tau^2 & = & \sum_{c,b\in \F_q^\star}\legendre{c}{q}\zeta^{bc + b}\\
       & = & \sum_{-1\neq
       c\in \F_q^\star}\legendre{c}{q}\sum_{b\in \F_q^\star}(\zeta^{c+1})^b
       + \sum_{b\in \F_q^\star}\legendre{-1}{q}
Since both $p$ and $q$ are primes and $-1\neq c\in \F_q^\star$,
$\zeta^{c+1}$ is also a principle $q$-th root of unity. And therefore,
$\sum_b (\zeta^{c+1})^b = -1.$ Therefore,
\tau^2 = \sum_{-1\neq c \in \F_q^\star}\legendre{c}{q} + (q-1)\legendre{-1}{q}
Look at the first term. If one were to sum over all elements of
$\F_q^\star$, then half of the $\legendre{c}{q}$ would be $1$ and the
other would be $-1$ thus fully cancelling off. Since we are
just excluding $c=-1$, the first term is just $\legendre{-1}{q}.$
\tau^2 = \legendre{-1}{q} + (q-1)\legendre{-1}{q} = q\legendre{-1}{q}

Now to evaluate $\tau^p.$
\tau^p & = & \sum_{a\in \F_q^\star}\legendre{a}{q}\zeta^{ap}\\
       & = & \sum_{c\in \F_q^\star}\legendre{cp^{-1}}{q}\zeta^c \qquad
       (c = ap)\\
       & = & \legendre{p^{-1}}{q}\sum_{c\in \F_q^\star}\legendre{c}{q}\zeta^c\\
       & = & \legendre{p}{q}\tau\\
\tau^p & = & \tau(\tau^2)^{\frac{p-1}{2}}\\
\implies \legendre{p}{q}\tau & = & \tau
       & = & \tau \legendre{q}{p}(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\\
\implies \legendre{p}{q}\legendre{q}{p}& =& (-1)^{\frac{p-1}{2}\frac{q-1}{2}}\qed

\section{Jacobi Symbol}

The legendre symbol $\legendre{m}{n}$ can be naturally generalized to the case when $m$
and $n$ are odd and coprime numbers. 
Suppose $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}.$ Then
the Jacobi symbol, also represented as $\legendre{m}{n}$, is defined
as follows
\legendre{m}{n} = \begin{cases}
0 & \text{if $(m,n)\neq 1$}\\
\prod_{i=1}^k \legendre{m}{p_i}^{\alpha_i} & \text{otherwise}

The Jacobi symbol also satisfies some nice multiplicative properties
\item $\legendre{m_1m_2}{n} = \legendre{m_1}{n}\legendre{m_2}{n}$
\item $\legendre{m}{n_1n_2} = \legendre{m}{n_1}\legendre{m}{n_2}$

Using the above properties, we can get a generalize the theorem on the
legendre symbol as well.

If $m,n$ are odd numbers such that $(m,n) = 1$, then
\legendre{2}{n} & = & (-1)^{\frac{n^2 - 1}{8}}\\
\legendre{m}{n}\legendre{n}{m} & = & (-1)^{\frac{m-1}{2}\frac{n-1}{2}}

We shall prove this theorem in the next class. The proof will just be
using induction on the factors of $m$ and $n.$ \\

{\bf WARNING: }Please note that the Jacobi symbol $\legendre{m}{n}$ doesn't say anything
about whether or not $m$ is a square modulo $n.$ For example, if $n =
p_1p_2$ and $m$ was chosen such that $m$ is not a square modulo $p_1$
or $p_2.$ Then the Jacobi symbol $\legendre{m}{p_1p_2} = (-1)(-1) = 1$
but $m$ is not a square in $p_1p_2.$