\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}

\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}