\begin{document}
\documentclass[11pt]{article}

\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{complexity}
\usepackage{graphicx}

\usepackage{palatino} %what a beautiful font!


\newcommand{\handout}[5]{
  \noindent
  \begin{center}
    \framebox[\textwidth]{
      \vbox{
        \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Number Theory }
       }
        \vspace{4mm}
        \hbox to \textwidth { {\Large \hfill #5  \hfill} }
        \vspace{2mm}
        \hbox to \textwidth { {\em #3 \hfill #4} }
      }
    }
  \end{center}
  \vspace*{4mm}
}

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

\newtheorem{theorem}{Theorem}
\newtheorem{theorem*}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[]{Fact}
\newtheorem{subclaim}[theorem]{Subclaim}

% 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{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\intersection}{\cap}
\newcommand{\Intersection}{\bigcap}
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inv}[1]{#1^{-1}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\iso}{\cong}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}
\newcommand{\legendre}[2]{\inparen{\frac{#1}{#2}}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\DeclareMathOperator{\Sym}{Sym}
\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{\llhd}{\!\!\lhd\!\!\lhd}
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}


% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\R}{\mathbb{R}}
\renewcommand{\C}{\mathbb{C}}

%for algorithms
\renewcommand{\algorithmicrequire}{\textbf{Input:}}

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

%for Quantum computing
\newcommand{\q}[1]{\left|#1\right\rangle}


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

\section*{Overview}

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.$ 
\bea{
\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}$
\bea{
\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.$
\bea{
\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
       q^{\frac{p-1}{2}}\legendre{-1}{q}^{\frac{p-1}{2}}\\
       & = & \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. 
\begin{definition}
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}
\end{cases}
$$
\end{definition}

The Jacobi symbol also satisfies some nice multiplicative properties
\begin{itemize}
\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}$
\end{itemize}

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

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

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.$ 
\end{document}