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