\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{18: Quadratic Reciprocity}{CS681}{Piyush P Kurur}{Ramprasad Saptharishi} \section*{Overview} Polynomial factorization and randomized primality testing were one of the first examples of the power of randomization. Two standard algorithms for primality testing (randomized) are the Miller-Rabin test and the Solovay-Strassen test. We shall build some theory on quadratic reciprocity laws before we get into the Solovay Strassen test. \section{Quadratic Reciprocity} The reciprocity laws are closely related to how primes split over {\em number fields.} Let us first understand what these number fields are. \begin{definition} An algebraic integer over $\Q$ is an element $\zeta$ such that it is a root of a monic polynomial in $\Z[X].$ For example, the number $\frac{1}{2} + i\frac{\sqrt{3}}{2}$ is an algebraic integer as it is a root of $x^2 -x+1.$ A number field is a finite extension of $\Q.$ One could think of this as just adjoining an algebraic number to $\Q.$ \end{definition} Note that number fields are strange objects. They may not even be UFDs. We saw the example when we consider $\Q(\sqrt{-5})$, the number $6$ factors as both $3\times 2$ and $(1+\sqrt{-5})(1 - \sqrt{-5}).$ However, if one were to consider factorization over ideals, they form unique factorizations. \subsection{The Legendre Symbol} Fix an odd prime $p.$ We want to study equations of the form $X^2 - a$ over $\F_p.$ What does it mean to say that this has a solution in $\F_p?$ It means that $a$ has a square-root in $\F_p$ or $a$ is a square in $\F_p.$ The legendre symbol captures that. \begin{definition} For $a\in \F_p$, the legendre symbol $\legendre{a}{p}$ is defined as follows: $$ \legendre{a}{p} = \begin{cases}0 & \text{if $p\mid a$}\\-1 &\text{if $a$ is not a square modulo $p$}\\1 & \text{if $a$ is a square modulo $p$}\end{cases} $$ \end{definition} \begin{proposition} $$ \legendre{ab}{p} = \legendre{a}{p}\legendre{b}{p} $$ \end{proposition} The proof is fairly straight forward; just consider them case by case when they are $-1,0,1.$ Thus, the above proposition tells us that the $\legendre{\cdot}{p}$ is a homomorphism from $\Z/p\Z$ to $\inbrace{-1,0,1}.$\\ Another observation is that since $\F_p^\star$ is cyclic, there is a generator $b.$ Then we can write $a = b^t.$ We then have, $$ a = \begin{cases} 0 & \text{if $p\mid a$}\\-1 & \text{if $a$ is not a square modulo $p$}\\1& \text{if $a$ is a square modulo $p$}\end{cases} $$ and therefore $\legendre{a}{p} = a^{\frac{p-1}{2}}.$\\ Note that $x^2 = y^2 \implies x=y$ or $x=-y$ and therefore, the number of squares in $\F_p^\star$ is exactly $\frac{p-1}{2}.$ And if the generator of the group is a quadratic non-residue (not a square), then any odd power of the generator is also a non-residue. \section{Quadratic Reciprocity Theorem} \begin{theorem} Let $p$ and $q$ be odd primes (not equal to each other). Then \bea{ \legendre{2}{p} & = & (-1)^{\frac{p^2 -1}{8}}\\ \legendre{p}{q}\legendre{q}{p} & = &(-1)^{\frac{p-1}{2}\frac{q-1}{2}} } \end{theorem} \begin{proof} We shall prove the part of $\legendre{2}{p}$ in this class and do the other in the next. The idea is to go to a field extension (if necessary) and evaluate certain elements in two ways to get what we want. In the case of $\legendre{2}{p}$ we shall go to the extension $\F_p(i)$ where $i$ is a square root of $-1.$ Firstly note that this needn't be a proper extension at all. For example, in $\F_5$, we already have a root of $-1$ which is $2.$ Infact, for every prime of the form $1\bmod{4}$, we have a square root of $-1.$ So we will go to an extension if necessary. Now set $\tau = 1+i.$ We know that $\tau^2 = 1 - 1 + 2i = 2i$ and $\tau^p = 1 + i^p$ in $\F_p.$ We could also evaluate $\tau^p$ as $\tau\cdot(\tau^2)^{\frac{p-1}{2}}.$ Also $(1+i)^{-1} = \frac{1-i}{2}.$ \bea{ 1+i^p & = & \tau^p\\ & = & \tau (2i)^{\frac{p-1}{2}}\\ & = & (1+i) 2^{\frac{p-1}{2}}i^{\frac{p-1}{2}}\\ \implies \frac{(1+i^p)(1 - i)}{2} & = & 2^{\frac{p-1}{2}}i^{\frac{p-1}{2}}\\ \implies \frac{1+i^p - i - i^{p+1}}{2} & = & \legendre{2}{p}i^{\frac{p-1}{2}} } \noindent {\bf Case 1:} When $p = 1\bmod{4}$ Then $i\in \F_p$ and the above equation reduces to \bea{ \frac{1 + i - i +1}{2} & = & \legendre{2}{p}(-1)^{\frac{p-1}{4}}\\ \implies \legendre{2}{p} &= &(-1)^{\frac{p-1}{4}} } \noindent {\bf Case 2:} When $p = 3\bmod{4}$ \bea{ \frac{1 - i - i - 1}{2} & = & \legendre{2}{p}i^{\frac{p-1}{2}}\\ \implies i^3 & = & \legendre{2}{p}i^{\frac{p-1}{2}}\\ \implies \legendre{2}{p} & = & i^{\frac{1 - p}{2}+3} = i^{\frac{8 - (1+p)}{4}}\\ & = & (-1)^{\frac{p+1}{4}} } Therefore, $$ \legendre{2}{p} = \begin{cases} (-1)^{\frac{p-1}{4}} & p = 1\bmod{4}\\ (-1)^{\frac{p+1}{4}} & p = 3\bmod{4}\end{cases} $$ and combining the two, we get $$ \legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} $$ \end{proof} The proof of the other part is very similar. We consider a similar $\tau$ and evaluate $\tau^p$ in two different ways to get to our answer. We shall do this in the next class. \end{document}