%\documentclass[a4paper,twoside,draft]{article} \documentclass[a4paper,twoside,reqno,12pt,openany,notitlepage]{amsbook} \usepackage[headings]{fullpage} %\usepackage[fulloldstyle]{fourier} \title{Elementary Number Theory} \author{David Pierce} \date{\today} \address{Mathematics Dept\\ Middle East Technical University\\ Ankara 06531, Turkey} \email{dpierce@metu.edu.tr} \urladdr{http://www.math.metu.edu.tr/~dpierce} \usepackage{amssymb,amsmath} \usepackage{url} \usepackage{verbatim} % allows a comment environment: \usepackage[all]{xy} \usepackage{pstricks} \usepackage{textcomp} % supposedly useful with \oldstylenums \usepackage{multicol} %\usepackage{showlabels} \usepackage{layout} \usepackage{hfoldsty} % this didn't work until I added missing % brackets to some of the files. %\newcommand{\osn}[1]{\oldstylenums{#1}} \newcommand{\asterism}{\mbox{}\hfill$*\qquad*\qquad*\qquad*\qquad*$\hfill} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \renewcommand{\leq}{\leqslant} \renewcommand{\geq}{\geqslant} \renewcommand{\setminus}{\smallsetminus} %\renewcommand{\phi}{\varphi} \newcommand{\Iff}{} \let\Iff\iff \renewcommand{\iff}{\leftrightarrow} \newcommand{\Exists}[1]{\exists{#1}\;} \renewcommand{\emptyset}{\varnothing} \renewcommand{\epsilon}{\varepsilon} %%%%%%%%%%%%%%%%%%%%%%% \newcommand{\lto}{\Rightarrow} \renewcommand{\land}{\mathrel{\&}} %\newcommand{\size}[1]{\left|#1\right|} \newcommand{\size}[1]{\lvert#1\rvert} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \makeindex \newcommand{\defn}[2]{\textbf{#1#2}\index{#1}} \newcommand{\defnplain}[2]{\textbf{#1#2}} \newcommand{\tech}[2]{\textsl{#1#2}\index{#1}} \renewcommand{\theenumi}{\alph{enumi}} \renewcommand{\labelenumi}{\textnormal{(\theenumi)}} \renewcommand{\theenumii}{\roman{enumii}} \renewcommand{\labelenumii}{\textnormal{(\theenumii)}} %%%%%%%%%%%%%%% \newcommand{\divides}{\mathrel{|}} \newcommand{\ndivides}{\mathrel{\nmid}} \newcommand{\ord}[2]{\operatorname{ord}_{#1}(#2)} \newcommand{\ls}[2]{\Bigl(\displaystyle\frac{#1}{#2}\Bigr)} % set-theoretic relations: \newcommand{\included}{\subseteq} % [the name suggests the meaning here] \newcommand{\nincluded}{\not\subseteq} % not included \newcommand{\pincluded}{\subset} % proper inclusion \newcommand{\includes}{\supseteq} \newcommand{\stnd}[1]{\mathbb{#1}} \newcommand{\N}{\stnd{N}} % natural numbers %\newcommand{\varN}{\omega} % my usual preference for this %\newcommand{\Zp}{\Z_{+}} % positive integers \newcommand{\Z}{\stnd{Z}} % integers \newcommand{\Q}{\stnd{Q}} % rationals \newcommand{\Pri}{\stnd{P}} % primes \newcommand{\R}{\stnd{R}} % reals \newcommand{\C}{\stnd{C}} % complex numbers \newcommand{\units}[1]{#1^{\times}} \newcommand{\Zmod}[1][n]{\Z/(#1)} \newcommand{\Zmodu}[1][n]{\units{(\Zmod[#1])}} \newcommand{\scr}[1]{\operatorname{s}(#1)} \newcommand{\pred}[1]{\operatorname{pred}(#1)} \DeclareMathOperator{\lcm}{lcm} \DeclareMathOperator{\dee}{d} % \newcommand{\rten}{\sqrt{10}} \newcommand{\dsp}{\,} % space between blocks of three digits \newcommand{\hw}[1]{\hfill{}\textnormal{[#1]}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Theorem-like environments % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtheorem*{theorem*}{Theorem} \newtheorem*{lemma*}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{axdef}[theorem]{Axiom and definition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{problem}{Problem}[section] \renewcommand{\theproblem}{\arabic{section}.\arabic{problem}} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{parag}[theorem]{} \newtheorem{xca}{Exercise}[section] \renewcommand{\thexca}{\arabic{section}.\arabic{xca}} \newtheorem*{solution}{Solution} \theoremstyle{remark} \newtheorem{remarks}[theorem]{Remarks} \newtheorem{remark}[theorem]{Remark} \newtheorem*{remark*}{Remark} %\numberwithin{section}{chapter} %\numberwithin{xca}{section} \numberwithin{equation}{section} \renewcommand{\theequation}{\fnsymbol{equation}} \begin{document} \frontmatter \maketitle \mainmatter \chapter*{Preface} %These notes are based on my lectures, in the fall of 2007, in This book is simply a record of Elementary Number Theory (Math 365), as taught by me in the fall semester of the 2007/8 academic year at METU. The contents of the chapters are as follows: \begin{enumerate} \renewcommand{\theenumi}{\arabic{enumi}} \item Some notes (with exercises) called `Foundations of number-theory', made available on the web at the beginning of the semester. \item The lectures themselves (with some mild corrections) as written from memory and from the handwritten notes that I used during the lectures. The main reference for the course was \cite{Burton}, but I used also \cite{MR2135478}. The Tuesday lectures were two hours; Thursday, one. (Each hour is 50 minutes.) \item Exercise sets (with a few corrections and cross-references), offered nearly every week. \item Examinations, with my solutions and remarks. There were three in-term examinations, on October 23 (Tuesday), November 27 (Tuesday), and December 27 (Thursday), and there was a final examination on January 11. \end{enumerate} On the day of an examination, I introduced no new material in class. Class was cancelled November 13 and 15, because I was away at the \emph{Centre Internationale de Rencontres Math\'ematiques} in Marseilles. October 11 (Thursday) fell within the \emph{\c Seker Bayram\i;} December 20 (Thursday), the \emph{Kurban Bayram\i.} There were originally to be only two examinations in term. The night before the second examination, a number of students came to ask to postpone the exam. Since it was too late to make such a change, I offered instead to give a third in-term exam and count the best two only towards the final grade. \tableofcontents \chapter{Foundations of Number-Theory}\label{ch:foundations} \input{foundations.tex} \chapter{Lectures}\label{ch:lectures} \section{September 20, 2007 (Thursday)} What can we say about the sequence \begin{equation*} 3,6,10,15,21,28,\dots? \end{equation*} We can add a couple of terms to the beginning, making it \begin{equation*} {0,1,3,6,10,15,21,28,\dots} \end{equation*} The terms increase by $1$, $2$, $3$, and so on. What do the numbers \emph{look like?} They are the \defn{triangular number}{s:} \begin{center} \begin{picture}(120,20.8)(0,11.2) \put(2,30){\circle*4} \put(18,30){\circle*4} \put(26,30){\circle*4} \put(42,30){\circle*4} \put(50,30){\circle*4} \put(58,30){\circle*4} \put(74,30){\circle*4} \put(82,30){\circle*4} \put(90,30){\circle*4} \put(98,30){\circle*4} \put(114,30){\dots} \put(22,24.4){\circle*4} \put(46,24.4){\circle*4} \put(54,24.4){\circle*4} \put(78,24.4){\circle*4} \put(86,24.4){\circle*4} \put(94,24.4){\circle*4} \put(50,18.8){\circle*4} \put(82,18.8){\circle*4} \put(90,18.8){\circle*4} \put(86,13.2){\circle*4} \end{picture} \end{center} Let $t_{0}={0}$, $t_{1}=1$, $t_{2}={3}$, \&c. The \defn{recursive}{} definition is \begin{equation*} t_{0}={0},\quad t_{n+1}=t_n+n+1. \end{equation*} There is a \emph{closed} form: \begin{equation}\label{eqn:tn} t_n=\sum_{k=1}^nk=\binom{n+1}{2}=\frac{n(n+1)}{2}. \end{equation} We can prove this by \defn{induction}: It is true when $n={0}$ (or $n=1$), and if it is true when $n=k$, then \begin{equation*} t_{k+1}=t_k+k+1 =\frac{k(k+1)}{2}+k+1 =\frac{(k+1)(k+{2})}{2}, \end{equation*} so it is true when $n=k+1$. By induction, \eqref{eqn:tn} is true for all $n$. But \emph{why} is equation~\eqref{eqn:tn} true? This can be seen from a picture: two copies of $t_n$ fit together to make a rectangle of $n(n+1)$ dots: \begin{center} \begin{picture}(36,28) \multiput(2,26)(8,0)4{\circle*4} \multiput(2,18)(8,0)3{\circle*4} \multiput(2,10)(8,0)2{\circle*4} \multiput(2,2)(8,0)1{\circle*4} \multiput(34,26)(8,0)1{\circle4} \multiput(26,18)(8,0)2{\circle4} \multiput(18,10)(8,0)3{\circle4} \multiput(10,2)(8,0)4{\circle4} \end{picture} \end{center} Similarly, $(n+1)^{2}=t_{n+1}+t_n$, since \begin{equation*} t_{n+1}+t_n=\frac{(n+1)(n+{2})}{2}+\frac{n(n+1)}{2}=\frac{n+1}{2}(n+{2}+n)=(n+1)^{2}; \end{equation*} but this can be seen in a picture: \begin{center} \begin{picture}(36,36) \multiput(2,34)(8,0)5{\circle*4} \multiput(2,26)(8,0)4{\circle*4} \multiput(2,18)(8,0)3{\circle*4} \multiput(2,10)(8,0)2{\circle*4} \multiput(2,2)(8,0)1{\circle*4} \multiput(34,26)(8,0)1{\circle4} \multiput(26,18)(8,0)2{\circle4} \multiput(18,10)(8,0)3{\circle4} \multiput(10,2)(8,0)4{\circle4} \end{picture} \end{center} What can we say about the following sequence? \begin{equation*} {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,\dots} \end{equation*} It is the sequence of odd numbers. Also, the first $n$ terms seem to add up to $n^{2}$, that is, \begin{equation}\label{eqn:n2} n^{2}=\sum_{k=1}^n({2}k-1). \end{equation} We can prove this by induction: It is true when $n={0}$, and if it is true when $n=k$, then \begin{equation*} (k+1)^{2}=k^{2}+{2}k+1=\sum_{j=1}^k({2}j-1)+{2}k+1=\sum_{j=1}^{k+1}({2}j-1), \end{equation*} so it is true when $n=k+1$. Therefore~\eqref{eqn:n2} is true for all $n$. A picture shows why: \begin{center} \begin{picture}(36,36) \multiput(2,34)(16,0)3{\circle*4} \multiput(18,26)(16,0)2{\circle*4} \multiput(2,18)(8,0)3{\circle*4} \put(34,18){\circle*4} \put(34,10){\circle*4} \multiput(2,2)(8,0)5{\circle*4} \multiput(10,34)(16,0)2{\circle4} \multiput(2,26)(8,0)2{\circle4} \put(26,26){\circle4} \multiput(26,18)(8,0)2{\circle4} \multiput(2,10)(8,0)4{\circle4} \end{picture} \end{center} Finally, observe: \begin{equation*} {1},\underbrace{{3,5}}_8,\underbrace{{7,9,11}}_{{27}}, \underbrace{{13,15,17,19}}_{{64}},\underbrace{{21,23,25,27,29}}_{{125}},\dots \end{equation*} Does the pattern continue? As an exercise, write the suggested equation, \begin{equation*} n^{3}=\sum_{\dots}^{\dots}\dots, \end{equation*} and prove it. (The theorem was apparently known to Nicomachus of Gerasa \cite[II.20.5, p.~263]{Nicomachus}, almost 2000 years ago.) \asterism{} We are studying the natural numbers, 0, 1, 2, \dots. (Some people start with 1 instead.) They compose the set $\N$. Everything about $\N$ follows from the following five conditions: \begin{enumerate} \item there is a first natural number, \defn{zero}{} (${0}$); \item each $n$ in $\N$ has a \defn{successor}{}, $\scr n$; \item ${0}$ is not a successor; \item distinct numbers have distinct successors: if $n\neq m$, then $\scr n\neq\scr m$; \item \defn{induction}: if $A\included\N$, and \begin{enumerate} \item ${0}\in A$, and \item if $n\in A$, then $\scr n$ is in $A$, \end{enumerate} then $A=\N$. \end{enumerate} \section{September 25, 2007 (Tuesday)} \begin{theorem*}[Recursion] Suppose $A$ is a set with an element $b$, and $f\colon A\to A$. Then there is a \emph{unique} function $g$ from $\N$ to $A$ such that \begin{enumerate} \item $g({0})=b$, and \item $g(\scr n)=f(g(n))$ for all $n$ in $\N$. \end{enumerate} \end{theorem*} For the proof, see~\cite{DPfnth}. By recursion, we define addition and multiplication: \begin{align*} m+{0}&=m,& m\cdot{0}&={0},\\ m+\scr n&=\scr{m+n},& m\cdot{\scr n}&=m\cdot n+m. \end{align*} Then the usual properties can be proved, usually by induction (exercise; see~\cite{DPfnth}). We write $1$ for $\scr {0}$, so $\scr n=n+1$. Some books suggest wrongly that everything about $\N$ is a consequence of: \begin{theorem*}[Well-Ordering Principle] Every non-empty subset of $\N$ has a least element. \end{theorem*} But what does \emph{least} mean? The \defn{least}{} element of $A$ is some $n$ such that \begin{enumerate} \item $n\in A$; \item if $m\in A$, then $n\leq m$. \end{enumerate} On $\N$, we define $\leq$ by \begin{equation*} m\leq n\Iff m+k=n\text{ for some $k$ in $\N$}. \end{equation*} Again, the usual properties can be proved (exercise; see~\cite{DPfnth}). Let's try to prove the WOP (the Well-Ordering Principle). Suppose $A\included\N$, and $A$ has no least element. We want to show that $A$ is empty, that is, $\N\setminus A=\N$. Try induction. For the base step, we cannot have ${0}\in A$, since then ${0}$ would be the least element of $A$. So ${0}\notin A$. For the inductive step, suppose $n\notin A$. This is not enough to establish $n+1\notin A$, since maybe $n-1\in A$, so $n+1$ can be in $A$ without being least. We need: \begin{theorem*}[Strong Induction] Suppose $A\included\N$, and for all $n$ in $\N$, if all predecessors of $n$ belong to $A$, then $n\in A$. Then $A=\N$. \end{theorem*} For the proof, see~\cite{DPfnth}. Now we can prove well-ordering: If $A$ has no least element, and no member of the set $\{x\in\N\colon xa_{1}\geq{0}$. By \emph{strong} recursion, define $a_{2}$, $a_{3}$,\dots by \begin{equation}\label{eqn:anq} a_n=a_{n+1}q+a_{n+{2}}\land {0}\leq a_{n+{2}}a_{1}>a_{2}>\dotsb \end{equation*} must stop. That is, let $a_m$ be the least element of $\{a_n\colon a_n>{0}\}$, so that $a_{m+1}={0}$. Then \begin{equation*} \gcd(a_{0},a_{1})=a_m; \end{equation*} why? Because, if $a_{n+1}\neq{0}$, then $\gcd(a_n,a_{n+1})=\gcd(a_{n+1},a_{n+{2}})$ by~\eqref{eqn:anq}; so, by induction, \begin{equation*} \gcd(a_{0},a_{1})=\gcd(a_{1},a_{2})=\dotsb=\gcd(a_m,a_{m+1})=\gcd(a_m,{0})=a_m. \end{equation*} \asterism{} A cock costs 5 L; a hen, 3 L; 3 chicks, 1 L. Can we buy 100 birds with 100 L? Let \begin{align*} x&=\#\text{ cocks,}\\ y&=\#\text{ hens,}\\ z&=\#\text{ chicks.} \end{align*} We want to solve \begin{equation}\label{eqn:sys} \begin{gathered} x+y+z=100,\\ 5x+{3}y+\frac13z=100. \end{gathered} \end{equation} Eliminate $z$ and proceed: \begin{gather}\notag z=100-x-y,\\\notag 15x+9y+z=300,\\\notag 15x+9y+100-x-y=300,\\\notag 14x+8y=200,\\\label{eqn:7x+4y=100} 7x+4y=100. \end{gather} Since $4\divides 100$, one solution is $({0},25)$, that is, $x={0}$ and $y=25$. Then $y=75$. So the answer to the original question is Yes. But can we include at least one cock? What are all the solutions? Think of linear algebra. If $(x_{0},y_{0})$ and $(x_{1},y_{1})$ are two solutions to~\eqref{eqn:7x+4y=100}, then \begin{gather*} 7x_{0}+4y_{0}=100,\\ 7x_{1}+4y_{1}=100,\\ 7(x_{1}-x_{0})+4(y_{1}-y_{0})={0}. \end{gather*} So we want to solve \begin{equation*} 7x+4y={0}. \end{equation*} Since $\gcd(7,4)={0}$, the solutions are $(4t,-7t)$. (Here is a difference with the usual linear algebra.) So the original system~\eqref{eqn:sys} has the general solution \begin{equation*} (x,y,z)=(4t,25-7t,75+{3}t). \end{equation*} If we want all entries to be positive, this means \begin{gather*} 4t>{0},\quad 25-7t>{0},\quad 75+{3}t>{0};\\ t>{0},\quad 7t<25,\quad {3}t>-75;\\ {0}1$ and \begin{equation*} a\divides p\lto\size a\in\{1,p\}. \end{equation*} Let $p$ and $q$ always stand for primes. Then \begin{equation*} \gcd(a,p)\in\{1,p\}, \end{equation*} so either $a$ and $p$ are co-prime, or else $p\divides a$. Suppose $p\divides ab$. Either $p\divides a$, or else $\gcd(a,p)=1$, so $p\divides b$ by Euclid's Lemma. Hence, by induction, if $p\divides a_{0}\dotsb a_n$, then $p\divides a_k$ for some $k$. Indeed, the claim is true when $n$ is ${0}$ or $1$. Suppose it is true when $n=m$. Say $p\divides a_{0}\dotsb a_{m+1}$. By the case $n=1$, we have that $p\divides a_{0}\dotsb a_m$ or $p\divides a_{m+1}$. In the former situation, by the inductive hypothesis, $p\divides a_k$ for some $k$. So the claim holds when $n=m+1$. \begin{theorem*}[Fundamental, of Arithmetic] Every positive integer is uniquely a product \begin{equation*} p_{1}\dotsb p_n \end{equation*} of primes, where \begin{equation*} p_{1}\leq\dotsb\leq p_n. \end{equation*} \end{theorem*} \begin{proof} Note that $1$ is such a product, where $n={0}$. Suppose $m>1$. Let $p_{1}$ be the least element of $\{x\in\N\colon x>1\land x\divides m\}$. Then $p_{1}$ must be prime; otherwise, if $a\divides p_{1}$, and $a>{0}$, but $a\notin\{1,p\}$, then $1\frac m{p_{1}}>\frac m{p_{1}p_{2}}>\dotsb \end{equation*} This must terminate in \begin{equation*} \frac m{p_{1}\dots p_n}=1 \end{equation*} by the Well-Ordering Principle, so that $m=p_{1}\dotsb p_n$. For uniqueness, suppose also $m=q_{1}\dotsb q_{\ell}$. Then $q_{1}\divides m$, so $q_{1}\divides p_i$ for some $i$, and therefore $q_{1}=p_i$. Hence \begin{equation*} p_{1}\leq p_i=q_{1}. \end{equation*} By the symmetry of the argument, $q_{1}\leq p_{1}$, so $p_{1}=q_{1}$. Similarly, $p_{2}=q_{2}$, \&c., and $n=\ell$. \end{proof} An analogous statement fails in some similar contexts. For example, \begin{equation*} (4+\rten)(4-\rten)=6={2}\cdot {3}; \end{equation*} but among the numbers $a+b\rten$, the numbers $4\pm\rten,{2},{3}$ are ``irreducible'' (like primes). Such matters are studied in \emph{algebraic} number theory. A positive non-prime number is \defn{composite}{} if it has prime factors. Then every positive number is uniquely prime, composite, or $1$. \asterism{} \begin{theorem*} The equation \begin{equation*} x^{2}={2}y^{2} \end{equation*} has no non-zero solution. \end{theorem*} \begin{proof} Suppose $a^{2}={2}b^{2}$. Then ${2}\divides a^{2}$, so ${2}\divides a$, so $4\divides a^{2}$, so $4\divides {2}b^{2}$, so ${2}\divides b^{2}$, so ${2}\divides b$. But if $a$ and $b$ are not ${0}$, then we may assume they are co-prime (otherwise, replace them with $a/d$ and $b/d$, where $d=\gcd(a,b)$). So $a$ and $b$ must be ${0}$. \end{proof} \asterism{} One can find primes with the Sieve of Eratosthenes\dots Eratosthenes also measured the circumference of the earth, by measuring the shadows cast by posts a certain distance apart in Egypt. Measuring \emph{this} distance must have needed teams of surveyors and a government to fund them. Columbus was not in a position to make the measurement again, so he had to rely on ancient measurements \cite{MR2038833}. \asterism{} \begin{theorem*}[Euclid, IX.20] If $n\in\N$, then there are more than $n$ primes. \end{theorem*} \begin{proof} Suppose $p_{0}<\dots{0}$, then $\{a+bn\colon n\in\N\}$ contains infinitely many primes. \end{theorem*} That is, arithmetic progressions (with the obvious condition\dots) contain infinitely many primes. The textbook \cite{Burton} omits the following. \begin{theorem*}[Ben Green and Terence Tao \cite{Green--Tao}, 2004] For every $n$, there are $a$ and $b$ such that each of the numbers $a, a+b, a+{2}b,\dots,a_nb$ is prime (and $b>{0}$). \end{theorem*} That is, there are arbitrarily long arithmetic progressions of primes. Is it possible that each of the numbers \begin{equation*} a,a+b,a+{2}b,a+{3}b,\dots \end{equation*} is prime? Yes, if $b={0}$. What if $b>{0}$? Then No, since $a\divides a+ab$. But what if $a=1$? Then replace $a$ with $a+b$. Two primes $p$ and $q$ are \defnplain{twin}{}\index{twin primes} if $\size{p-q}={2}$. The list of all primes begins: \begin{equation*} {2},\underbrace{{3},5,7}, \underbrace{11,13},\underbrace{17,19},23,\underbrace{29,31},37, \underbrace{41,43},47,\dots \end{equation*} and there are several twins. Are there infinitely many? People think so, but can't prove it. We do have: \begin{theorem*}[Goldston, Pintz, Y\i ld\i r\i m \cite{GPY}, 2005] For every positive real number $\epsilon$, there are primes~$p$ and~$q$ such that ${0}0$. But every positive integer is \emph{uniquely} a product $q_0{}^{f(0)}q_1{}^{f(1)}\dotsm q_{m-1}{}^{f(m-1)}$, by the Fundamental Theorem. Therefore \begin{equation*} \prod_{p\in\Pri}\frac1{1-\frac1p}=\sum_{n=1}^{\infty}\frac1n. \end{equation*} If $\Pri$ is infinite, then we must talk about convergence; but if $\Pri$ is finite, there is no problem. But the harmonic series $\sum_{n=1}^{\infty}\frac1n$ diverges: \begin{equation*} 1+\frac12 +\underbrace{\frac13+\frac14}_{\geq\frac12} +\underbrace{\frac15+\frac16+\frac17+\frac18}_{\geq\frac12}+\dotsb \end{equation*} Therefore $\Pri$ must be infinite. Using similar ideas, one can show that $\sum_{p\in\Pri}\frac1p$ diverges. \asterism{} Suppose $p\in\Pri$. If $p\divides ab$, but $p\ndivides a$, then $p\divides b$. If $p=ab$, but $p\ndivides a$, then $p\divides b$, but also $b\divides p$, so $b=\pm p$, and then $a=\pm1$. Among the integers, what property do $1$ and $-1$ have uniquely? They have multiplicative inverses: \begin{equation*} (-1)\cdot(-1)=1,\qquad 1\cdot 1=1, \end{equation*} but if $\size n>1$, then the equation $nx=1$ has no solution. In a word, $\pm1$ are \defn{unit}{s} in $\Z$. Then an integer $n$ is called \defn{irreducible}{} if \begin{enumerate} \item $n=ab\lto(\text{$a$ or $b$ is a unit})$; \item $n$ is not a unit. \end{enumerate} Then the irreducibles of $\Z$ are $\pm p$, where $p$ is prime. But irreducibility of primes is not enough to prove \emph{uniqueness} of prime factorizations. If \begin{equation*} p_1\dotsm p_m=q_1\dotsm q_n, \end{equation*} where $p_1\leq\dotsb p_m$ and $q_1\leq\dotsb q_m$, how do we know $p_1=q_1$, \&c.? We need the stronger property that $p\divides ab\lto(p\divides a\text{ or }p\divides b)$. Again, there is a situation where the stronger property fails for arbitrary irreducibles: \begin{equation*} (4+\rten)(4-\rten)=6=2\cdot3, \end{equation*} but $4\pm\rten$, $2$, and $3$ are irreducible in $\{x+y\rten\colon x,y\in\Z\}$, which is denoted by $\Z[\rten]$. Let $\sigma\colon\Z[\rten]\to\Z[\rten]$, where \begin{equation*} \sigma(a+b\rten)=a-b\rten. \end{equation*} (Compare this with complex conjugation.) Now define $N(x)=x\cdot\sigma(x)$, so that \begin{equation*} N(a+b\rten)=a^2-10b^2. \end{equation*} Then one can show $N(xy)=N(x)\cdot N(y)$. Also, $N(c)$ is always a square \emph{modulo} $10$. We have \begin{align*} 0^2&=0,\\ 1^2&=1,\\ 2^2&=4,\\ 3^2&=9\equiv-1\pmod{10},\\ 4^2&=16\equiv-4\pmod{10},\\ 5^2&=25\equiv5\pmod{10}, \end{align*} so $N(c)$ is congruent to $0$, $\pm1$, $\pm 4$ or $5$ \emph{modulo} $10$. \section{October 9, 2007 (Tuesday)} We have implicitly used that congruence respects arithmetic: If $a\equiv b\pmod n$ and $c\equiv d\pmod n$, then \begin{align*} a+c&\equiv b+d\pmod n,\\ a\cdot c&\equiv b\cdot d\pmod n. \end{align*} Indeed, we assume $n\divides b-a$ and $n\divides d-c$, so $n\divides b-a+d-c$, that is, \begin{equation*} n\divides b+d-(a+c), \end{equation*} which means $a+c\equiv b+d\pod n$; likewise, $n\divides(b-a)c+(d-c)b$, that is, $n\divides bd-ac$, so $ac\equiv bd\pod n$. In short, if set $\Z/(n)$ or $\Z_n$ of congruence-classes \emph{modulo} $n$ is a \defn{commutative ring}. Hence we can solve $35^{14}\equiv x\pod{43}$ as follows: First, $35\equiv-8\pod{43}$, so \begin{equation*} 35^{14}\equiv(-8)^{14}\equiv 8^{14}\pod{43}. \end{equation*} Also, $14=8+4+2=2^3+2^2+2^1$, so $8^{14}=8^8\cdot8^4\cdot8^2$; and \begin{gather*} 8^2=64\equiv21\pod{43},\\ 21^2=441\equiv11\pod{43},\\ 11^2=121\equiv35\equiv-8\pod{43}, \end{gather*} so that \begin{align*} 35^{14}&\equiv-8\cdot11\cdot21\pod{43}\\ &\equiv-88\cdot21\pod{43}\\ &\equiv-2\cdot21\pod{43}\\ &\equiv-44\equiv1\pod{43}. \end{align*} \asterism{} For another use of congruences, recall $\Z[\rten]=\{x+y\rten\colon x,y\in\Z\}$, closed under addition and multiplication; and \begin{align*} \sigma\colon\Z[\rten]&\longrightarrow\Z[\rten],\\ x+y\rten&\longmapsto x-y\rten, \end{align*} and \begin{align*} N\colon\Z[\rten]&\longrightarrow\Z,\\ x&\longmapsto x\cdot\sigma(x). \end{align*} Then $N(ab)=N(a)\cdot N(b)$. If $a$ is a unit (that is, invertible) of $\Z[\rten]$, then $ab=1$ for some $b$ in $\Z[\rten]$, so $N(ab)=N(1)$, that is, $N(a)\cdot N(b)=1$, so $N(a)=\pm1$. Conversely, if $N(a)=\pm1$, then $a\cdot(\pm\sigma(a))=1$, so $a$ is a unit. We observed \begin{equation*} (4+\rten)(4-\rten)=6=2\cdot3. \end{equation*} All of these factors are irreducible in $\Z[\rten]$. For example, if $2=ab$, then $N(2)=N(ab)$, that is, $4=N(a)\cdot N(b)$, so $N(a)\in\{\pm1,\pm2,\pm4\}$. But $N(a)$ is a square \emph{modulo} $10$, so $N(a)\equiv0,\pm1,\pm4,5\pod{10}$. Therefore one of $N(a)$ or $N(b)$ is $\pm1$, so it is a unit. \asterism{} \label{passage:division} If $a\equiv b\pod n$, then $ac\equiv bc\pod n$. But do we have the converse? We do if $c$ is invertible (is a unit) \emph{modulo} $n$. In that case, $cd\equiv1\pod n$ for some $d$, and then \begin{align*} ac\equiv bc\pmod n&\implies acd\equiv bcd\pmod n\\ &\implies a\equiv b\pmod n. \end{align*} Invertibility of $c$ \emph{modulo} $n$ is equivalent to solubility of $cx\equiv1\pod n$, or equivalently \begin{equation*} cx+ny=1. \end{equation*} Thus $c$ is invertible \emph{modulo} $n$ if and only if $c$ and $n$ are co-prime. Alternatively, if $ac\equiv bc\pod n$, and $c$ and $n$ are co-prime, then we can argue by Euclid's Lemma that, since $n\divides bc-ac$, that is, $n\divides(b-a)c$, we have $n\divides b-a$, that is, $a\equiv b\pod n$. Suppose we simply have $\gcd(c,n)=d$. Then $\gcd(c,n/d)=1$. Hence \begin{align*} ac\equiv bc\bmod n&\implies ac\equiv bc\bmod{\frac nd}\\ &\implies a\equiv b\bmod{\frac nd}. \end{align*} Conversely, \begin{align*} a\equiv b\bmod{\frac nd}&\implies\frac nd\divides b-a\\ &\implies\frac{cn}d\divides bc-ac\\ &\implies n\divides bc-ac\\ &\implies ac\equiv bc\bmod n. \end{align*} In short, \begin{equation*} ac\equiv bc\bmod n\Iff a\equiv b\bmod{\frac n{\gcd(c,n)}}. \end{equation*} For example, $6x\equiv 6\pod 9\Iff x\equiv 1\pod 3$. A longer problem is to solve \begin{equation}\label{eqn:70} 70x\equiv18\pod{134}. \end{equation} This reduces to \begin{equation*} 35x\equiv9\pod{67}, \end{equation*} or $35x+67y=9$. So there is a solution if and only if $\gcd(35,67)\divides9$. To \emph{find} the solutions, we should solve $35x+67y=1$, which we can do with the Euclidean Algorithm: \begin{align*} 67&=35\cdot1+32,\\ 35&=32\cdot1+3,\\ 32&=3\cdot10+2,\\ 3&=2\cdot1+1, \end{align*} so $\gcd(35,67)=1$. We now have \begin{align*} 32&=67-35,\\ 3&=35-32=35-(67-35)=35\cdot2-67,\\ 2&=32-3\cdot10=67-35-(35\cdot2-67)\cdot10=67\cdot11-35\cdot21,\\ 1&=3-2=35\cdot2-67-67\cdot11+35\cdot21=35\cdot23-67\cdot12. \end{align*} In particular, $35\cdot23\equiv1\pod{67}$, so~\eqref{eqn:70} is equivalent to \begin{align*} x&\equiv23\cdot9\pod{67}\\ &\equiv207\pod{67}\\ x&\equiv6\pod{67},\\ x&\equiv6,73\pod{134}. \end{align*} \asterism{} A puzzle from a recent newspaper [\emph{Guardian Weekly}] is mathematically the same as one attributed \cite[Prob.~4.4.8--9, p.~83]{Burton} to Brahmagupta (7th century \textsc{c.e.}): A man dreams he runs up a flight of stairs. If he takes the stairs 2, 3, 4, 5, or 6 at time, then one stair is left before the top. If he takes them 7 at a time, then he reaches the top exactly. How many stairs are there? If $x$ is that number, then \begin{align*} x&\equiv1\pmod{2,3,4,5,6},\\ x&\equiv0\pmod7. \end{align*} But $\lcm(2,3,4,5,6)=60$, so $x=60n+1$, where $7\divides 60n+1$. We have this when $n=5$, hence when $n=12,19,\dots$ The general problem is to solve systems \begin{equation}\label{eqn:crt} x\equiv a_0\bmod{n_0}\land x\equiv a_1\bmod{n_1}\land\dotsb\land x\equiv a_k\bmod{n_k}. \end{equation} Let's start with two congruences: \begin{equation}\label{eqn:xan} x\equiv a\bmod n\land x\equiv b\bmod m. \end{equation} A solution will take the form \begin{align*} x&=a+nu\\ &=mv+b. \end{align*} So we should like to make $a\equiv mv\pod n$ and $nu\equiv b\pod m$. We can do this if $\gcd(n,m)=1$. Then we have $nr\equiv1\pod m$ and $ms\equiv1\pod n$ for some $r$ and $s$, so that a solution to~\eqref{eqn:xan} is \begin{equation*} x=ams+bnr. \end{equation*} This solution is unique \emph{modulo} $\lcm(n,m)$, which is $nm$ since $\gcd(n,m)=1$. We can solve~\eqref{eqn:crt} similarly, under the assumption \begin{equation*} \gcd(n_i,n_j)=1 \end{equation*} whenever $i1$, then $m^n\equiv0\pmod{m^2}$, so $m\equiv0\pmod{m^2}$, which is absurd unless $m=\pm1$. \section{October 18, 2007 (Thursday)} Can we solve $(p-1)!\equiv x\pmod p$? The answer is certainly not $0$. \begin{theorem*} Suppose $n>1$. Then $(n-1)!\equiv-1\pmod n$ if and only if $n$ is prime. \end{theorem*} This is called `Wilson's Theorem,' though Wilson did not prove it. It was supposedly \cite{MR2135478} known to al-Haytham (964--1040). It gives a theoretical test for primality, though not a practical one. \begin{proof}[Proof of theorem] One of the two directions should be easier; which one? Suppose $n$ is not prime, so that $n=ab$, where $10$. \end{enumerate} Indeed, suppose $\gcd(a,p^r)\neq1$. Then $\gcd(a,p^r)=p^k$ for some positive $k$. In particular, $p\divides a$. Conversely, if $p\divides a$, then $p\divides\gcd(a,p^r)$, so $\gcd(a,p^r)\neq1$. Therefore $\phi(p^r)$ is the number of integers $x$ such that $0\leq x0;\\ \phi(mn)&=\phi(m)\cdot\phi(n),&&\text{ if }\gcd(m,n)=1. \end{align*} Hence, if $n$ has the distinct prime divisors $p_1$, \dots, $p_s$, then \begin{equation*} \phi(n)=n\cdot\prod_{k=1}^s\Bigl(1-\frac1{p_i}\Bigr). \end{equation*} We can write this more neatly as \begin{equation*} \phi(n)=n\cdot\prod_{p\divides n}\Bigl(1-\frac1p\Bigr). \end{equation*} For example, \begin{equation*} \phi(30)=30\cdot\Bigl(1-\frac12\Bigr)\cdot\Bigl(1-\frac13\Bigr)\cdot\Bigl(1-\frac15\Bigr)=30\cdot\frac12\cdot\frac23\cdot\frac45=8. \end{equation*} Since $180$ has the same prime divisors as $30$, we have \begin{equation*} \frac{\phi(180)}{\phi(30)}=\frac{180}{30}=6, \end{equation*} so $\phi(180)=6\phi(30)=48$. But $15$ and $30$ do not have the same prime divisors, and we cannot expect $\phi(15)/\phi(30)$ to be $15/30$, or $1/2$; indeed, $\phi(15)=\phi(3)\cdot\phi(5)=2\cdot 4=8=\phi(30)$. \begin{theorem*}[Euler] If $\gcd(a,n)=1$, then \begin{equation*} a^{\phi(n)}\equiv1\pmod n. \end{equation*} \end{theorem*} Fermat's Theorem is the special case when $n=p$. But we do \emph{not} generally have $a^{\phi(n)+1}\equiv a\pmod n$ for arbitrary $a$. For example, $\phi(12)=4$, but $2^5=32\equiv 8\pmod{12}$; so \begin{equation*} 2^{\phi(12)+1}\not\equiv2\pmod{12}. \end{equation*} \begin{proof}[Proof of Euler's Theorem] Assume $\gcd(a,n)=1$. We can write $\{x\in\Z\colon0\leq x1$, then the average member of $S_n$ is~$n/2$: \begin{equation*} \frac{\sum_{x\in S_n}x}{\phi(n)}=\frac n2. \end{equation*} Indeed, when $n>1$, then $S_n$ has the permutation $x\mapsto n-x$, so \begin{equation*} 2\cdot\sum_{x\in S_n}x =\sum_{x\in S_n}x+\sum_{x\in S_n}(n-x) =\sum_{x\in S_n}(x+(n-x)) =\sum_{x\in S_n}x=n\cdot\phi(n). \end{equation*} Therefore \begin{equation*} n>1\implies \sum_{x\in S_n}=\frac{n\cdot\phi(n)}2. \end{equation*} \section{November 8, 2007 (Thursday)} Recall Gauss's Theorem: \begin{equation}\label{eqn:sum-phi} \sum_{d\divides n}\phi(d)=n. \end{equation} We gave two proofs; each one exhibits some useful techniques. Let us make the tabular proof more precise. If $d\divides n$, let \begin{equation*} S_d^n=\{x\colon0\leq x0$), \emph{provided} we can show that \emph{every} solution to~\eqref{eqn:x^n-1} is on the list $a$, $a^2$, \dots, $a^n$. But this is a consequence of the following theorem. \end{proof} \section{November 22, 2007 (Thursday)} \begin{theorem*}[Lagrange] Every congruence of the form \begin{equation*} x^n+a_1x^{n-1}+\dotsb+a_{n-1}x+a_n\equiv0\pmod p \end{equation*} has $n$ solutions or fewer (\emph{modulo} $p$). \end{theorem*} \begin{proof} Use induction. The claim is trivially true when $n=0$. Suppose it is true when $n=k$. Say the congruence \begin{equation}\label{eqn:x^(k+1)} x^{k+1}+a_1x^k+\dotsb+a_kx+a_{k+1}\equiv0\pmod p \end{equation} has a solution $b$. Then we can factorize the left member, and rewrite the congruence as \begin{equation*} (x-a)\cdot(x^k+c_1x^{k-1}+\dotsb+c_{k-1}x+c_k)\equiv0\pmod p. \end{equation*} Any solution to this that is different from $a$ is a solution of \begin{equation*} x^k+c_1x^{k-1}+\dotsb+c_{k-1}x+c_k\equiv0\pmod p. \end{equation*} But by inductive hypothesis, there are at most $k$ such solutions. Therefore~\eqref{eqn:x^(k+1)} has at most $k+1$ solutions. This completes the induction and the proof. \end{proof} How did we use that $p$ is prime? We needed to know that, if $f(x)$ and $g(x)$ are polynomials, and $f(a)\cdot g(a)\equiv0\pmod p$, then either $f(a)\equiv0\pmod p$, or else $g(a)\equiv0\pmod p$. That is, if $mn\equiv0\pmod p$, then either $m\equiv0\pmod p$ or $n\equiv0\pmod p$. That is, if $p\divides mn$, then $p\divides m$ or $p\divides n$. This fails if $p$ is replaced by a composite number. From analysis, we have \begin{equation*} \exp\colon\R\to\units\R. \end{equation*} Here, $\units{\R}=\R\setminus\{0\}$ (the multiplicatively invertible real numbers), and $\exp(x+y)=\exp(x)\cdot\exp(y)$. The range of $\exp$ is $(0,\infty)$, which is closed under multiplication and inversion. So $\exp$ is an isomorphism from $(\R,+)$ onto $((0,\infty),{}\cdot{})$. We have been looking at a similar isomorphism in discrete mathematics. We have $\size{\Zmodu}=\phi(n)$. A primitive root of $n$, if it exists, is a generator of the multiplicative group $\Zmodu$. In particular: \begin{enumerate} \item $\Zmodu[2]=\{1\}$, so $1$ is a primitive root of $2$. \item $\Zmodu[3]=\{1,2\}$, and $2^2\equiv1\pmod3$, so $2$ is a primitive root of $3$. \item $\Zmodu[4]=\{1,3\}$, and $3^2\equiv1\pmod4$, so $3$ is a primitive root of $4$. \item $\Zmodu[5]=\{1,2,3,4\}$, and $2^2\equiv4$, $2^3\equiv3$, and $2^4\equiv1\pmod 5$, so $2$ is a primitive root of $5$. \item $\Zmodu[6]=\{1,5\}$, and $5^2\equiv1\pmod6$, so $5$ is a primitive root of $6$. \item $\Zmodu[7]=\{1,2,3,4,5,6\}$, and we have \begin{equation*} \begin{array}{|c*{6}{|r}|}\hline k &1&2&3&4&5&6\\\hline 2^k&2&4&1& & & \\\hline 3^k&3&2&6&4&5&1\\\hline \end{array} \end{equation*} so $3$ (but not $2$) is a primitive root of $7$. \item $\Zmodu[8]=\{1,3,5,7\}$, but $3^2\equiv1$, $5^2\equiv1$, and $7^2\equiv1\pmod 8$, so $8$ has no primitive root. \end{enumerate} We have shown that primes have primitive roots, but the converse fails: not every number with a primitive root is prime. In fact, the following numbers have primitive roots: \begin{enumerate} \item powers of odd primes; \item $2$ and $4$; \item doubles of powers of odd primes. \end{enumerate} %\section{November 27, 2007 (Tuesday)} %[Exam day; I work problems only.] \section{November 29, 2007 (Thursday)} \emph{Modulo} $17$, we have \begin{equation*} \begin{array}{*{17}{|r}|}\hline k&0&1&2& 3& 4&5& 6& 7& 8& 9&10&11&12&13&14&15\\\hline 3^k&1&3&9&10&13&5&15&11&16&14& 8& 7& 4&12& 2& 6\\\hline \end{array} \end{equation*} Reordering, we have \begin{equation*} \begin{array}{*{17}{|r}|}\hline 3^k&1& 2&3& 4&5& 6& 7& 8&9&10&11&12&13&14&15&16\\\hline k&0&14&1&12&5&15&11&10&2& 3& 7&13& 4& 9& 6& 8\\\hline \end{array} \end{equation*} If $3^k=\ell$, then we can denote $k$ by $\log_3\ell$. But we can think of these numbers as congruence-classes: \begin{equation*} 3^k\equiv\ell\pmod{17}\Iff k\equiv\log_3\ell\pmod{16}. \end{equation*} The usual properties hold: \begin{equation*} \log_3(xy)\equiv\log_3x+\log_3y\pmod{16}; \qquad\log_3{x^n}\equiv n\log_3x\pmod{16}. \end{equation*} For example, \begin{equation*} \log_3(11\cdot 14)\equiv\log_311+\log_314\equiv7+9\equiv16\equiv0\pmod{16}, \end{equation*} and therefore $11\cdot17\equiv3^0\equiv1\pmod{17}$. In general, the base of logarithms will be a primitive root. If $b$ is a primitive root of $n$, and $\gcd(a,n)=1$, then there is some $s$ such that \begin{equation*} b^s\equiv a\pmod n. \end{equation*} Then $s$ is unique \emph{modulo} $\phi(n)$. Indeed, recall that \begin{equation*} b^x\equiv b^y\pmod n\Iff x\equiv y\pmod{\phi(n)}. \end{equation*} The least non-negative such $s$ is defined to be $\log_ba$, \emph{modulo} $n$. Another application of logarithms, besides multiplication problems, is congruences of the form \begin{equation*} x^d\equiv a\pmod n. \end{equation*} This is equivalent to \begin{gather*} \log_bx^d\equiv\log_ba\pmod{\phi(n)},\\ d\log_bx\equiv\log_ba\pmod{\phi(n)}. \end{gather*} If this is to have a solution, then we must have \begin{equation*} \gcd(d,\phi(n))\divides \log_ba. \end{equation*} For example, let's work \emph{modulo} $7$: \begin{equation*} \begin{array}{*{7}{|r}|}\hline k&0&1&2&3&4&5\\\hline 3^k&1&3&2&6&4&5\\\hline \end{array} \quad \begin{array}{*{7}{|r}|}\hline \ell&1&2&3&4&5&6\\\hline \log_3\ell&0&2&1&4&5&3\\\hline \end{array} \end{equation*} Then we have, for example, \begin{equation*} x^3\equiv2\pmod7 \Iff3\log_3x\equiv2\pmod6, \end{equation*} so there is no solution, since $\gcd(3,6)=3$, and $3\ndivides 2$. But we also have \begin{align*} x^3\equiv6\pmod7 &\Iff3\log_3x\equiv3\pmod6\\ &\Iff\log_3x\equiv1\pmod2\\ &\Iff\log_3x\equiv1,3,5\pmod6\\ &\Iff x\equiv 3^1,3^3,3^5\pmod7\\ &\Iff x\equiv3,6,5\pmod7. \end{align*} We expect no more than $3$ solutions, by the Lagrange's Theorem. Is there an alternative to using logarithms? As $6\equiv3^3\pmod7$, we have \begin{equation*} x^3\equiv6\pmod7\Iff x^3\equiv3^3\pmod7; \end{equation*} but we cannot conclude from this $x\equiv3\pmod7$. \section{December 4, 2007 (Tuesday)} For congruences \emph{modulo} $11$, we can use the following table: \begin{equation*} \begin{array}{*{11}{|r}|l|}\hline k& 1& 2& 3& 4& 5& 6& 7& 8& 9&10&\log_2\ell\pmod{10}\\\hline 2^k\pmod{11}& 2& 4&-3& 5&-1&-2&-4& 3&-5& 1&\ell\\\hline \end{array} \end{equation*} We have then \begin{align*} 4x^{15}\equiv7\pmod{11} &\Iff4x^5\equiv7\pmod{11}\\ &\Iff\log_2(4x^5)\equiv\log_27\pmod{10}\\ &\Iff\log_24+5\log_2x\equiv\log_27\pmod{10}\\ &\Iff2+5\log_2x\equiv7\pmod{10}\\ &\Iff5\log_2x\equiv5\pmod{10}\\ &\Iff\log_2x\equiv1\pmod{2}\\ &\Iff\log_2x\equiv1,3,5,7,9\pmod{10}\\ &\Iff x\equiv 2^1,2^3,2^5,2^7,2^9\pmod{11}\\ &\Iff x\equiv2,8,10,7,6\pmod{11}. \end{align*} Why are there five solutions? \begin{theorem*} Suppose $n$ has a primitive root $r$, so that logarithms with base $r$ are defined. (So $a\equiv r^b\pmod{n}$ if and only if $\log_ra\equiv b\pmod{\phi(n)}$, when $\gcd(a,n)=1$.) Assume $\gcd(a,n)=1$. Let $d=\gcd(k,\phi(n))$. Then the following are equivalent: \begin{enumerate} \item\label{item:x^k} The congruence $x^k\equiv a\pmod n$ is soluble. \item\label{item:d} The congruence has $d$ solutions. \item\label{item:a^phi} $a^{\phi(n)/d}\equiv1\pmod n$. \end{enumerate} \end{theorem*} \begin{proof} The following are equivalent: \begin{gather*} x^k\equiv a\pmod n\text{ is soluble};\\ k\log x\equiv a\pmod{\phi(n)}\text{ if soluble};\\ d\divides\log a;\\ \phi(n)\divides\frac{\phi(n)}d\cdot\log a;\\ \frac{\phi(n)}d\cdot\log a\equiv0\pmod{\phi(n)};\\ \log a^{\phi(n)/d}\equiv0\pmod{\phi(n)};\\ a^{\phi(n)/d}\equiv1\pmod n. \end{gather*} Thus~\eqref{item:x^k}$\Iff$\eqref{item:a^phi}. Trivially,~\eqref{item:d}$\implies$\eqref{item:x^k}. Finally, assume~\eqref{item:x^k}, so that $d\divides\log a$, as above. Then \begin{align*} x^k\equiv a\pmod n &\Iff k\log x\equiv\log a\pmod{\phi(n)}\\ &\Iff\frac kd\cdot\log x\equiv\frac{\log a}d\pmod{\frac{\phi(n)}d}\\ &\Iff\log x\equiv\frac{\log a}k\pmod{\frac{\phi(n)}d}\\ &\Iff\begin{aligned}[t] \log x&\equiv\frac{\log a}k+\frac{\phi(n)}d\cdot j\pmod{\phi(n)},\\ & \text{ where }j\in\{0,1,\dots,d-1\} \end{aligned}\\ &\Iff \begin{aligned}[t] x&\equiv r^{(\log a)/k}\cdot(r^{\phi(n)/d})^j\pmod n,\\ &\text{ where }j\in\{0,1,\dots,d-1\}. \end{aligned} \end{align*} These $d$ solutions are incongruent, as $\ord nr=\phi(n)$. \end{proof} \asterism{} We know that all primes have primitive roots. Now we show that the numbers with primitive roots are precisely: \begin{equation*} 2,4,p^s,2\cdot p^s, \end{equation*} where $p$ is an odd prime, and $s\geq1$. We shall first show that the numbers \emph{not} on this list do \emph{not} have primitive roots: \begin{lemma*} If $k>2$, then $2\divides\phi(k)$. \end{lemma*} \begin{proof} Suppose $k>2$. Then either $k=2^s$, where $s>1$, or else $k=p^s\cdot m$ for some odd prime $p$, where $s>0$ and $\gcd(p,m)=1$. In the first case, $\phi(k)=2^s-2^{s-1}=2^{s-1}$, which is even. In the second case, $\phi(k)=\phi(p^s)\cdot\phi(m)$, which is even, since $\phi(p^s)=p^s-p^{s-1}$, the difference of two odd numbers. \end{proof} \begin{theorem*} If $m$ and $n$ are co-prime, both greater than $2$, then $mn$ has no primitive root. \end{theorem*} \begin{proof} Suppose $\gcd(a,mn)=1$. (This is the only possibility for a primitive root.) Then $a$ is prime to $m$ and $n$, so \begin{gather*} a^{\phi(m)}\equiv 1\pmod m;\qquad a^{\phi(n)}\equiv 1\pmod n;\\ a^{\lcm(\phi(m),\phi(n))}\equiv 1\pmod{m,n},\\ a^{\lcm(\phi(m),\phi(n))}\equiv 1\pmod{\lcm(m,n)},\\ a^{\lcm(\phi(m),\phi(n))}\equiv 1\pmod{mn}. \end{gather*} By the lemma, $2$ divides both $\phi(m)$ and $\phi(n)$, so \begin{equation*} \lcm(\phi(m),\phi(n))\divides\frac{\phi(m)\phi(n)}2, \end{equation*} that is, $\lcm(\phi(m),\phi(n))\divides\phi(mn)/2$. Therefore \begin{equation*} \ord{mn}a\leq\frac{\phi(mn)}2, \end{equation*} so $a$ is not a primitive root of $mn$. \end{proof} \begin{theorem*} If $k\geq0$, then $2^{3+k}$ has no primitive root. \end{theorem*} \begin{proof} Any primitive root of $2^{3+k}$ must be odd. Let $a$ be odd. We shall show by induction that \begin{equation*} a^{\phi(2^{3+k})/2}\equiv1\pmod{2^{3+k}}. \end{equation*} This means, since $\phi(2^{3+k})=2^{3+k}-2^{2+k}=2^{2+k}$, that we shall show \begin{equation*} a^{2^{1+k}}\equiv1\pmod{2^{3+k}}. \end{equation*} The claim is true when $k=0$, since $a^2\equiv1\pmod8$ for all odd numbers $a$. Suppose the claim is true when $k=\ell$: that is, \begin{equation*} a^{2^{1+\ell}}\equiv1\pmod{2^{3+\ell}}. \end{equation*} This means \begin{equation*} a^{2^{1+\ell}}=1+2^{3+\ell}\cdot m \end{equation*} for some $m$. Now square: \begin{equation*} a^{2^{2+\ell}} =(a^{2^{1+\ell}})^2 =(1+2^{3+\ell}\cdot m)^2=1+2^{4+\ell}\cdot m+2^{6+2\ell}\cdot m^2. \end{equation*} Hence $a^{2^{2+\ell}}\equiv1\pmod{2^{4+\ell}}$, that is, \begin{equation*} a^{2^{1+(\ell+1)}}\equiv1\pmod{2^{3+(\ell+1)}}; \end{equation*} so our claim is true when $k=\ell+1$. This completes the induction and the proof. \end{proof} Now for the positive results. These will use the following. \begin{lemma*} Let $r$ be a primitive root of $p$, and $k>0$. Then \begin{equation*} \ord{p^k}r=(p-1)p^{\ell} \end{equation*} for some $\ell$, where $0\leq\ell2$, so that $p\divides\binom p2$, we have \begin{align*} r^{(p-1)\cdot p^{\ell+1}} &\equiv1+p^{1+(\ell+1)}\cdot m\pmod{p^{2+(\ell+1)}}\\ &\not\equiv 1\pmod{p^{2+(\ell+1)}}. \end{align*} Therefore we must have \begin{equation*} \ord{p^{2+(\ell+1)}}r=(p-1)\cdot p^{1+(\ell+1)}=\phi(p^{2+(\ell+1)}), \end{equation*} which means $r$ is a primitive root of $p^{2+(\ell+1)}$. \end{proof} It remains to show that $2\cdot p^s$ also has a primitive root. \section{December 6, 2007 (Thursday)} If $\gcd(r,n)=1$, then the following are equivalent: \begin{enumerate} \item $r$ is a primitive root of $n$; \item $\ord nr=\phi(n)$; \item if $\gcd(a,n)=1$, then $a\equiv r^b\pmod n$ for some $b$. \end{enumerate} We have shown: \begin{enumerate} \item Every prime $p$ has a primitive root, $r$; \item either $r$ or $r+p$ is a primitive root of $p^2$; \item if $p$ is odd, then every primitive root of $p^2$ is a primitive root of $p^{2+k}$. \end{enumerate} For example, $3$ has the primitive root $2$, since $2\not\equiv1\pmod3$, but $2^2\equiv1\pmod3$. Hence, either $2$ or $5$ is a primitive root of $9$. In fact, both are. Using $5\equiv-4\pmod9$, we have: \begin{equation*} \begin{array}{|c*{3}{|r}|l|}\hline k&1&2&3&6=\phi(9)\\\hline 2^k\pmod9&2&4&-1&1\\\hline (-4)^k\pmod9&-4&-2&-1&1\\\hline \end{array} \end{equation*} Therefore $2$ and $-4$ must be primitive roots of $27$, and indeed \begin{equation*} \begin{array}{|c*{9}{|r}|l|}\hline k&1&2&3&4&5&6&7&8&9&18=\phi(27)\\\hline 2^k\pmod{27}&2&4&8&-11&5&10&-7&13&-1&1\\\hline (-4)^k\pmod{27}&-4&-11&-10&13&2&-8&5&7&-1&1\\\hline \end{array} \end{equation*} But does $18$ have a primitive root? We have \begin{equation*} \begin{array}{|c*{7}{|r}|}\hline k&1&2&3&4&5&6&7\\\hline (-4)^k&-4&-2&8&4&2&-8&-4\\\hline 5^k&5&7&-1&-5&-7&1&5\\\hline \end{array} \end{equation*} The powers of $-4$ and $5$ cycle through six numbers in each case. Corresponding powers differ by $9$: Since $-4\equiv5\pmod9$, we have $(-4)^k\equiv5^k\pmod9$. But the powers of $-4$ are not prime to $18$, so $-4$ is not a primitive root of $18$. However, $5$ is. \begin{theorem*} If $p$ is an odd prime, and $r$ is a primitive root of $p^s$, then either $r$ or $r+p^s$ is a primitive root of $2p^s$---whichever one is odd. \end{theorem*} \begin{proof} Let $r$ be an odd primitive root of $p^s$, so that $\gcd(r,2p^s)=1$. Let $n=\ord{2p^s}r$. We want to show $n=\phi(2p^s)$. We have \begin{equation*} n\divides\phi(2p^s). \end{equation*} Also $r^n\equiv1\pmod{2p^s}$, so $r^n\equiv1\pmod{p^s}$, and therefore \begin{equation*} \ord{p^s}r\divides n. \end{equation*} But $\ord{p^s}r=\phi(p^s)=\phi(2p^s)$. Hence \begin{equation*} \phi(2p^s)\divides n. \end{equation*} So $n=\phi(2p^s)$. \end{proof} \asterism{} Now we return to high-school-like problems. For example, how can we solve \begin{equation*} x^2-4x-1\equiv0\pmod{11}? \end{equation*} \emph{Modulo} $11$, we have $x^2-4x-1\equiv x^2-4x-12\equiv(x-6)(x+2)$, so the solutions are $6$ and $-2$, or rather $6$ and $9$. Alternatively, $x^2-4x-1\equiv x^2+7x+10\equiv(x+5)(x+2)$, so $x$ is $-5$ or $-2$, that is, $6$ or $9$ again. To solve \begin{equation*} 3x^2-4x-6\equiv0\pmod{13}, \end{equation*} we can search for a factorization as before; but we can also \defn{complete the square}: \begin{align*} 3x^2-4x-6\equiv0 &\Iff x^2-\frac43x-2\equiv0\\ &\Iff x^2-\frac43x+\frac49\equiv2+\frac49\\ &\Iff\Bigl(x-\frac23\Bigr)^2\equiv\frac{22}9\equiv1\\ &\Iff x-\frac23\equiv\pm1\\ &\Iff x\equiv\frac23\pm1\\ &\Iff x\equiv\frac53\text{ or }\frac{-1}3\\ &\Iff x\equiv6\text{ or }4. \end{align*} Here we can divide by $3$ because it is invertible \emph{modulo} $13$; indeed, $3\cdot9\equiv1\pmod{13}$, so $1/3\equiv9\pmod{13}$. If we take this approach with the first problem, we have, \emph{modulo} $11$, \begin{align*} x^2-4x-1\equiv0 &\Iff x^2-4x+4\equiv5\\ &\Iff(x-2)^2\equiv5. \end{align*} If $5$ is a square \emph{modulo} $11$, then there is a solution; if not, not. But $5\equiv16\equiv4^2$, so we have \begin{align*} x^2-4x-1\equiv0 &\Iff(x-2)^2\equiv4^2\\ &\Iff x-2\equiv\pm4\\ &\Iff x\equiv 2\pm 4\\ &\Iff x\equiv 6\text{ or }9, \end{align*} as before. But the congruence \begin{equation*} x^2\equiv5\pmod{13} \end{equation*} has no solution. How do we know? One way is by trial. As $2$ is a primitive root of~$13$, and $0$ is not a solution of the congruence, every solution would be a power of $2$. But we have, \emph{modulo} $13$, \begin{equation*} \begin{array}{*{13}{|r}|}\hline k&1&2&3&4&5&6&7&8&9&10&11&12\\\hline 2^k&2&4&-5&3&6&-1&-2&-4&5&-3&-6&1\\\hline 2^{2k}&4&3&-1&-4&-3&1&4&3&-1&-4&-3&1\\\hline \end{array} \end{equation*} and $5$ does not appear on the bottom row. In general, if $p\ndivides a$, we say $a$ is a \defn{quadratic residue}{} of $p$ if the congruence \begin{equation*} x^2\equiv a\pmod p \end{equation*} is soluble; otherwise, $a$ is a \defn{quadratic non-residue}{} of $p$. So we have just seen that the quadratic residues of $13$ are $\pm1$, $\pm 3$, and $\pm4$, or rather $1$, $3$, $4$, $9$, $10$, and $12$; the quadratic non-residues are $2$, $5$, $6$, $7$, $8$, and $11$. So there are six residues, and six non-residues. \begin{theorem*}[Euler's Criterion] Let $p$ be an odd prime, and $\gcd(a,p)=1$. Then $a$ is a quadratic residue of $p$ if and only if \begin{equation*} a^{(p-1)/2}\equiv1\pmod p. \end{equation*} \end{theorem*} \begin{proof} Let $r$ be a primitive root of $p$. If $x^2\equiv a\pmod p$ has a solution, then that solution is $r^k$ for some $k$. Then \begin{equation*} a^{(p-1)/2}\equiv((r^k)^2)^{(p-1)/2}\equiv(r^k)^{p-1}\equiv1\pmod{p} \end{equation*} by Euler's Theorem. In any case, $a\equiv r^{\ell}\pmod p$ for some $\ell$. Suppose $a^{(p-1)/2}\equiv1\pmod p$. Then \begin{equation*} 1\equiv(r^{\ell})^{(p-1)/2}\equiv r^{\ell\cdot(p-1)/2}\pmod p, \end{equation*} so $\ord pr\divides \ell\cdot(p-1)/2$, that is, \begin{equation*} p-1\divides\ell\cdot\frac{p-1}2. \end{equation*} Therefore $\ell/2$ is an integer, that is, $\ell$ is even. Say $\ell=2m$. Then $a\equiv r^{2m}\equiv(r^m)^2\pmod p$. \end{proof} \section{December 11, 2007 (Tuesday)} Henceforth $p$ is an odd prime, and $\gcd(a,p)=1$. We have defined quadratic residues and non-residues of $p$, and we have established Euler's Criterion: $a$ is a quadratic residue of $p$ if and only if $a^{(p-1)/2}\equiv1\pmod p$. What other congruence-class can $a^{(p-1)/2}$ belong to, besides $1$? Only $-1$, since $a^{p-1}\equiv1\pmod p$, by Euler's Theorem. So $a^{(p-1)/2}\equiv-1\pmod p$ if and only if $a$ is a quadratic non-residue of $p$. Another way to prove this is the following: Suppose $a$ is a quadratic non-residue of $p$. If $b\in\{1,\dots,p-1\}$, then the congruence \begin{equation*} bx\equiv a\pmod p \end{equation*} has a unique solution in $\{1,\dots,p-1\}$, and we may denote the solution by $a/b$. Then $b\neq a/b$, since $a$ is not a quadratic residue of $p$. Now we define a sequence $(b_1,\dots,b_{p-1})$ recursively. If $b_k$ has been chosen when $k<\ell2$. With these properties, we can calculate many Legendre symbols. For example, \begin{gather*} \ls{50}{19}=\ls{12}{19}=\ls2{19}^2\ls3{19}=\ls3{19},\\ 3^{(19-1)/2}\equiv 3^9\equiv 3^8\cdot3\equiv 9^4\cdot 3\equiv 81^2\cdot 3\equiv5^2\cdot 3\equiv6\cdot3\equiv 18\equiv-1\pmod{19}, \end{gather*} so $(50/19)=-1$, which means the congruence $x^2\equiv50\pmod{19}$ has no solution. \asterism{} \begin{theorem*} There are infinitely many primes $p$ such that $p\equiv3\pmod 4$. \end{theorem*} \begin{proof} Suppose $(q_1,q_2,\dots,q_n)$ is a list of primes. We shall prove that there is a prime $p$, not on this list, such that $p\equiv3\pmod 4$. Let \begin{equation*} s=4q_1\cdot q_2\dotsm q_n-1. \end{equation*} Then $s\equiv3\pmod 4$. Then $s$ must have a prime factor $p$ such that $p\equiv 3\pmod 4$. Indeed, if all prime factors of $s$ are congruent to $1$, then so must $s$ be. But $p$ is not any of the $q_k$. \end{proof} This argument fails when $3$ is replaced by $1$, since $3^2\equiv1\pmod4$. Nonetheless, we still have: \begin{theorem*} There are infinitely many primes $p$ such that $p\equiv1\pmod 4$. \end{theorem*} \begin{proof} Suppose $(q_1,q_2,\dots,q_n)$ is a list of primes. We shall prove that there is a prime $p$, not on this list, such that $p\equiv1\pmod 4$. Let \begin{equation*} s=2q_1\cdot q_2\dotsm q_n. \end{equation*} Then $s^2+1$ is odd, so it is divisible by some odd prime $p$. Consequently, $s$ is a solution of the congruence $x^2\equiv-1\pmod p$. This means $(-1/p)=1$, so $p\equiv 1\pmod 4$, by~\eqref{item:cases} above. \end{proof} \asterism{} \begin{theorem*} $\displaystyle\sum_{k=1}^{p-1}\ls kp=0$. \end{theorem*} \begin{proof} Let $r$ be a primitive root of $p$. Then \begin{equation*} \sum_{k=1}^{p-1}\ls kp =\sum_{k=1}^{p-1}\ls{r^k}p =\sum_{k=1}^{p-1}\ls rp^k =\sum_{k=1}^{p-1}(-1)^k=0, \end{equation*} since $r^{(p-1)/2}\equiv-1\pmod p$, since $r$ is a primitive root. \end{proof} \asterism{} \begin{lemma*}[Gauss] Let $p$ be an odd prime, and $\gcd(a,p)=1$. Then \begin{equation*} \ls ap=(-1)^n, \end{equation*} where $n$ is the number of elements of the set \begin{equation*} \bigl\{a,2a,3a,\dots,\frac{p-1}2a\bigr\} \end{equation*} whose remainders after division by $p$ are greater than $p/2$. \end{lemma*} For example, to find $(3/19)$, we can look at \begin{equation*} 3,\; 6,\; 9,\; 12,\; 15,\; 18,\; 21,\; 24,\; 27, \end{equation*} whose remainders on division by $19$ are, respectively, \begin{equation*} 3,\; 6,\; 9,\; 12,\; 15,\; 18,\; 2,\; 5,\; 8. \end{equation*} Of those, $12$, $15$, and $18$ exceed $19/2$, and these are three; so \begin{equation*} \ls3{19}=(-1)^3=-1. \end{equation*} \begin{proof}[Proof of Gauss's Lemma] If $1\leq k\leq p-1$, let $b_k$ be such that \begin{gather*} 1\leq b_k\leq p-1,\\ ka\equiv b_k\pmod p. \end{gather*} Then $\{1,2,\dots,p-1\}=\{b_1,b_2,\dots,b_{p-1}\}$, because the $b_k$ are distinct: \begin{equation*} b_k=b_{\ell}\Iff ka\equiv\ell a\Iff k\equiv\ell. \end{equation*} In the set $\{b_1,b_2,\dots,b_{(p-1)/2}\}$, let $n$ be the number of elements that are greater than $p/2$. We want to show \begin{equation*} (-1)^n=\ls ap. \end{equation*} There is some permutation $\sigma$ of $\{1,2,\dots,(p-1)/2\}$ such that \begin{equation*} b_{\sigma(1)}>b_{\sigma(2)}>\dotsb>b_{\sigma(n)}>\frac p2>b_{\sigma(n+1)}>\dotsb >b_{\sigma((p-1)/2)}. \end{equation*} Observe now that \begin{equation*} b_{p-k}=p-b_k; \end{equation*} indeed, both numbers are in $\{1,2,\dots,p-1\}$, and \begin{equation*} b_{p-k}\equiv(p-k)a\equiv-ka\equiv-b_k\equiv p-b_k\pmod p. \end{equation*} In particular, if $1\leq k\leq(p-1)/2$, then $p-b_k\notin\{b_1,b_2,\dots,b_{(p-1)/2}\}$. Therefore \begin{equation*} \{p-b_{\sigma(1)},p-b_{\sigma(2)},\dotsc,p-b_{\sigma(n)}, b_{\sigma(n+1)},\dotsc b_{\sigma((p-1)/2)}\}=\Bigl\{1,2,\dots,\frac{p-1}2\Bigr\}. \end{equation*} Now take products: \begin{align*} \frac{p-1}2! &\equiv(p-b_{\sigma(1)})(p-b_{\sigma(2)})\dotsm(p-b_{\sigma(n)}) b_{\sigma(n+1)}\dotsm b_{\sigma((p-1)/2)}\\ &\equiv(-1)^n\cdot b_{\sigma(1)}\dotsm b_{\sigma((p-1)/2)}\\ &\equiv(-1)^n\cdot b_1\dotsm b_{(p-1)/2}\\ &\equiv(-1)^n\cdot a\cdot2a\cdot3a\dotsm\frac{p-1}2a\\ &\equiv(-1)^n\cdot\frac{p-1}2!\cdot a^{(p-1)/2}\pmod p. \end{align*} Therefore, since $p\ndivides((p-1)/2)!$, we have \begin{equation*} 1\equiv(-1)^n\cdot a^{(p-1)/2}\equiv(-1)^n\cdot(a/p)\pmod p. \end{equation*} As both $(-1)^n$ and $(a/p)$ are $\pm1$, the claim follows. \end{proof} We shall use Gauss's Lemma to prove the Law of Quadratic Reciprocity, by which we shall be able to relate $(p/q)$ and $(q/p)$ when both $p$ and $q$ are odd primes. Meanwhile, besides the direct application of Gauss's Lemma to computing Legendre symbols, we have: \begin{theorem*} If $p$ is an odd prime, then \begin{equation*} \ls2p= \begin{cases} 1,&\text{ if }p\equiv\pm1\pmod 8;\\ -1,&\text{ if }p\equiv\pm3\pmod 8. \end{cases} \end{equation*} \end{theorem*} \begin{proof} To apply Gauss's Lemma, we look at the numbers \begin{equation*} 2\cdot1,\;2\cdot2,\;\dotsc,\; 2\cdot\frac{p-1}2. \end{equation*} Each is its own remainder on division by $p$. Hence $(2/p)=(-1)^n$, where $n$ is the number of integers $k$ such that \begin{equation*} \frac p2<2k\leq p-1, \end{equation*} or rather $p/4\dotsb>b_{\sigma(n)}>\frac p2>b_{\sigma(n+1)}>\dotsb b_{\sigma((p-1)/2)}, \end{equation*} and we showed $(a/p)=(-1)^n$ after first showing \begin{equation*} \Bigl\{1,2,\dots,\frac{p-1}2\Bigr\}= \{p-b_{\sigma(1)},\dotsc,p-b_{\sigma(n)}, b_{\sigma(n+1)},\dotsc b_{\sigma((p-1)/2)}\}. \end{equation*} Now take sums: \begin{equation*} \sum_{k=1}^{(p-1)/2}k=\sum_{k=1}^n(p-b_{\sigma(k)})+ \sum_{\ell=n+1}^{(p-1)/2}b_{\sigma(\ell)}. \end{equation*} Subtracting this from~\eqref{eqn:G} (and using that $\sum_{k=1}^{(p-1)/2}b_{\sigma(k)}= \sum_{k=1}^{(p-1)/2}b_k$) gives \begin{equation*} (a-1)\cdot\sum_{k=1}^{(p-1)/2}k =p\cdot\Bigl(\sum_{k=1}^n\left[\frac{ka}p\right]-n\Bigr) + 2\cdot\sum_{k=1}^nb_{\sigma(k)}. \end{equation*} Since $a-1$ is even, but $p$ is odd, we conclude \begin{equation*} \sum_{k=1}^n\left[\frac{ka}p\right]\equiv n\pmod 2, \end{equation*} which yields the claim. \end{proof} \section{December 18, 2007 (Tuesday)} A \defn{Germain prime}{} (named for Sophie Germain, 1776--1831) is an odd prime $p$ such that $2p+1$ is also prime. We showed that, if $p$ is a Germain prime, then $2p+1$ has the primitive root $(-1)^{(p-1)/2}\cdot2$. (However, it is not known whether there infinitely many Germain primes.) We used that \begin{equation*} \ls2p= \begin{cases} 1,&\text{ if }p\equiv\pm1\pmod 8;\\ -1,&\text{ if }p\equiv\pm3\pmod 8. \end{cases} \end{equation*} Another consequence of this formula is: \begin{theorem*} There are infinitely many primes congruent to $-1$ \emph{modulo} $8$. \end{theorem*} \begin{proof} Let $q_1$, \dots, $q_n$ be a finite list of primes. We show that there is $p$ not on the list such that $p\equiv-1\pmod8$. Let \begin{equation*} M=(4q_1\dotsm q_n)^2-2. \end{equation*} Then $M\equiv-2\pmod{16}$, so $M$ is not a power of $2$; in particular, $M$ has odd prime divisors. Also, for every odd prime divisor $p$ of $M$, we have \begin{equation*} (4q_1\dotsm q_n)^2\equiv2\pmod p, \end{equation*} so $(2/p)=1$, and therefore $p\equiv\pm1\pmod 8$. Since $M/2\equiv-1\pmod8$, we conclude that not every odd prime divisor of $M$ can be congruent to $1$ \emph{modulo}~$8$. \end{proof} Finally, for the proof of Quadratic Reciprocity, we showed that, if $p$ is an odd prime, $p\ndivides a$, and $a$ is odd, then \begin{equation*} \ls ap=(-1)^n,\quad\text{ where }\quad n=\sum_{k=1}^{(p-1)/2}\left[\frac{ka}p\right]. \end{equation*} Now we can establish: \begin{theorem*}[Law of Quadratic Reciprocity] If $p$ and $q$ are distinct odd primes, then \begin{equation*} \ls pq\ls qp=(-1)^n,\quad\text{ where }\quad n=\frac{p-1}2\cdot\frac{q-1}2. \end{equation*} \end{theorem*} This Law was: \begin{itemize} \item conjectured by Euler, 1783; \item imperfectly proved by Legendre, 1785, 1798; \item discovered and proved independently by Gauss, 1795, at age 18. \end{itemize} \begin{proof}[Proof of Quadratic Reciprocity \textnormal{(due to Gauss's student Eisenstein)}] By the lemma just mentioned, \begin{equation*} \ls pq\ls qp=(-1)^n,\quad\text{ where }\quad n=\sum_{k=1}^{(q-1)/2}\left[\frac{kp}q\right]+ \sum_{\ell=1}^{(p-1)/2}\left[\frac{\ell q}p\right]. \end{equation*} So it is enough to show \begin{equation*} \frac{p-1}2\cdot\frac{q-1}2= \sum_{k=1}^{(q-1)/2}\left[\frac{kp}q\right]+ \sum_{\ell=1}^{(p-1)/2}\left[\frac{\ell q}p\right]. \end{equation*} First consider the example where $p=5$ and $q=7$. Then \begin{gather*} \frac{p-1}2\cdot\frac{q-1}2=2\cdot3=6;\\ \begin{split} \sum_{k=1}^{(q-1)/2}\left[\frac{kp}q\right]+ \sum_{\ell=1}^{(p-1)/2}\left[\frac{\ell q}p\right] &= \left[\frac{5}7\right]+ \left[\frac{10}7\right]+ \left[\frac{15}7\right]+ \left[\frac{7}5\right]+ \left[\frac{14}5\right]\\ &= 0+1+2+1+2=6. \end{split} \end{gather*} Here $6$ is the number of certain points in a lattice: \begin{center} \begin{pspicture}(-1,-6)(8,1) \multips(0,0)(1,0){8}{\psdots[dotsize=1pt 1](0,0)(0,-1)(0,-2)(0,-3)(0,-4)(0,-5)} \psline(0,0)(7,-5) \uput[ul](0,0){$(0,0)$} \uput[ur](7,0){$(0,7)$} \uput[dl](0,-5){$(5,0)$} \uput[dr](7,-5){$(5,7)$} \multips(1,-1)(1,0){3}{\psdots[dotsize=3pt 1](0,0)(0,-1)} \uput[u](1,0){$\left[\displaystyle\frac57\right]$} \uput[u](2,0){$\left[\displaystyle\frac{10}7\right]$} \uput[u](3,0){$\left[\displaystyle\frac{15}7\right]$} \uput[l](0,-1){$\left[\displaystyle\frac75\right]$} \uput[l](0,-2){$\left[\displaystyle\frac{14}5\right]$} \end{pspicture} \end{center} In general, $((p-1)/2)\cdot((q-1)/2)$ is the number of ordered pairs $(\ell,k)$ of integers such that \begin{equation*} 1\leq\ell\leq\frac{p-1}2,\quad\land\quad1\leq k\leq\frac{q-1}2. \end{equation*} Then $\ell/k\neq p/q$, since $p$ and $q$ are co-prime. Hence the set of these pairs $(\ell,k)$ is a disjoint union $A\cup B$, where \begin{align*} (\ell,k)\in A&\Iff \frac{\ell}k<\frac pq;\\ (\ell,k)\in B&\Iff\frac{\ell}k>\frac pq\Iff\frac k{\ell}<\frac qp. \end{align*} Hence \begin{gather*} A=\Bigl\{(\ell,k)\in\Z\times\Z\colon 1\leq k\leq\frac{q-1}2\land 1\leq\ell\leq\left[\frac{kp}q\right]\Bigr\},\\ B=\Bigl\{(\ell,k)\in\Z\times\Z\colon 1\leq\ell\leq\frac{p-1}2\land 1\leq k\leq\left[\frac{\ell q}p\right]\Bigr\}, \end{gather*} so \begin{equation*} \frac{p-1}2\cdot\frac{q-1}2=\size{A\cup B}=\size A+\size B= \sum_{k=1}^{(q-1)/2}\left[\frac{kp}q\right]+ \sum_{\ell=1}^{(p-1)/2}\left[\frac{\ell q}p\right], \end{equation*} which is what we wanted to show. \end{proof} Again, the more useful form of the theorem is \begin{equation*} \ls qp= \begin{cases} (p/q),&\text{ if }p\equiv1\text{ or }q\equiv 1\pmod 4;\\ -(p/q),&\text{ if }q\equiv3\equiv p\pmod 4. \end{cases} \end{equation*} Hence, for example, \begin{equation*} \ls{47}{199} =-\ls{199}{47} =-\ls{11}{47} =\ls{47}{11} =\ls3{11} =-\ls{11}3 =-\ls23=-(-1)=1. \end{equation*} We have used here the formula for $(2/p)$. What about $(3/p)$? We can compute: \begin{equation*} \ls 3p=\left\{ \begin{aligned} \ls p3,&\text{ if }p\equiv1\pmod 4\\ -\ls p3,&\text{ if }p\equiv 3\pmod 4 \end{aligned}\right\},\quad \ls p3= \begin{cases} 1,&\text{ if }p\equiv1\pmod 3\\ -1,&\text{ if }p\equiv2\pmod 3. \end{cases} \end{equation*} By the Chinese Remainder Theorem, we have \begin{align*} \left\{ \begin{aligned} p&\equiv1\pod 4\\ p&\equiv1\pod 3 \end{aligned} \right\}&\Iff p\equiv1\pod{12},& \left\{ \begin{aligned} p&\equiv1\pod 4\\ p&\equiv2\pod 3 \end{aligned} \right\}&\Iff p\equiv5\pod{12},\\ \left\{ \begin{aligned} p&\equiv3\pod 4\\ p&\equiv1\pod 3 \end{aligned} \right\}&\Iff p\equiv7\pod{12},& \left\{ \begin{aligned} p&\equiv3\pod 4\\ p&\equiv2\pod 3 \end{aligned} \right\}&\Iff p\equiv11\pod{12}. \end{align*} Therefore \begin{equation*} \ls 3p= \begin{cases} 1,&\text{ if }p\equiv\pm1\pmod p,\\ -1,&\text{ if }p\equiv\pm5\pmod p. \end{cases} \end{equation*} \asterism{} Assuming $\gcd(a,n)=1$, we know when the congruence $x^2\equiv a\pmod n$ has solutions, provided $n$ is an odd prime; but what about the other cases? When $n=2$, then the congruence always has the solution $1$. If $\gcd(m,n)=1$, and $\gcd(a,mn)=1$, then the congruence $x^2\equiv a\pmod{mn}$ is soluble if and only if the system \begin{equation*} \left\{ \begin{aligned} x^2&\equiv a\pmod m,\\ x^2&\equiv a\pmod n \end{aligned} \right. \end{equation*} is soluble. By the Chinese Remainder Theorem, the system is soluble if and only if the individual congruences are separately soluble. Indeed, suppose $b^2\equiv a\pmod m$, and $c^2\equiv a\pmod n$. By the Chinese Remainder Theorem, there is some $d$ such that $d\equiv b\pmod m$ and $d\equiv c\pmod n$. Then $d^2\equiv b^2\equiv a\pmod m$, and $d^2\equiv c^2\equiv a\pmod n$, so $d^2\equiv a\pmod{mn}$. For example, suppose we want to solve \begin{equation*} x^2\equiv365\pmod{667}. \end{equation*} Factorize $667$ as $23\cdot29$. Then we first want to solve \begin{equation*} x^2\equiv365\pmod{23}\quad\land\quad x^2\equiv365\pmod{29}. \end{equation*} But we have $(365/23)=(20/23)=(5/23)=(23/5)=(3/5)=-1$ by the formula for $(3/p)$, so the first of the two congruences is insoluble, and therefore the original congruence is insoluble. It doesn't matter whether the second of the two congruences is insoluble. Contrast with the following: $(2/11)=-1$, and $(7/11)=-(11/7)=-(4/7)=-1$; so the congruences \begin{equation*} x^2\equiv2\pmod{11},\qquad x^2\equiv7\pmod{11} \end{equation*} are insoluble; but $x^2\equiv14\pmod{11}$ is soluble. Now consider \begin{equation*} x^2\equiv361\pmod{667}. \end{equation*} One may notice that this has the solutions $x\equiv\pm19$; but there are others, and we can find them as follows. We first solve \begin{equation*} x^2\equiv16\pmod{23},\qquad x^2\equiv13\pmod{29}. \end{equation*} The first of these is solved by $x\equiv\pm4\pmod{23}$ (and nothing else, since $23$ is prime. For the second, note $13\equiv42,71,100\pmod{29}$, so $x\equiv\pm10\pmod{29}$. So the solutions of the original congruence are the solutions of one of the following systems: \begin{align*} & \left\{ \begin{aligned} x&\equiv 4 \pmod{23},\\ x&\equiv 10\pmod{29} \end{aligned} \right\}, && \left\{ \begin{aligned} x&\equiv 4\pmod{23},\\ x&\equiv -10\pmod{29} \end{aligned} \right\},\\ & \left\{ \begin{aligned} x&\equiv -4\pmod{23},\\ x&\equiv 10\pmod{29} \end{aligned} \right\}, && \left\{ \begin{aligned} x&\equiv -4\pmod{23},\\ x&\equiv -10\pmod{29} \end{aligned} \right\}. \end{align*} One finds $x\equiv19,648,280,387\pmod{667}$. So now $x^2\equiv a\pmod n$ is soluble if and only if the congruences \begin{equation*} x^2\equiv a\pmod{p^{k(p)}} \end{equation*} are soluble, where $n=\prod_{p\divides n}p^{k(p)}$. Assuming $p$ is odd, and $(a/p)=1$, we can show by induction that $x^2\equiv a\pmod{p^k}$ is soluble for all positive $k$. Indeed, suppose $b^2\equiv a\pmod{p^{\ell}}$, where $\ell\geq1$. This means \begin{equation*} b^2=a+c\cdot p^{\ell} \end{equation*} for some $c$. Then \begin{align*} (b+p^{\ell}\cdot y)^2 &=b^2+2bp^{\ell}\cdot y+p^{2\ell}\cdot y^2\\ &=a+(c+2by)p^{\ell}+p^{2\ell}\cdot y^2 \end{align*} Therefore $(b+p^{\ell}\cdot y)^2\equiv a\pmod{p^{\ell+1}} \Iff c+2by\equiv0\pmod p$. But the latter congruence is soluble, since $p$ is odd. \section{December 25, 2007 (Tuesday)} Assuming $\gcd(a,n)=1$, we have shown that $x^2\equiv a\pmod n$ is soluble if and only if $x^2\equiv a\pmod{p^{k(p)}}$ is soluble whenever $p\divides n$, where $n=\prod_{p\divides n}p^{k(p)}$. We also have that, if $p$ is an odd prime, and $p\ndivides a$, then the following are equivalent: \begin{enumerate} \item $(a/p)=1$; \item $x^2\equiv a\pmod p$ is soluble; \item $x^2\equiv a\pmod{p^k}$ is soluble for some positive $k$; \item $x^2\equiv a\pmod{p^k}$ is soluble for all positive $k$. \end{enumerate} We must finally consider powers of $2$. \begin{theorem*} Suppose $a$ is odd. Then: \begin{enumerate} \item $x^2\equiv a\pmod 2$ is soluble; \item $x^2\equiv a\pmod 4$ is soluble if and only if $a\equiv 1\pmod 4$; \item the following are equivalent: \begin{enumerate} \item\label{item:8} $x^2\equiv a\pmod 8$ is soluble; \item\label{item:some} $x^2\equiv a\pmod{2^{2+k}}$ is soluble for some positive $k$; \item\label{item:all} $x^2\equiv a\pmod{2^{2+k}}$ is soluble for all positive $k$; \item\label{item:a18} $a\equiv 1\pmod 8$. \end{enumerate} \end{enumerate} \end{theorem*} \begin{proof} The first two parts are easy. So, are~\eqref{item:8}$\Leftrightarrow$\eqref{item:a18} and~\eqref{item:all}$\Rightarrow$\eqref{item:some}$\Rightarrow$\eqref{item:8}. We shall show~\eqref{item:8}$\Rightarrow$\eqref{item:all} by induction. Suppose $b^2\equiv a\pmod{2^{2+\ell}}$ for some positive $\ell$. Then $b^2=a+2^{2+\ell}\cdot c$ for some $c$. Hence \begin{align*} (b+2^{1+\ell}\cdot y)^2 &=b^2+2^{2+\ell}\cdot by+2^{2+2\ell}\cdot y^2\\ &=a+2^{2+\ell}\cdot c+2^{2+\ell}\cdot by+2^{2+2\ell}\cdot y^2\\ &=a+2^{2+\ell}\cdot(c+by)+2^{2+2\ell}\cdot y^2, \end{align*} and this is congruent to $a$ \emph{modulo} $p^{3+\ell}$ if and only if $c+by\equiv 0\pmod 2$. But this congruence is soluble, since $b$ is odd (since $a$ is odd). \end{proof} \asterism{} A \emph{Diophantine equation}{} is an equation for which the solutions sought are integers. We have considered such equations, as for example $ax+by=c$. Now we shall show that, if $n$ is a natural number, then the Diophantine equation \begin{equation*} x^2+y^2+z^2+w^2=n \end{equation*} is soluble. If $p$ is an odd prime, we know that the congruence $x^2\equiv-1\pmod p$ is soluble if and only if $(-1/p)=1$, that is, $(-1)^{(p-1)/2}=1$, that is, $p\equiv 1\pmod 4$. \begin{lemma*} For every prime $p$, the congruence \begin{equation*} x^2+y^2\equiv-1\pmod p \end{equation*} is soluble. \end{lemma*} \begin{proof} The claim is easy when $p=2$. So assume now $p$ is odd. We define two sets: \begin{gather*} A=\Bigl\{x^2\colon0\leq x\leq\frac{p-1}2\Bigr\},\\ B=\Bigl\{-y^2-1\colon0\leq x\leq\frac{p-1}2\Bigr\}. \end{gather*} We shall show that $A$ and $B$ have elements representing the same congruence-class \emph{modulo} $p$; that is, $A$ contains some $a$, and $B$ contains some $b$, such that $a\equiv b\pmod p$. To prove this, note first that distinct elements of $A$ are incongruent, and likewise of $B$. Indeed, if $a_0$ and $a_1$ are between $0$ and $(p-1)/2$ inclusive, and $a_0{}^2\equiv a_1{}^2\pmod p$, then $a_0\equiv\pm a_1\pmod p$. If $a_0\equiv-a_1$, then $a_0=p-a_1$, which is absurd. Hence $a_0\equiv a_1\pmod p$, so $a_0=a_1$. Hence the elements of $A$ represent $(p-1)/2+1$ distinct congruence-classes \emph{modulo} $p$, and so do the elements of $B$. Since $2((p-1)/2+1)=p+1$, and there are only $p$ distinct congruence-classes \emph{modulo} $p$, there must be a class represented both in $A$ and in $B$, by the Pigeonhole Principle. \end{proof} Another way to express the lemma is that, for all primes $p$, there are $a$, $b$, and $m$ such that \begin{equation*} a^2+b^2+1=mp. \end{equation*} Hence there are $a$, $b$, $c$, $d$, and $m$ such that \begin{equation*} a^2+b^2+c^2+d^2=mp. \end{equation*} We shall show that we can require $m=1$. We can combine this with the following: \begin{theorem*}[Euler] The product of two sums of four squares is the sum of four squares. \end{theorem*} \begin{proof} One can confirm that \begin{equation*} (a^2+b^2+c^2+d^2)(q^2+r^2+s^2+t^2)= \begin{aligned}[t] (aq&+br+cs+dt)^2+{}\\ (ar&-bq+ct-ds)^2+{}\\ (as&-bt-cq+dr)^2+{}\\ (at&+bs-cr-dq)^2 \end{aligned} \end{equation*} by expanding each side. \end{proof} \begin{theorem*}[Lagrange] Every positive integer is the sum of four squares. \end{theorem*} \begin{proof} By the lemma Euler's theorem, it is now enough to show the following. Let $p$ be a prime. Suppose $m$ is a positive integer such that \begin{equation}\label{eqn:abcd} a^2+b^2+c^2+d^2=mp \end{equation} for some $a$, $b$, $c$, and $d$. We shall show that the same is true for some smaller positive $m$, unless $m$ is already $1$. First we show that, if $m$ is even, then we can replace it with $m/2$. Indeed, if $a^2+b^2=n$, then \begin{equation*} \Bigl(\frac{a+b}2\Bigr)^2+ \Bigl(\frac{a-b}2\Bigr)^2=\frac n2, \end{equation*} and if $n$ is even, then so are $(a\pm b)/2$. In~\eqref{eqn:abcd} then, if $m$ is even, then we may assume that $a^2+b^2$ and $c^2+d^2$ are both even, so \begin{equation*} \Bigl(\frac{a+b}2\Bigr)^2+ \Bigl(\frac{a-b}2\Bigr)^2+ \Bigl(\frac{c+d}2\Bigr)^2+ \Bigl(\frac{c-d}2\Bigr)^2=\frac m2\cdot p. \end{equation*} Henceforth we may assume $m$ is odd. Then there are $q$, $r$, $s$ and $t$ \emph{strictly} between $-m/2$ and $m/2$ such that \begin{equation*} q\equiv a,\quad r\equiv b,\quad s\equiv c,\quad t\equiv d\pmod m. \end{equation*} Then \begin{equation*} q^2+r^2+s^2+t^2\equiv0\pmod m, \end{equation*} but also $q^2+r^2+s^2+t^2