\documentclass[% version=last,% a5paper,% 10pt,% headings=small,% bibliography=totoc,% index=totoc,% twoside,% reqno,% cleardoublepage=empty,% open=any,% %draft=false,% draft=true,% %BCOR=2mm,% DIV=18,% %DIV=12,% %DIV=10,% %DIV=9,% headinclude=false,% pagesize]% {scrbook} %\usepackage[nosolutionfiles]{answers} %\usepackage{answers} %\Newassociation{soln}{rawsolution}{math-365-text-raw-solutions} %\usepackage{showlabels} \makeindex \usepackage{makeidx} \usepackage{scrpage2} \pagestyle{scrheadings} \ohead{} \ihead{} \ofoot{\pagemark} \ifoot{\headmark} %\usepackage{float} %\floatstyle{boxed} %\floatstyle{ruled} %\restylefloat{figure} \renewcommand*{\captionformat}{ } % This does not work with the float % package \usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X \renewenvironment{quote}{\begin{list}{} {\relscale{.90}\setlength{\leftmargin}{0.05\textwidth} \setlength{\rightmargin}{\leftmargin}} \item[]} {\end{list}} \usepackage{cclicenses} \usepackage{amssymb,amsmath,amsthm} \usepackage{url} \usepackage{verbatim} % allows a comment environment: \usepackage[all]{xy} \usepackage{pstricks} \usepackage{textcomp} % supposedly useful with \oldstylenums \usepackage{multicol} \usepackage[neverdecrease]{paralist} \usepackage{flafter} % floats appear after they are mentioned \usepackage{layout} \usepackage{hfoldsty} % this didn't work until I added missing % brackets to some of the files. \usepackage[polutonikogreek,english]{babel} \newcommand{\Gk}[1]{\selectlanguage{polutonikogreek}#1\selectlanguage{english}} \usepackage{graphicx,rotating} \hyphenation{Arith-metic} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \renewcommand{\leq}{\leqslant} \renewcommand{\geq}{\geqslant} \renewcommand{\setminus}{\smallsetminus} \renewcommand{\phi}{\varphi} \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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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} \usepackage{bm} \newcommand{\class}[1]{\bm{#1}} \newcommand{\on}{\mathbf{ON}} \newcommand{\stnd}[1]{\mathbb{#1}} \newcommand{\N}{\stnd{N}} % natural numbers \newcommand{\Z}{\stnd{Z}} % integers \newcommand{\Q}{\stnd{Q}} % rationals \newcommand{\Qp}{\stnd Q^+} % positive rationals %\newcommand{\Pri}{\stnd{P}} % primes \newcommand{\R}{\stnd{R}} % reals \newcommand{\C}{\stnd{C}} % complex numbers \newcommand{\Ham}{\stnd H} % quaternions \newcommand{\mi}{\mathrm i} \newcommand{\me}{\mathrm e} \newcommand{\mj}{\mathrm j} \newcommand{\mk}{\mathrm k} \usepackage{upgreek} \newcommand{\mpi}{\uppi} \newcommand{\ephi}{\upvarphi} %\renewcommand{\theta}{\vartheta} \newcommand{\mtheta}{\upvartheta} \newcommand{\id}{\mathrm{id}} \newcommand{\mep}{\upvarepsilon} \newcommand{\mmu}{\upmu} \newcommand{\msig}{\upsigma} \newcommand{\mtau}{\uptau} \newcommand{\mpsi}{\uppsi} \newcommand{\rzeta}{\upzeta} \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{\Lap}[1]{\mathcal L\{#1\}} \let\oldsqrt\sqrt \renewcommand{\sqrt}[1]{\oldsqrt{\vphantom1}{#1}} \newcommand{\rten}{\sqrt{10}} %\newcommand{\dsp}{\,} % space between blocks of three digits %%%%%%%%%%%%%% For the Sieve of Eratosthenes %\usepackage{cancel} %\newcommand{\os}[1]{\,\cancel{#1}\,} \newcommand{\os}[1]{\,\makebox[0pt][l]{/}#1\,} \newcommand{\pb}[1]{\fbox{$#1$}} %\usepackage{ulem} %\newcommand{\pb}[1]{\,\uline{#1}\,} \newcommand{\mymod}{\operatorname{mod}} \newcommand{\rem}[1]{\operatorname{rem}(#1)} \numberwithin{equation}{chapter} \renewcommand{\theequation}{\fnsymbol{equation}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Theorem-like environments % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Main text: \newtheorem*{lemma}{Lemma} \newtheorem*{corollary}{Corollary} \newtheorem{theorem}{Theorem} \newtheorem*{axdef}{Axiom and definition} \theoremstyle{definition} \newtheorem*{definition}{Definition} \theoremstyle{remark} \newtheorem*{remark}{Remark} % Appendix B: Exercises \theoremstyle{definition} \newtheorem{xca}{Exercise}%[section] \newenvironment{soln}{\emph{Solution:}}{} % Appendix C: Examinations \theoremstyle{plain} \newtheorem{problem}{Problem}[section] \renewcommand{\theproblem}{\arabic{section}.\arabic{problem}} \theoremstyle{definition} \newtheorem*{solution}{Solution} \theoremstyle{remark} \newtheorem*{remark*}{Remark} \newcommand{\hw}[1]{\hfill{}\textnormal{[#1]}} % to show a homework % source for an exam problem \begin{document} \title{Elementary Number Theory} \author{David Pierce} \date{\today} \publishers{Mathematics Department\\ Mimar Sinan Fine Arts University\\ Istanbul\\ \url{dpierce@msgsu.edu.tr}\\ \url{http://mat.msgsu.edu.tr/~dpierce/}} \uppertitleback{\centering This work is licensed under the\\ Creative Commons\\ Attribution-NonCommercial-ShareAlike 3.0\\ Unported License.\\ To view a copy of this license, visit\\ \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}\\ or send a letter to\\ Creative Commons,\\ 444 Castro Street, Suite 900,\\ Mountain View, California, 94041, USA. \mbox{}\\ Bu \c cal\i\c sma\\ Creative Commons Attribution-Gayriticari-ShareAlike 3.0\\ Unported Lisans\i\ ile lisansl\i.\\ Lisans\i n bir kopyas\i n\i\ g\"orebilmek i\c cin,\\ \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}\\ adresini ziyaret edin ya da mektup at\i n:\\ Creative Commons,\\ 444 Castro Street, Suite 900,\\ Mountain View, California, 94041, USA.\\ \mbox{}\\ \cc \ccby David Austin Pierce \ccnc \ccsa\\ \mbox{}\\ Matematik B\"ol\"um\"u\\ Mimar Sinan G\"uzel Sanatlar \"Universitesi\\ Bomonti, \c Si\c sli, \.Istanbul, 34380\\ \mbox{}\\ \url{dpierce@msgsu.edu.tr}\\ \url{http://mat.msgsu.edu.tr/~dpierce/} } \maketitle \tableofcontents \listoffigures \listoftables \addchap{Preface} This book started out as a record of my lectures in the course called Elementary Number Theory I (Math 365) at Middle East Technical University in Ankara in 2007--8. When I was to teach the same course in 2010--1, I revised my lecture-notes and made them the official text for the course. That text, dated September 29, 2011, was 139 pages long. After the course, filled with enthusiasm, I made many revisions and additions. The result is this book. The standard text for Math 356 at METU was Burton's \emph{Elementary Number Theory}~\cite{Burton}. My lectures of 2007--8 more or less followed this. The catalogue description of the course was: \begin{quote}%\sloppy Divisibility, congruences, Euler, Chinese Remainder and Wilson's Theorems. Arithmetical functions. Primitive roots. Quadratic resi\-dues and quadratic reciprocity. Diophantine equations. \end{quote} In 2010--1, without realizing that \emph{I} had written the course textbook, one student complained that it was hard to read. I am glad he felt free to criticize. But I had not aimed to create a textbook that could replace classroom lectures. I had written summarily, without trying to give all of the explanations that anybody could possibly want. Among the many changes I have made since the 2010--1 course, I have: \begin{compactenum}[1)] \item put proofs of theorems \emph{after} their statements, and not before as is sometimes natural in lectures (an omitted proof in the present text is left to the reader as an exercise); \item removed the Fermat factorization method~\cite[\S5.4]{Burton} as being out of the main stream of the course; \item added Dirichlet convolution, which gives a streamlined way of understanding M\"obius inversion \emph{and} of defining the phi-function; \item added forward references, to show better how everything is interconnected; \item added citations for the theorems, when I have been able to find them. \end{compactenum} Precisely because these changes are significant, the book must still be considered as a work in progress, a rough draft. As I suggested, Burton's text was the original model for this book,---but not in style, only in arrangement of topics. Models for style, as well as sources of content, include the sparer texts of Landau~\cite{MR0092794} and Hardy and Wright~\cite{MR568909}. Much of the mathematics in the present text can be found in Gauss's \emph{Disquisitiones Arithmeticae}~\cite{Gauss} of 1801, written when Gauss was the age of many undergraduate students. Some of the mathematics is two thousand years older than Gauss. I have made some attempt to trace theorems to their origins; but this work is not complete. I prefer to see the primary source myself before attributing a theorem. In this case, I cite the source \emph{near} the theorem itself, possibly in a footnote, and not in some extra section at the end of the chapter. Even when I can find the primary source, usually a secondary source has led me there. The secondary source helps to determine what the primary source \emph{is.} The best history would arise from reading all \emph{possible} primary sources; but I have not done this. Full names and dates of mathematicians named in the text are generally taken from the MacTutor History of Mathematics archive,\footnote{\url{http://www-gap.dcs.st-and.ac.uk/~history/index.html}} or from Wikipedia. I ask students to learn something of the logical foundations of number theory. Section~\ref{sect:N} contains an account of these foundations, namely a derivation of basic arithmetic from the so-called Peano Axioms. This section was originally an appendix, but I have decided that it belongs in the main body of text, even if most number theory texts do not have such a section. Chapter~\ref{ch:foundations} is filled out with a summary review of the constructions of the other standard number systems, of integers, rationals, reals, and complex numbers. All of these systems have their place in number theory. Their constructions alone could constitute a course, and I do not expect number theory students as such to go through them all; but students should be aware that the constructions \emph{can} be done, and they themselves can do them. Readers will already know most of the \emph{results} of Chapter~\ref{ch:foundations}. Assuming some of these results, the preceeding Chapter~\ref{ch:look} is a general exploration of what \emph{can} be done with numbers and, in some cases, what \emph{has} been done for over two thousand years. The chapter begins with the \emph{visual} display of certain numbers as triangles or squares. Throughout the text, where it makes sense, I try to display the mathematics in pictures or tables, as for example in the account of the Chinese Remainder Theorem in \S\ref{sect:CRT-again}. Appendix~\ref{ch:foundations-again} begins with the \emph{construction} of the natural numbers by von Neumann's method. This is a part of set theory and is beyond the scope of the course as such, but it is good for everybody to know that the construction can be done. The appendix continues with a discussion of common misunderstandings of foundational matters. I do not like to quote a theorem without either proving it or being able to expect readers to prove it for themselves. In the original course, I did quote theorems, some recent, without myself knowing the proofs; I have now relegated these to Appendix~\ref{ch:unproved}. Appendix~\ref{ch:exercises} consists of exercises, most of which were made available in installments to the students in the 2007/8 class. I have not incorporated the exercises into the main text. One reason for this is to make it less obvious how the exercises should be done. The position of an exercise in a text is often a hint as to how the exercise should be done; and yet there are no such hints on examinations. The exercises here are strung together in one numbered sequence. (So, by the way, are the theorems in the main text.) Appendices~\ref{ch:exams} and \ref{ch:exams-2} contain the examinations given to the 2007--8 and 2010--1 classes, along with my solutions and remarks on students' solutions. In 2007--8, I treated $0$ as a natural number; in 2010--1, I did not. In the present book, I intend to use the symbol $\N$ for the set $\{1,2,3,\dots\}$; if a symbol for the set $\{0,1,2,\dots\}$ is desired, this symbol can be $\upomega$. I have tried to update Appendix~\ref{ch:exams} (as well as my original lecture-notes from 2007--8) accordingly. \chapter{Proving and seeing}\label{ch:look} \section{The look of a number} What can we say about the following sequence of numbers? \begin{equation*} 1,3,6,10,15,21,28,\dots \end{equation*} The terms increase by $2$, $3$, $4$, and so on. A related observation is that the numbers in the sequence can be given an appearance, a \textbf{look,}\index{look} as shown in Figure~\ref{fig:triangular}. \begin{figure}[ht] \begin{center} \psset{xunit=1cm,yunit=1.73cm} \begin{pspicture}(0,-0.8)(8,0) %\psgrid \psdots(0,0) (1.0,-0.2)(1.4,-0.2) (1.2,0.0) (2.4,-0.4)(2.8,-0.4)(3.2,-0.4) (2.6,-0.2)(3,-0.2) (2.8,0.0) (4.2,-0.6)(4.6,-0.6)(5,-0.6)(5.4,-0.6) (4.4,-0.4)(4.8,-0.4)(5.2,-0.4) (4.6,-0.2)(5,-0.2) (4.8,0.0) (6.4,-0.8)(6.8,-0.8)(7.2,-0.8)(7.6,-0.8)(8.0,-0.8) (6.6,-0.6)(7.0,-0.6)(7.4,-0.6)(7.8,-0.6) (6.8,-0.4)(7.2,-0.4)(7.6,-0.4) (7.0,-0.2)(7.4,-0.2) (7.2,0.0) \end{pspicture} \end{center} \caption{Triangular numbers}\label{fig:triangular} \end{figure} In particular, the numbers are the \textbf{triangular numbers.}% \index{triangular number}% \index{number!triangular ---} Let us designate them by $t_1$, $t_2$, $t_3$, and so on. Then they can be given \textbf{recursively}\index{recursive definition} by the equations \begin{align*} t_1&=1,& t_{n+1}&=t_n+n+1. \end{align*} This definition can be abbreviated as \begin{equation*} t_n=\sum_{k=1}^nk. \end{equation*} The triangular numbers can also be given non-recursively, in \textbf{closed form}% \index{closed form} (so that $t_n$ can be calculated directly): \begin{theorem} For all numbers $n$, \begin{equation}\label{eqn:tn} t_n %=\sum_{k=1}^nk %=\binom{n+1}{2} =\frac{n(n+1)}{2}. \end{equation} \end{theorem} \begin{proof} We prove the claim~\eqref{eqn:tn} for all $n$ by \textbf{induction:}\index{induction} \begin{compactenum}[1.] \item The claim is true when $n=1$. \item If the claim is true when $n=k$, so that $t_k=k(k+1)/2$, then \begin{align*} t_{k+1} &=t_k+k+1\\ &=\frac{k(k+1)}{2}+k+1\\ &=\frac{k(k+1)}{2}+\frac{2(k+1)}2\\ &=\frac{(k+2)(k+1)}{2}\\ &=\frac{(k+1)(k+2)}{2}, \end{align*} so the claim is true when $n=k+1$. \end{compactenum} By induction then, \eqref{eqn:tn} is true for all $n$. \end{proof} So equation~\eqref{eqn:tn} \emph{is} true; but we might ask further: \emph{why} is it true? One answer can be seen in a picture. First rewrite~\eqref{eqn:tn} as \begin{equation*} 2t_n=n(n+1). \end{equation*} Two copies of $t_n$ do indeed fit together to make an $n\times(n+1)$ array of dots, \begin{figure}[ht] \begin{center} \begin{pspicture}(0,-1.2)(1.6,0) \psdots(0,0) (0.4,0) (0.8,0) (1.2,0) (0,-0.4)(0.4,-0.4)(0.8,-0.4) (0,-0.8)(0.4,-0.8) (0,-1.2) \psdots[dotstyle=o] (1.6,-0) (1.2,-0.4)(1.6,-0.4) (0.8,-0.8)(1.2,-0.8)(1.6,-0.8) (0.4,-1.2)(0.8,-1.2)(1.2,-1.2)(1.6,-1.2) \end{pspicture} \end{center} \caption{A pair of equal triangular numbers}\label{fig:equal-tri} \end{figure} as in Figure~\ref{fig:equal-tri}. One may establish other identities in the same way. \begin{figure}[ht] \begin{center} \begin{pspicture}(0,-1.6)(1.6,0) \psdots(0,0)(0.4,0)(0.8,0)(1.2,0)(1.6,0) (0,-0.4)(0.4,-0.4)(0.8,-0.4)(1.2,-0.4) (0,-0.8)(0.4,-0.8)(0.8,-0.8) (0,-1.2)(0.4,-1.2) (0,-1.6) \psdots[dotstyle=o] (1.6,-0.4) (1.2,-0.8)(1.6,-0.8) (0.8,-1.2)(1.2,-1.2)(1.6,-1.2) (0.4,-1.6)(0.8,-1.6)(1.2,-1.6)(1.6,-1.6) \end{pspicture} \end{center} \caption{A pair of consecutive triangular numbers}\label{fig:cons-tri} \end{figure} For example, Figure~\ref{fig:cons-tri} suggests the next theorem.\footnote{The theorem is mentioned by Nicomachus of Gerasa (c.~60--c.~120) in his \emph{Introduction to Arithmetic}~\cite[II.XII.1--2, p.~247]{Nicomachus}. For him, the picture alone seems to have been sufficient proof. (Gerasa is now Jerash, in Jordan.)} \begin{theorem} For all numbers $n$, \begin{equation*} t_{n+1}+t_n=(n+1)^{2}. \end{equation*} \end{theorem} \begin{proof} Just compute: \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}.\qedhere \end{equation*} \end{proof} 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}$. Indeed we do have: \begin{theorem}\label{thm:n^2} For all numbers $n$, \begin{equation}\label{eqn:n2} \sum_{k=1}^n({2}k-1)=n^{2}. \end{equation} \end{theorem} \begin{proof} We use induction. \begin{compactenum}[1.] \item The claim is true when $n=1$. \item If the claim is true when $n=k$, then \begin{equation*} \sum_{j=1}^{k+1}({2}j-1) =\sum_{j=1}^k({2}j-1)+{2}k+1 =k^{2}+{2}k+1 =(k+1)^{2}, \end{equation*} so the claim is true when $n=k+1$. \end{compactenum} Therefore~\eqref{eqn:n2} is true for all $n$. \end{proof} Figure~\ref{fig:odds} \begin{figure}[ht] \begin{center} \psset{unit=4mm} \begin{pspicture}(1,1)(5,5) \psdots (1,1)(3,1)(5,1)(3,2)(5,2)(1,3)(2,3)(3,3)(5,3)(5,4)(1,5)(2,5)(3,5)(4,5)(5,5) \psdots[dotstyle=o](2,1)(4,1)(1,2)(2,2)(4,2)(4,3)(1,4)(2,4)(3,4)(4,4) \end{pspicture} \end{center} \caption{Consecutive odd numbers}\label{fig:odds} \end{figure} shows why the theorem is true. The point here is that, once a numerical sequence is defined recursively, then identities involving the sequence can be \emph{proved} by induction; but the identities will probably be first \emph{discovered} in other ways, possibly through pictures. From figure~\ref{fig:odds}, we may derive two more observations.\footnote{These observations are suggested by two possible interpretations of a passage in Aristotle's \emph{Physics.} In \emph{A History of Greek Mathematics}~\cite[p.~77]{MR654679}, Thomas Heath asserts that Aristotle (384--322) alludes to Figure~\ref{fig:odds} in that passage. Here is Apostol's translation of the passage~\cite[$\Gamma$ 4]{Aristo-Phy-Apost}: `Moreover, the Pythagoreans posit the infinite as being the \emph{Even;} for they say that it is this which, when cut off and limited by the \emph{Odd,} provides [as matter] for the infinity of things. A sign of this, they say, is what happens to numbers; for if gnomons are placed around the one and apart, in the latter case the form produced is always distinct, but in the former it is unique.' Here a \emph{gnomon} is apparently a figure in the shape of the letter \textsf L (the word originally refers to the part of a sundial whose shadow shows the time). So Figure~\ref{fig:odds} results from placing gnomons around one dot. If we then remove the dot, we get Figure~\ref{fig:n^2-1}; if we start with two dots rather than one, we get Figure~\ref{fig:evens}. A few centuries later, Theon\index{Theon of Smyrna} of Smyrna (c.~70--c.~135) states Theorem~\ref{thm:n^2} in his \emph{Mathematics useful for understanding Plato}~\cite[pp.~52--55]{Theon}. (Smyrna is today's \.Izmir.)} The rearrangement shown in Figure~\ref{fig:n^2-1} \begin{figure}[ht] \mbox{}\hfill \psset{unit=4mm} \begin{pspicture}(1,1)(5,5) \psdots (3,1)(5,1)(3,2)(5,2)(1,3)(2,3)(3,3)(5,3)(5,4)(1,5)(2,5)(3,5)(4,5)(5,5) \psdots[dotstyle=o](2,1)(4,1)(1,2)(2,2)(4,2)(4,3)(1,4)(2,4)(3,4)(4,4) \end{pspicture} \hfill \begin{pspicture}(0,1)(5,5) \psdots (3,2)(5,2)(0,3)(1,3)(2,3)(3,3)(5,3)(5,4)(0,5)(1,5)(2,5)(3,5)(4,5)(5,5) \psdots[dotstyle=o](0,2)(1,2)(2,2)(4,2)(4,3)(0,4)(1,4)(2,4)(3,4)(4,4) \end{pspicture} \hfill\mbox{} \caption{Consecutive odd numbers, without one}\label{fig:n^2-1} \end{figure} suggests the identity \begin{equation*} n^2-1=(n+1)(n-1), \end{equation*} while Figure~\ref{fig:evens} \begin{figure}[ht] \centering \psset{unit=4mm} \begin{pspicture}(1,2)(5,5) \psdots (3,2)(5,2)(1,3)(2,3)(3,3)(5,3)(5,4)(1,5)(2,5)(3,5)(4,5)(5,5) \psdots[dotstyle=o](1,2)(2,2)(4,2)(4,3)(1,4)(2,4)(3,4)(4,4) \end{pspicture} \caption{Consecutive even numbers}\label{fig:evens} \end{figure} suggests \begin{equation*} \sum_{k=1}^n2k=n(n+1). \end{equation*} Observe finally: \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.\footnote{This theorem too was apparently known to Nicomachus~\cite[II.XX.5, p.~263]{Nicomachus}.} \section{Patterns that fail} The following passage from V. I. Arnol$'$d's talk `On the teaching of mathematics'~\cite{Arnold} seems to provide a reasonable description of how mathematics (and in particular number theory) is done.\footnote{A footnote explains the origin of the text: `This is an extended text of an address at a discussion on the teaching of mathematics in Palais de D\'ecouverte in Paris on 7 March 1997.' The text is on line at \url{http://pauli.uni-muenster.de/~munsteg/arnold.html} (accessed November 14, 2010). I do not actually agree that mathematics is a part of physics.} \begin{quote} Mathematics is a part of physics. Physics is an experimental science, a part of natural science. Mathematics is the part of physics where experiments are cheap\dots The scheme of construction of a mathematical theory is exactly the same as that in any other natural science. First we consider some objects and make some observations in special cases. Then we try and find the limits of application of our observations, look for counter-examples which would prevent unjustified extension of our observations onto a too wide range of events (example: the number of partitions of consecutive odd numbers $1$, $3$, $5$, $7$, $9$ into an odd number of natural summands gives the sequence $1$, $2$, $4$, $8$, $16$, but then comes $29$). As a result we formulate the empirical discovery that we made (for example, the Fermat conjecture or Poincar\'e conjecture) as clearly as possible. After this there comes the difficult period of checking as to how reliable are the conclusions. At this point a special technique has been developed in mathematics. This technique, when applied to the real world, is sometimes useful, but can sometimes also lead to self-deception. This technique is called modelling. When constructing a model, the following idealisation is made: certain facts which are only known with a certain degree of probability or with a certain degree of accuracy, are considered to be `absolutely' correct and are accepted as `axioms'. The sense of this `absoluteness' lies precisely in the fact that we allow ourselves to use these `facts' according to the rules of formal logic, in the process declaring as `theorems' all that we can derive from them. \end{quote} Arnol$'$d's parenthetical example is apparently the following. For each number $n$, we consider the number of ways to write the odd number $2n-1$ as a sum \begin{equation*} t_1+\cdots+t_{2k-1}, \end{equation*} where $k$ is an arbitrary number (so that $2k-1$ is an arbitrary odd number), but $t_1\geq\cdots\geq t_{2k-1}$. Let us call the number of such sums $a_n$. Immediately $a_1=1$; and since \begin{align*} 3&=1+1+1,& 5&={3}+1+1={2}+{2}+1=1+1+1+1+1, \end{align*} we have $a_2=2$ and $a_3=4$. To find $a_4$, we note \begin{align*} &\begin{aligned} &\phantom{{}={}}7\\ &=5+1+1\\ &=4+{2}+1\\ &={3}+{3}+1 \end{aligned}& &\begin{aligned} &={3}+{2}+{2}\\ &={3}+1+1+1+1\\ &={2}+{2}+1+1+1\\ &=1+1+1+1+1+1+1, \end{aligned} \end{align*} so $a_4=8$; and $a_5=16$, by the computations in Table~\ref{tab:9-as-sum} below. \begin{table} \hrulefill \begin{align*} &\begin{aligned} &\phantom{{}={}}9\\ &=7+1+1\\ &=6+2+1\\ &=5+3+1\\ &=5+2+2\\ &=5+1+1+1+1\\ &=4+4+1\\ &=4+3+2 \end{aligned}& &\begin{aligned} &=4+2+1+1+1\\ &=3+3+3\\ &=3+3+1+1+1\\ &=3+2+2+1+1\\ &=3+1+1+1+1+1+1\\ &=2+2+2+2+1\\ &=2+2+1+1+1+1+1\\ &=1+1+1+1+1+1+1+1+1 \end{aligned} \end{align*} \hrulefill \caption{The number $9$ as the sum of odd numbers of summands}\label{tab:9-as-sum} \end{table} Thus the equation \begin{equation}\label{eqn:a_n} a_n=2^{n-1} \end{equation} is correct when $n$ is $1$, $2$, $3$, $4$, or $5$. However, there is no obvious reason why it should be true when $n>5$. In fact it \emph{fails} when $n=6$. We have $a_6=29$, by counting the sums listed in Table~\ref{tab:sums}. \begin{sidewaystable} \begin{align*} &\begin{aligned} 11 &=9+1+1\\ &=8+2+1\\ &=7+3+1\\ &=7+2+2\\ &=7+1+1+1+1\\ &=6+4+1\\ &=6+3+2\\ &=6+2+1+1+1\\ &=5+5+1\\ &=5+4+2\\ &=5+3+3\\ &=5+3+1+1+1\\ &=5+2+2+1+1\\ &=5+1+1+1+1+1+1 \end{aligned}& &\begin{aligned} &=4+4+3\\ &=4+4+1+1+1\\ &=4+3+2+1+1\\ &=4+2+2+2+1\\ &=4+2+1+1+1+1+1\\ &=3+3+3+1+1\\ &=3+3+2+2+1\\ &=3+3+1+1+1+1+1\\ &=3+2+2+2+2\\ &=3+2+2+1+1+1+1\\ &=3+1+1+1+1+1+1+1+1\\ &=2+2+2+2+2+1\\ &=2+2+2+1+1+1+1+1\\ &=2+1+1+1+1+1+1+1+1+1. \end{aligned} \end{align*} \caption{The number $11$ as the sum of odd numbers of summands}\label{tab:sums} \end{sidewaystable} If one is so inclined, one can find further information on these numbers $a_n$ in the \emph{The On-Line Encyclopedia of Integer Sequences.}\footnote{\url{http://oeis.org/}, accessed November 14, 2010.} Another failed pattern is shown in Chapter 3, `Proofs', of Timothy Gowers's \emph{Mathematics: A Very Short Introduction} \cite{MR2147526}. Suppose $n$ distinct points are chosen on a circle, and each pair of the $n$ points are connected by a straight line, and no three of those straight lines have a common point. Then the circle is divided into a number of regions, say $a_n$ regions. Figure~\ref{fig:circles} \begin{figure} \hfill \begin{pspicture}(-1,-1)(1,1) \pscircle(0,0){1} \end{pspicture} \hfill \begin{pspicture}(-1,-1)(1,1) \pscircle(0,0){1} \psdots(0,1) \end{pspicture} \hfill \begin{pspicture}(-1,-1)(1,1) \pscircle(0,0){1} \psdots(0,1)(0,-1) \psline(0,1)(0,-1) \end{pspicture} \hfill \begin{pspicture}(-1,-1)(1,1) \pscircle(0,0){1} \psdots(0,1)(0.866,-0.5)(-0.866,-0.5) \pspolygon(0,1)(0.866,-0.5)(-0.866,-0.5) \end{pspicture} \hfill\mbox{} \psset{unit=1.333cm} \hfill \begin{pspicture}(-1,-1)(1,1.2) \pscircle(0,0){1} \psdots(0,1)(1,0)(0,-1)(-1,0) \pspolygon(0,1)(1,0)(0,-1)(-1,0) \psline(1,0)(-1,0) \psline(0,1)(0,-1) \end{pspicture} \hfill \begin{pspicture}(-1,-1)(1,1) \pscircle(0,0){1} \psdots(0,1)(0.951,0.309)(0.588,-0.809)(-0.588,-0.809)(-0.951,0.309) \pspolygon(0,1)(0.951,0.309)(0.588,-0.809)(-0.588,-0.809)(-0.951,0.309) (0,1)(0.588,-0.809)(-0.951,0.309)(0.951,0.309)(-0.588,-0.809) \end{pspicture} \hfill \begin{pspicture}(-1,-1)(1,1) \pscircle(0,0){1} \psdots(0,1)(0.643,0.766)(0.866,-0.5)(0.342,-0.940)(-0.866,-0.5)(-0.985,0.174) \pspolygon(0,1)(0.643,0.766)(0.866,-0.5)(0.342,-0.940)(-0.866,-0.5)(-0.985,0.174) \pspolygon(0,1)(0.866,-0.5)(-0.866,-0.5) \pspolygon(0.643,0.766)(0.342,-0.940)(-0.985,0.174) \psline(0,1)(0.342,-0.940) \psline(0.643,0.766)(-0.866,-0.5) \psline(0.866,-0.5)(-0.985,0.174) \end{pspicture} \hfill\mbox{} \caption{Partitions of circles by straight lines}\label{fig:circles} \end{figure} shows that \eqref{eqn:a_n} now holds when $n$ is one of the numbers $1$, $2$, $3$, $4$, and $5$; but when $n=0$, then there is $1$ region, not $1/2$; and when $n=6$, there are $31$ regions, not $32$. Is there a formula for the number $a_n$ here? When we add a new point, so that there are $n+1$ points in all, then the new point will be connected to $n$ other points. Suppose we number those $n$ points with the numbers from $1$ to $n$ inclusive. Then the line going to point $j$ has $j-1$ points on one side, and $n-j$ on the other, so it crosses $(j-1)(n-j)$ lines. So this new line is divided into $(j-1)(n-j)+1$ segments, and each of these corresponds to a new region. Thus \begin{align*} a_1&=1,& a_{n+1}&=a_n+\sum_{j=1}^n\bigl((j-1)(n-j)+1\bigr); \end{align*} this is a recursive definition of the numbers $a_n$, but it is perhaps not a very attractive definition. We can rewrite the last equation as \begin{equation*} a_{n+1}=a_n+n+\sum_{j=2}^{n-1}(j-1)(n-j). \end{equation*} The sum $\sum_{j=2}^{n-1}(j-1)(n-j)$ can be understood as the number of ways to choose $3$ points out of $n$ points. Indeed, if the points are again numbered from $1$ to $n$ inclusive, then for each $j$, there are $(j-1)(n-j)$ ways to choose $i$ and $k$ so that $i2$. This claim is the so-called \emph{Fermat's Last Theorem,}% \index{Fermat's Last Theorem}% \index{theorem!Fermat's Last Th---} although Fermat did not publish a proof, and he almost certainly did not know a correct proof.} is a polynomial equation with integral coefficients. If such a solution has no \emph{integral} solutions, way to prove this is the method of \textbf{infinite descent,}% \index{infinite descent}% \index{proof!--- by infinite descent} which is attributed to Pierre de Fermat (1601--65).\footnote{In his \emph{History of Mathematics}~\cite[\S XVII.16, p. 387]{MR0234791}, Boyer writes: `Some of his theorems he [Fermat] proved by a method that he called his ``infinite descent''---a sort of inverted mathematical induction, a process that Fermat was among the first to use.'} A simple application of the method is the following. \begin{theorem} No integers solve the equation \begin{equation*} x^{2}={2}y^{2}. \end{equation*} \end{theorem} \begin{proof} Suppose $a^{2}={2}b^{2}$, and $a$ and $b$ are positive. Then $a>b$. Also, $a$ must be even. Say $a=2c$. Consequently $4c^2=2b^2$, so $b^2=2c^2$. Thus we obtain a sequence \begin{equation*} a,b,c,\dots,k,\ell,\dots, \end{equation*} where always $k^2=2\ell^2$. But we have also $a>b>c>\dotsb$, which is absurd; there is no infinite descending sequence of positive integers. Therefore no positive $a$ and $b$ exist such that $a^2=2b^2$. \end{proof} In geometric form, the theorem is that the side and diagonal of a square are \textbf{incommensurable:}% \index{incommensurable} there is no one line segment that \textbf{measures,}% \index{measure} or evenly divides, each of them. We can see this as follows, using propositions from Euclid's \emph{Elements} \cite{MR1932864}.\footnote{The method is discussed in Heath's edition of the \emph{Elements}~\cite[v.~III, p.~19]{MR17:814b}.} In Figure~\ref{fig:square}, \begin{figure}[ht] \begin{center} \psset{unit=6mm} \begin{pspicture}(-0.5,-0.5)(5.8,4.5) \psline(0,0)(4,0)(4,4)(0,4)(0,0)(4,4) \psline(1.172,1.172)(0,2.343)(4,4) \psarc[linestyle=dotted](4,4){4}{180}{225} \psline(5,1.8)(5.8,1.8) \uput[ul](0,4){$A$} \uput[ur](4,4){$B$} \uput[dr](4,0){$C$} \uput[dl](0,0){$D$} \uput[dr](1.172,1.172){$E$} \uput[l](0,2.343){$F$} \uput[u](5.4,1.8){$d$} \end{pspicture} \end{center} \caption{Incommensurability of diagonal and side}\label{fig:square} \end{figure} there is a square, $ABCD$ (constructed by I.46). On the diagonal $BD$, the distance $BE$ is marked equal to $AB$ (as by drawing a circle with center $B$, passing through $A$). The perpendicular at $E$ (constructed by I.11) meets $AD$ at $F$. The straight line $BF$ is drawn. Then triangles $ABF$ and $EBF$ are congruent, and in particular $EF=AF$ (by I.4, I.16, and I.32). Also, triangle $DEF$ is similar to $DAB$ (by VI.4, since angle $DEF$ is equal to angle $DAB$, and angle $EDB$ is common), so $DE=EF$. Suppose a straight line $G$ measures both $AB$ and $BD$. Then it measures $ED$ and $DF$, since \begin{align*} ED&=BD-AB,& DF&=AB-ED. \end{align*} The same construction can be performed with triangle $DEF$ in place of $DAB$. Since $DEa_2>a_3>\dotsb$, which again is absurd. The same argument, adjusted, gives us a way to \emph{approximate} $\sqrt2$. Suppose there are $b_1$ and $b_2$ such that \begin{equation*} \frac{b_1}{b_2}=\sqrt 2-1. \end{equation*} Then \begin{equation*} \frac{b_2}{b_1}=\sqrt 2+1=\frac{b_1}{b_2}+2=\frac{b_1+2b_2}{b_2}. \end{equation*} If we define \begin{equation}\label{eqn:bn2} b_{n+2}=b_n+2b_{n+1}, \end{equation} then by induction \begin{equation*} \frac{b_{n+1}}{b_{n+2}}=\sqrt 2-1. \end{equation*} Now however the sequence $b_1$, $b_2$, \dots, increases, so there is no obvious contradiction. But the definition~\eqref{eqn:bn2} alone yields \begin{align*} \frac{b_3}{b_2}&=2+\frac{b_1}{b_2},\\ \frac{b_4}{b_3}&=2+\frac{b_2}{b_3}=2+\cfrac1{2+\cfrac{b_1}{b_2}},\\ \frac{b_5}{b_4}&=2+\frac{b_3}{b_4}= 2+\cfrac1{2+\cfrac{b_2}{b_3}}= 2+\cfrac1{2+\cfrac1{2+\cfrac{b_1}{b_2}}}, \end{align*} and so on. If we just let $b_1=1$ and $b_2=2$, then by~\eqref{eqn:bn2} we sequence of the $b_n$ is the increasing sequence \begin{equation*} 1,2,5,12,29,70,\dots \end{equation*} Then the sequence \begin{equation*} \frac21,\frac52,\frac{12}5,\frac{29}{12},\frac{70}{29},\dots \end{equation*} of fractions converges to $\sqrt2+1$. That is, we have the following. \begin{theorem} When the sequence $b_1$, $b_2$, \dots, is defined recursively by \begin{align*} b_1&=1,& b_2&=2,& b_{n+2}&=b_n+2b_{n+1}, \end{align*} then \begin{equation}\label{eqn:lim} \lim_{n\to\infty}\frac{b_{n+1}}{b_n}=\sqrt 2+1. \end{equation} \end{theorem} \begin{proof} Considering successive differences, we have \begin{equation*} \frac{b_{n+2}}{b_{n+1}}-\frac{b_{n+1}}{b_n} =2+\frac{b_n}{b_{n+1}}-\frac{b_{n+1}}{b_n} =\frac{b_n{}^2+2b_nb_{n+1}-b_{n+1}{}^2}{b_nb_{n+1}}. \end{equation*} Replacing $n$ with $n+1$ gives \begin{align*} \frac{b_{n+3}}{b_{n+2}}-\frac{b_{n+2}}{b_{n+1}}&= \frac{b_{n+1}{}^2+2b_{n+1}b_{n+2}-b_{n+2}{}^2}{b_{n+1}b_{n+2}}\\ &=\frac{b_{n+1}{}^2+2b_{n+1}(2b_{n+1}+b_n)-(2b_{n+1}+b_n)^2}{b_{n+1}b_{n+2}}\\ &=-\frac{b_n{}^2+2b_nb_{n+1}-b_{n+1}{}^2}{b_{n+1}b_{n+2}}\\ &=-\Bigl(\frac{b_{n+2}}{b_{n+1}}-\frac{b_{n+1}}{b_n}\Bigr). \end{align*} By induction then, \begin{equation}\label{eqn:2-ind} \frac{b_{n+2}}{b_{n+1}}-\frac{b_{n+1}}{b_n}=\frac{(-1)^{n+1}}{b_nb_{n+1}}, \end{equation} since this holds when $n=1$. The sequence of products $b_nb_{n+1}$ is positive an strictly increasing; so we have \begin{gather*} \frac{b_2}{b_1}<\frac{b_3}{b_1},\\ \frac{b_2}{b_1}<\frac{b_4}{b_3}<\frac{b_3}{b_1},\\ \frac{b_2}{b_1}<\frac{b_4}{b_3}<\frac{b_5}{b_4}<\frac{b_3}{b_1},\\ \frac{b_2}{b_1}<\frac{b_4}{b_3}<\frac{b_6}{b_5}<\frac{b_5}{b_4}<\frac{b_3}{b_1}, \end{gather*} and in general \begin{equation*} \frac{b_2}{b_1}<\frac{b_4}{b_3}<\frac{b_6}{b_5}< \cdots<\frac{b_7}{b_6}<\frac{b_5}{b_4}<\frac{b_3}{b_1}. \end{equation*} A consequence of this and~\eqref{eqn:2-ind} is that the sequence of fractions $b_{n+1}/b_n$ must be a \textsl{Cauchy sequence.}% \index{Cauchy sequence} The limit is $\sqrt2+1$, since \begin{align*} \frac{b_{n+2}}{b_{n+1}}<\sqrt2+1 &\iff\Bigl(\frac{b_{n+2}}{b_{n+1}}-1\Bigr)^2<2\\ &\iff\Bigl(\frac{b_n}{b_{n+1}}+1\Bigr)^2<2\\ &\iff\frac{b_n}{b_{n+1}}<\sqrt2-1\\ &\iff\frac{b_{n+1}}{b_n}>\sqrt2+1.\qedhere \end{align*} \end{proof} The limit equation~\eqref{eqn:lim} is written more suggestively as \begin{equation*} \sqrt{2}+{1}= {2}+ \cfrac{1}{{2}+ \cfrac{1}{{2}+\cfrac{1}{{2}+\cfrac{1}{{2}+\cfrac{1}{\ddots}}}}}. \end{equation*} \chapter{Numbers}\label{ch:foundations} \section{The natural numbers}\label{sect:N} Theorems about natural numbers have been known for thousands of years. Some of these theorems come down to us in Euclid's \emph{Elements} \cite{MR1932864}, for example, or Nicomachus's \emph{Introduction to Arithmetic} \cite{Nicomachus}, which were referred to in the last chapter. Certain underlying assumptions on which the proofs of these theorems are based were apparently not worked out until more recent centuries. It turns out that all theorems about the natural numbers are logical consequences of the Axiom below. The Axiom lists five conditions that the natural numbers meet. Richard Dedekind published these conditions in 1888 \cite[II, \S71, p.~67]{MR0159773}. In 1889, Giuseppe Peano \cite[\S1, p.~94]{Peano}\nocite{MR0209111} repeated them in a more symbolic form, along with some logical conditions, making nine conditions in all, which he called axioms. Of these, the five specifically number-theoretic conditions have come to be known as the \textbf{Peano Axioms.}% \index{Peano axioms} The foundations of number-theory are often not well understood, even today. Some books give the impression that all theorems about natural numbers follow from the so-called `Well Ordering Principle' (Theorem~\ref{thm:wo}). Others suggest that the possibility of definition by recursion (Theorem~\ref{thm:rec}) can be proved by induction (part~\eqref{part:ind} of the Axiom) alone. These are mistakes about the foundations of number-theory. They are perhaps not really mistakes about number-theory itself; still, they are mistakes, and it is better not to make them. This is a reason why I have written this chapter. An admirable development of the material in this chapter and more is found in Edmund Landau's book \emph{Foundations of Analysis: The Arithmetic of Whole, Rational, Irrational, and Complex Numbers: A Supplement to Text-Books on the Differential and Integral Calculus}~\cite{MR12:397m}. In the present chapter, \emph{when proofs of lemmas and theorems here are not supplied, I have left them to the reader as exercises.} An expression like `$f\colon A\to B$' is to be read as the statement `$f$ is a function from $A$ to $B$.' This means $f$ is a certain kind of subset of the Cartesian product $A\times B$, namely a subset that, for each $a$ in $A$, has exactly one element of the form $(a,b)$; then one writes $f(a)=b$. The function $f$ can also be written as $x\mapsto f(x)$. \begin{axdef} The set of \textbf{natural numbers,}% \index{natural number}% \index{number!natural ---} denoted by \begin{equation*} \N, \end{equation*} meets the following five conditions. \begin{compactenum} \item\label{part:zero} There is a \textbf{first}% \index{first natural number}% \index{number!first natural ---, one} natural number, called $1$ (\textbf{one}% \index{one}% \index{number!one}). \item\label{part:s} Every $n$ in $\N$ has a unique \textbf{successor,}% \index{successor}% \index{number!successor} denoted (for now) by $\scr n$. \item\label{part:not} The first natural number is not a successor: if $n\in\N$, then $\scr n\neq1$. \item\label{part:inj} Distinct natural numbers have distinct successors: if $n\in\N$ and $m\in\N$ and $n\neq m$, then $\scr n\neq\scr m$. \item\label{part:ind} Proof by \textbf{induction}% \index{induction}% \index{proof!--- by induction} is possible: Suppose $A\included\N$, and two conditions are met, namely \begin{compactenum} \item the \textbf{base condition:}% \index{base of induction} $1\in A$, and \item the \textbf{inductive condition:}% \index{inductive condition}% \index{inductive hypothesis} if $n\in A$ (the \textbf{inductive hypothesis}), then $\scr n\in A$. \end{compactenum} Then $A=\N$. \end{compactenum} The natural number $\scr 1$ is denoted by $2$; the number $\scr 2$, by $3$; \&c. \end{axdef} \begin{remark} Again, the five conditions satisfied by $\N$ are the \emph{Peano axioms.} Parts~\eqref{part:not}, \eqref{part:inj} and~\eqref{part:ind} of the axiom are conditions concerning a set with a first element and an operation of succession. For each of those conditions, there is an example of such a set that meets that condition, but not the others. In short, the three conditions are logically independent. \end{remark} \begin{lemma} Every natural number is either $1$ or a successor. \end{lemma} \begin{proof} Let $A$ be the set comprising every natural number that is either $1$ or a successor. In particular, $1\in A$, and if $n\in A$, then (since it is a successor) $\scr n\in A$. Therefore, by induction, $A=\N$. \end{proof} \begin{theorem}[Recursion]\label{thm:rec} Suppose a set $A$ has an element $b$, and $f\colon A\to A$. Then there is a \emph{unique} function $g$ from $\N$ to $A$ such that \begin{compactenum} \item $g(1)=b$, and \item $g(\scr n)=f(g(n))$ for all $n$ in $\N$. \end{compactenum} \end{theorem} \begin{proof} The following is only a sketch. One must prove existence and uniqueness of~$g$. Assuming existence, one can prove uniqueness by induction. To prove existence, let $\mathcal S$ be the set of subsets $R$ of $\N\times A$ such that \begin{compactenum} \item if $(1,c)\in R$, then $c=b$; \item if $(\scr n,c)\in R$, then $(n,d)\in R$ for some $d$ such that $f(d)=c$. \end{compactenum} Then $\bigcup\mathcal S$ is the desired function $g$. \end{proof} \begin{remark} In its statement (though not the proof), the Recursion Theorem assumes only parts~\eqref{part:zero} and~\eqref{part:s} of the Axiom. The other parts can be proved as consequences of the Theorem. Recursion is a method of \emph{definition;} induction is a method of \emph{proof.} There are sets (with first elements and successor-operations) that allow proof by induction, but not definition by recursion. In short, induction is logically weaker than recursion. \end{remark} \begin{definition}[Addition] For each $m$ in $\N$, the operation $x\mapsto m+x$ on $\N$ is the function $g$ guaranteed by the Recursion Theorem when $A$ is $\N$ and $b$ is $m$ and $f$ is $x\mapsto\scr x$. That is, \begin{align*} m+1&=\scr m,& m+\scr n&=\scr{m+n}. \end{align*} \end{definition} \begin{lemma} For all $n$ and $m$ in $\N$, \begin{compactenum} \item $1+n=\scr n$; \item $\scr m+n=\scr{m+n}$. \end{compactenum} \end{lemma} \begin{theorem}\label{thm:add} For all $n$, $m$, and $k$ in $\N$, \begin{compactenum} \item $n+m=m+n$; \item $(n+m)+k=n+(m+k)$; \end{compactenum} \end{theorem} \begin{remark} It is possible to prove by induction alone that there is a unique operation of addition satisfying the definition and Theorem~\ref{thm:add}. \end{remark} \begin{definition}[Multiplication] For each $m$ in $\N$, the operation $x\mapsto m\cdot x$ on $\N$ is the function $g$ guaranteed by the Recursion Theorem when $A$ is $\N$ and $b$ is $1$ and $f$ is $x\mapsto x+m$. That is, \begin{align*} m\cdot1&=m,& m\cdot(n+1)&=m\cdot n+m. \end{align*} \end{definition} \begin{lemma} For all $n$ and $m$ in $\N$, \begin{compactenum} \item $1\cdot n=n$; \item $(m+1)\cdot n=m\cdot n+n$. \end{compactenum} \end{lemma} \begin{theorem}\label{thm:mul} For all $n$, $m$, and $k$ in $\N$, \begin{compactenum} \item $n\cdot m=m\cdot n$; \item $n\cdot(m+k)=n\cdot m+n\cdot k$; \item $(n\cdot m)\cdot k=n\cdot (m\cdot k)$; \end{compactenum} \end{theorem} \begin{remark} As with addition, so with multiplication, one can prove by induction alone that there is a unique operation satisfying the definition and Theorem~\ref{thm:mul}. However, the next theorem requires also parts \eqref{part:not}--\eqref{part:inj} of the Axiom. \end{remark} \begin{theorem}[Cancellation] For all $n$, $m$, and $k$ in $\N$, \begin{compactenum} \item if $n+k=m+k$, then $n=m$; \item if $n\cdot k=m\cdot k$, then $n=m$. \end{compactenum} \end{theorem} \begin{definition}[Exponentiation] For each $m$ in $\N$, the operation $x\mapsto m^x$ on $\N$ is the function $g$ guaranteed by the Recursion Theorem when $A$ is $\N$ and $b$ is $m$ and $f$ is $x\mapsto x\cdot m$. That is, \begin{align*} m^1&=m,& m^{n+1}&=m^n\cdot m. \end{align*} \end{definition} \begin{theorem} For all $n$, $m$, and $k$ in $\N$, \begin{compactenum} \item $n^{m+k}=n^m\cdot n^k$; \item $(n\cdot m)^k=n^k\cdot m^k$; \item $(n^m)^k=n^{m\cdot k}$. \end{compactenum} \end{theorem} \begin{remark} In contrast with addition and multiplication, exponentiation requires more than induction for its existence. \end{remark} \begin{definition}[Ordering] If $n,m\in\N$, and $m+k=n$ for some $k$ in $\N$, then this situation is denoted by $m0$, that is, if $a\in\N$; but $a$ is \textbf{zero,}% \index{zero} if $a=0$, and $a$ is \textbf{negative,}% \index{negative} if $a<0$. \section{The rational numbers} It is also useful in number theory to be aware that integers are \textbf{rational numbers.} In order to define these precisely, it is useful to begin (as one does in school) with the \textbf{positive rational numbers.} These compose the quotient \begin{equation*} \N\times\N/\mathord{\approx}, \end{equation*} where $\approx$ is the equivalence relation defined by \begin{equation*} (a,b)\approx(x,y)\iff a\cdot y=b\cdot x. \end{equation*} The equivalence class of $(a,b)$ is denoted by \begin{equation*} \frac ab \end{equation*} or $a/b$. Let us denote the set of positive rational numbers by \begin{equation*} \Qp. \end{equation*} On this set, one shows that the following are valid definitions: \begin{align*} \frac ab+\frac xy&=\frac{ay+bx}{by},& \frac ab\cdot\frac xy&=\frac{ab}{xy},& \frac ab<\frac xy&\iff ayk$ and $m>k$, then \begin{equation*} \size{a_n-a_m}<\epsilon. \end{equation*} Then $\R$ itself is also complete in this sense. The field of complex numbers also has the convenient property of being \textbf{algebraically closed:}% \index{algebraic} it contains a solution of every polynomial equation \begin{equation}\label{eqn:alg} a_0+a_1x+\dotsb+a_{n-1}x^{n-1}+x^n=0, \end{equation} for every $n$ in $\N$, where of course the coefficients $a_k$ range over $\C$. But there are other algebraically closed fields. The field $\Q$ is \textbf{countable,}% \index{countable} that is, there is a bijection between $\Q$ and $\N$. The same is not true for $\R$ or $\C$: they are \textbf{uncountable.}% \index{uncountable} If we select from $\C$ the solutions of the equations~\eqref{eqn:alg} such that the coefficients are \emph{rational,} the result is the set of \textbf{algebraic numbers.} This set is a countable algebraically closed subfield of $\C$. Every equation $a+bx=0$, where $a$ and $b$ are integers and $b\neq0$, has a solution in $\Q$, namely $-a/b$ (that is, $-ab^{-1}$). In particular, there is a solution when $b=1$; but then the solution is just $-a$, an integer. More generally, if the coefficients in~\eqref{eqn:alg} are integers, then a solution to the equation is called an \textbf{algebraic integer.} In particular, $\sqrt 2$ is an algebraic integer, being a solution of $x^2-2=0$. The algebraic integers are the subject of \textbf{algebraic number theory;} so we have had a taste of this in \S\ref{sect:incomm}. The only algebraic integers in $\Q$ are the usual integers---which in this context may be called \textbf{rational integers.} The study of $\R$ and $\C$ is \textbf{analysis.} There is a part of number theory that makes use of analysis; this is \textbf{analytic number theory.} We shall not try to do it here, but if one does prove the Prime Number Theorem (Theorem~\ref{thm:PNT}) for example, then the \textbf{Gamma function}% \index{Gamma function} may be useful: this is the function $\Gamma$ given by \begin{equation*} \Gamma(x)=\int_{0}^{\infty}\me^{-t}t^{x-1}\dee x \end{equation*} when $x\geq1$. You can show that $\Gamma(n+1)=n\Gamma(n)$, and $\Gamma(1)=1$, so that $G(n+1)=n!$. Our subject is mainly \textbf{elementary number theory.} This means not that the subject is easy, but that our integers are just the rational integers, and we shall not use analysis. However, the proof of Bertrand's Postulate in \S\ref{sect:B} gives a taste of analysis.\footnote{For an overview of algebraic numbers, analytic number theory, and other areas of mathematics, an excellent print reference is \emph{The Princeton Companion to Mathematics,} edited by Timothy Gowers with June Barrow-Green and Imre Leader~\cite{MR2467561}.} \chapter{Divisibility}\label{ch:divisibility} \section{Division} Henceforth minuscule letters will usually denote integers. If $n$ is such, let the set $\{nx\colon x\in\Z\}$ be denoted by $\Z n$ or $n\Z$ or \begin{equation*} (n). \end{equation*} To give it a name, we may call $(n)$ the \textbf{ideal}\index{ideal}\footnote{In the original terminology, $(n)$ was an \emph{ideal number.}} of $\Z$ generated by $n$. Note that \begin{equation*} (-n)=(n). \end{equation*} Moreover, \begin{equation*} a\in(n)\iff (a)\included(n). \end{equation*} It is not strictly necessary to introduce ideals, but they may clarify some arguments. By definition, if $a\in(n)$, that is, if $a=nx$ for some integer $x$, then $n$ \textbf{divides}% \index{divides, divisor} $a$, or $n$ is a \textbf{divisor} of $a$; this situation is denoted by \begin{equation*} n\divides a. \end{equation*} Then the following holds, simply because $\Z$ is a commutative ring in the sense of \S\ref{sect:integers}. \begin{theorem}\label{thm:div} In $\Z$: \begin{gather}\notag a\divides {0},\\\notag {0}\divides a\iff a={0},\\\notag 1\divides a,\\\notag a\divides a,\\\notag a\divides b\And b\divides c\implies a\divides c,\\\notag a\divides b\And c\divides d\implies ac\divides bd,\\\label{eqn:bx} a\divides b\implies a\divides bx,\\\label{eqn:b+c} a\divides b\And a\divides c\implies a\divides b+c. \end{gather} \end{theorem} In particular, if $a\divides b$, then both $a$ and $-a$ divide both $b$ and $-b$. Every divisor of an integer $b$ is a \textbf{proper} divisor if it is not $\pm b$ (this notion will be useful when we discuss \textsl{prime numbers} in Chapter~\ref{ch:primes}). We have an additional property because $\Z$ is an \emph{ordered} commutative ring in which every positive element is $1$ or greater; the following does not hold in $\Q$ or $\R$.\footnote{\label{n:Z[X]}It does hold in other ordered commutative rings, such as $\Z[X]$, the ring of polynomials in a single variable $X$ with integer coefficients, ordered so that $X$ is greater than every constant polynomial.} \begin{theorem}\label{thm:div-ord} In $\Z$, \begin{equation*} a\divides b\And b\neq{0}\implies \size a\leq\size b. \end{equation*} In particular, \begin{equation*} a\divides b\And b\divides a\implies a=\pm b. \end{equation*} \end{theorem} \begin{proof} If $a\divides b$, and $b\neq0$, then $n\cdot\size a=\size b$ for some positive $n$, so $1\leq n$ and hence $\size a\leq n\cdot\size a=\size b$. \end{proof} We have now shown, in effect: \begin{theorem} The relation $\divides$ of divisibility is an \textbf{ordering}\index{ordering} of $\N$ that is refined by the linear ordering $\leq$, that is, if $k$, $m$, and $n$ are in $\N$, then \begin{gather*} n\divides n,\\ m\divides n\And n\divides m\implies m=n,\\ k\divides m\And m\divides n\implies k\divides n,\\ m\divides n\implies m\leq n. \end{gather*} \end{theorem} Ordered sets can be depicted in so-called \textbf{Hasse diagrams.}% \index{Hasse diagram} Consider for example the positive divisors of $60$, namely $1$, $2$, $3$, $4$, $5$, $6$, $10$, $12$, $15$, $20$, $30$, and $60$: these twelve numbers can be arranged as in Figure~\ref{fig:60}. \begin{figure}[ht] \centering \psset{unit=2mm} \begin{pspicture}(-12,-12)(12,12) \pspolygon(0,-12)(-12,0)(-2,6)(10,-6) \psline(-6,-6)(4,0) \psdots[linecolor=white,dotsize=4pt 4](-1,-3)(7,-3)(1,3)(-7,3) \pspolygon(0,12)(12,0)(2,-6)(-10,6) \psline(-12,0)(-10,6) \psline(0,-12)(2,-6) \psline(12,0)(10,-6) \psline(6,6)(-4,0) \psline(0,12)(-2,6) \psline(-6,-6)(-4,0) \psline(6,6)(4,0) \rput(0,12){\psframebox*[fillstyle=solid]{$60$}} \rput(0,-12){\psframebox*[fillstyle=solid]{$1$}} \rput(6,6){\psframebox*[fillstyle=solid]{$30$}} \rput(-6,-6){\psframebox*[fillstyle=solid]{$2$}} \rput(-2,6){\psframebox*[fillstyle=solid]{$20$}} \rput(2,-6){\psframebox*[fillstyle=solid]{$3$}} \rput(-10,6){\psframebox*[fillstyle=solid]{$12$}} \rput(10,-6){\psframebox*[fillstyle=solid]{$5$}} \rput(12,0){\psframebox*[fillstyle=solid]{$15$}} \rput(-12,0){\psframebox*[fillstyle=solid]{$4$}} \rput(4,0){\psframebox*[fillstyle=solid]{$10$}} \rput(-4,0){\psframebox*[fillstyle=solid]{$6$}} \end{pspicture} \caption{Divisors of $60$}\label{fig:60} \end{figure} Here a line is drawn from a number $a$ up to a number $b$ if $a\divides b$, but there is no $c$ distinct from $a$ and $b$ such that $a\divides c$ and $c\divides b$. In general, $a\divides b$ if and only if there is a path upwards from $a$ to $b$. \section{Congruence}\label{sect:cong} If $a-b\in(n)$, then we may also write \begin{equation}\label{eqn:mod} a\equiv b\pmod n \end{equation} or $a\equiv b\pod n$, saying $a$ and $b$ are \textbf{congruent}% \index{congruent numbers}% \index{number!congruent ---s} with respect to the \textbf{modulus}% \index{modulus, \emph{modulo}} $n$, or $a$ and $b$ are congruent \textbf{\emph{modulo}} $a$; also $b$ is a \textbf{residue}% \index{residue} of $a$, and $a$ is a residue of $b$, \emph{modulo} $n$.\footnote{The notation of~\eqref{eqn:mod} is introduced by Johann Carl Friedrich Gauss% \index{Gauss} (1777--1855) in \P2 of his \emph{Disquisitiones Arithmeticae}~\cite{Gauss}, first published in 1801. Gauss notes that Legendre uses the same sign for both equality and congruence, because they are analogous concepts. Gauss writes in Latin, and Latin nouns, like Turkish nouns, have \emph{cases.} In particular, the Latin noun \emph{modulus,} meaning literally `small measure', has the cases \emph{modulum, moduli, modulo, modulo,} corresponding respectively (albeit roughly) to the Turkish \emph{mod\"ul\"u, mod\"ul\"un, mod\"ule, mod\"ulden.} However, Gauss does not use a form like `\emph{modulo} $5$', at least not in the first two paragraphs of the \emph{Disquisitiones}; he says instead `\emph{secundum modulum} 5', that is, with respect to the modulus 5, or in Turkish \emph{$5$ mod\"ul\"une g\"ore.} (I took Gauss's Latin text from \url{http://resolver.sub.uni-goettingen.de/purl?PPN235993352}, December 7, 2010; the link was in the Wikipedia article on the \emph{Disquisitiones.})} If the modulus $n$ is understood, we might write simply \begin{equation*} a\equiv b. \end{equation*} Congruence with respect to a given modulus is an equivalence-relation. The congru\-ence-class of $a$ \emph{modulo} $n$ is \begin{equation*} \{x\in\Z\colon a-x\in(n)\}. \end{equation*} If $n={0}$, then congruence \emph{modulo} $n$ is equality. In any case, congruence \emph{modulo} $n$ is the same as congruence \emph{modulo} $-n$. So we usually need only be concerned with positive moduli.\footnote{Gauss writes in a footnote to his \P1, `The modulus must obviously be taken \emph{absolutely,} i.e. without sign.' This suggests to me the picture in which $-5$ is `really' $5$, from a special point of view.} \begin{lemma} For every positive modulus $n$, for every integer $a$, distinct elements of the $n$-elemment set $\{a,a+1,\dots,a+n-1\}$ are incongruent. \end{lemma} \begin{proof} If $i$ and $j$ are distinct elements of the set, then $0<\size{i-j}b$. This principle is used by Archimedes (c.~287--212 \textsc{bce}) to show, for example, that the surface of a sphere is equal to a circle of twice the radius \cite{MR2093668}. An example of a nonarchimedean ordered commutative ring is $\Z[X]$, defined in note~\ref{n:Z[X]} on page~\pageref{n:Z[X]} above. We can characterize $\Z$ as the unique archimedean ordered commutative ring with no positive elements less than $1$.} \begin{lemma} For every positive modulus $n$, every integer has a unique residue in $\{0,1,\dots,n-1\}$. \end{lemma} \begin{proof} For any integer $a$, we just compute \begin{gather*} \Bigl[\frac an\Bigr]\leq\frac an<\Bigl[\frac an\Bigr]+1,\\ \frac an-1<\Bigl[\frac an\Bigr]\leq\frac an,\\ 1>\frac an-\Bigl[\frac an\Bigr]\geq0,\\ n>a-n\Bigl[\frac an\Bigr]\geq0. \end{gather*} So $a-n[a/n]$ belongs to the desired set; and it is an integer congruent to $a$. \end{proof} The following theorem is basically a restatement of the last lemma. It is called the Division Algorithm, though it is not really an algorithm; it is the observation that finding a quotient (with remainder) of one integer after division by a nonzero integer is always \emph{possible.} So-called \emph{long division} is an algorithm for doing this that is learned in school. \begin{theorem}[Division Algorithm]\label{thm:div-alg} For every positive integer $q$, for every integer $a$, there are unique integers $k$ and $r$ such that \begin{align*} a&=kq+r,&0\leq ra_2\geq0$. There are unique sequences $(a_n\colon n\in\N)$ and $(q_n\colon n\in\N)$ such that, if $a_{n+1}\neq{0}$, then \begin{align} a_n&=a_{n+1}\cdot q_n+a_{n+2},&{0}\leq a_{n+2}&arijm'os}) as a number `that is measured by a unit alone.' But a \emph{number} (\Gk{>arijm'os}) here is `a multitude composed of units.' A multitude is more than one. Thus a unit is \emph{not} a number for Euclid; it is just a unit, out of which numbers can be created. If, according to Euclid, a prime number is measured---or we might say \emph{divided}---only by a unit, then it seems that no number measures \emph{itself.} However, in Proposition 2 (mentioned above on page~\pageref{VII.2} in \S\ref{sect:gcd}), Euclid mentions that a number \emph{does} measure itself. So there seems to be some confusion in Euclid's text as we have it today. Our formulation of Euclid's definition is that a positive integer is prime if it has exactly one \emph{proper} positive divisor, which must then be $1$. Having \emph{no} proper divisors, $1$ is not prime; but $2$ is prime. More generally, $b$ is prime if and only if $b>1$ and \begin{equation*} a>0\And a\divides b\implies a\in\{1,b\}. \end{equation*} By Theorem~\ref{thm:div-ord}, an alternative formulation of this last condition is \begin{equation*} 11$, then the least of the divisors of $n$ that are greater than $1$ must be prime by Theorem~\ref{thm:div-ord}. \end{proof} A positive integer with a proper divisor that is greater than $1$ is \textbf{composite.}% \index{composite number}% \index{number!composite ---} So $1$ is neither prime nor composite, but every integer that is greater than $1$ is prime or composite, but not both. \begin{theorem}[Euclid, VII.30]\label{thm:Euclid} \index{theorem!Euclid's Th---}% \index{Euclid!---'s Theorem} If $p\divides ab$, then either $p\divides a$ or $p\divides b$. \end{theorem} \begin{proof} If $p\ndivides a$, then $\gcd(a,p)=1$, so $p\divides b$ by Theorem~\ref{thm:a|bc}. \end{proof} \begin{corollary} If $p\divides a_1\dotsb a_n$, where $n\geq1$, then $p\divides a_k$ for some $k$. \end{corollary} \begin{proof} Use induction. The claim is trivially true when $n=1$. Suppose it is true when $n=m$. Say $p\divides a_1\dotsb a_{m+1}$. By the theorem, we have that $p\divides a_1\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$, assuming it holds when $n=m$. Therefore the claim does indeed hold for all $n$. \end{proof} The following appears in Gauss's \emph{Disquisitiones Arithmeticae} as \P16; Hardy and Wright~\cite[p.~10]{MR568909} judge that to be the first explicit statement of the theorem. \begin{theorem}[Fundamental Theorem of Arithmetic]\label{thm:FTA}% \index{Fundamental Theorem of Arithmetic}% \index{theorem!Fundamental Th--- of Arithmetic} Every positive integer is uniquely a product \begin{equation*} p_{1}\dotsm p_n \end{equation*} of primes, where \begin{equation*} p_{1}\leq\dotsb\leq p_n. \end{equation*} \end{theorem} \begin{proof} Trivially, $1=p_1\dotsm p_n$, where $n=0$. Suppose $m>1$, and let $p_1$ be its least prime divisor (which exists by Theorem~\ref{thm:prime-div}). If $m=p_1$, we are done; otherwise, the least divisor of $m/p_1$ that is greater than $1$ is a prime, $p_2$. If $m=p_1p_2$, we are done; otherwise, the least divisor of $m/p_1p_2$ that is greater than $1$ is a prime $p_3$. Continuing thus, we get an increasing sequence $p_1,p_2,p_3,\dots$ of primes, where $p_1\dotsm p_k\divides m$. Since \begin{equation*} m>\frac m{p_{1}}>\frac m{p_{1}p_{2}}>\dotsb, \end{equation*} the sequence of primes must terminate by the Well Ordering Principle, and for some $n$ we have $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$ by the corollary to Theorem~\ref{thm:Euclid}, 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} Alternatively, every positive integer is uniquely a product \begin{equation*} p_1{}^{a_1}\dotsm p_n{}^{a_n}, \end{equation*} that is, \begin{equation*} \prod_{k=1}^np_k{}^{a_k}, \end{equation*} where $p_1<\dotsb1$, to the value denoted by $\rzeta(s)$; this is the \textbf{Riemann zeta function}% \index{Riemann zeta function} of $s$. Then the product also converges, in the sense that \begin{equation*} \lim_{n\to\infty}\prod_{p\leq n}\frac1{1-1/p^s}=\rzeta(s). \end{equation*} Hardy and Wright~\cite[p.~246]{MR568909} describe~\eqref{eqn:rzeta} as `an analytical expression of the fundamental theorem of arithmetic.' \section{Bertrand's Postulate}\label{sect:B} We shall prove one result on the distribution of primes, namely the so-called Bertrand's Conjecture, Theorem~\ref{thm:B} below. The proof does use a bit of analysis, though this could be eliminated.\footnote{The proof here is based on that of Hardy and Wright~\cite[\S22.3]{MR568909}, who attribute it to Paul Erd\H os~\cite{Erdos}. Note that Erd\H os's paper appeared in 1932, and Erd\H os was born in 1913. An earlier proof, from 1919, is due to Srinivasa Ramanujan~\cite{Ramanujan}; this proof is very short (2 pages), but makes use of the Gamma function\index{Gamma function} (defined in \S\ref{sect:other}) and the so-called \textsl{Stirling's approximation}% \index{Stirling's approximation} to it. Hardy and Wright attribute the earliest proof of Bertrand's Postulate to Tchebyshef in 1850.} given an arbitrary positive real number $x$, we define \begin{equation*} \mtheta(x)=\sum_{p\leq x}\log p. \end{equation*} Here of course $\log x$ is the \textbf{natural logarithm}% \index{natural logarithm}% \index{logarithm} of $x$, that is, \begin{equation*} \log x=\int_1^x\frac{\mathrm dt}t. \end{equation*} So $\mtheta(x)=\log\prod_{p\leq x}p$. For example, $\mtheta(\mpi)=\mtheta(3)=\log 2+\log 3=\log 6$. If $x<2$, then $\mtheta(x)=0$. We could work with $\me^{\mtheta(x)}$ instead, which is an integer if $x$ is; this is the only case we need consider; but there is no harm in giving a more general treatment. \begin{lemma} For all positive real numbers $x$, \begin{equation*} \mtheta(x)<2x\log 2. \end{equation*} \end{lemma} \begin{proof} It is enough to prove the claim when $x$ is a positive integer $n$. We shall use strong induction. We have \begin{equation*} \mtheta(2m)=\mtheta(2m-1), \end{equation*} so the claim holds when $n$ is an \emph{even} positive integer, provided it holds for lesser positive integers $n$. We now show that the claim holds when $n$ is an \emph{odd} positive integer, provided it holds for lesser positive integers $n$. We have \begin{align*} \mtheta(2m+1) &=\mtheta(2m+1)-\mtheta(m+1)+\mtheta(m+1)\\ &=\sum_{m+1\frac{4n^2}9=\frac{2n}9\cdot2n>2n \end{equation*} and hence $[2n/p^2]=0$. Therefore $k(p)=0$. We have now \begin{equation*} \binom{2n}n=\prod_{p\leq2n/3}p^{k(p)}. \end{equation*} Also, by the earlier lemma, \begin{equation*} \sum_{p\divides\binom{2n}n}\log p\leq\sum_{p\leq2n/3}\log p=\mtheta(2n/3)\leq\frac{4n}3\log 2. \end{equation*} In the series expansion \eqref{eqn:k(p)} for $k(p)$, each term $[2n/p^j]-2[n/p^j]$ is $0$ if $[2n/p^j]$ is even, and $1$ if $[2n/p^j]$ is odd. Also the term is $0$ if $p^j>2n$, that is, $j>\log(2n)/\log p$. This then is a bound for $k(p)$, that is, \begin{equation}\label{eqn:k(p)<} k(p)\leq\frac{\log(2n)}{\log p}. \end{equation} Therefore, if $k(p)\geq2$, then \begin{equation*} 2\log p\leq k(p)\log p\leq\log(2n), \end{equation*} so in particular $p\leq\sqrt{(2n)}$. That is, $\sqrt{(2n)}$ is a bound on the number of $p$ such that $k(p)\geq2$. By the bound \eqref{eqn:k(p)<} on $k(p)$ itself, we have now \begin{equation*} \sum_{k(p)\geq2}k(p)\log p \leq\sum_{k(p)\geq2}\log(2n) \leq\sqrt{(2n)}\log(2n). \end{equation*} Therefore \begin{align*} \log\binom{2n}n &=\sum_{k(p)=1}\log p+\sum_{k(p)\geq2}k(p)\log p\\ &\leq\sum_{p\divides\binom{2n}n}\log p+\sqrt{(2n)}\log(2n)\\ &\leq\frac{4n}3\log 2+\sqrt{(2n)}\log(2n). \end{align*} Also, \begin{equation*} 2^{2n}=\sum_{j=0}^{2n}\binom{2n}j=2+\sum_{j=1}^{2n-1}\binom{2n}j\leq2n\binom{2n}n. \end{equation*} Taking logarithms yields \begin{align*} 2n\log 2 &\leq\log(2n)+\log\binom{2n}n\\ &\leq\log(2n)+\frac{4n}3\log 2+\sqrt{(2n)}\log(2n), \end{align*} which gives \begin{equation}\label{eqn:2n3} \frac{2n}3\log2\leq\bigl(1+\sqrt{(2n)}\bigr)\log(2n). \end{equation} Now, $\log x$ grows more slowly than any power of $x$; so the last inequality should fail if $n$ is large enough. We complete the proof by showing that the inequality fails when, as we have assumed, $n\geq2^9$. To this end, we define \begin{equation*} \zeta=\frac{\log n-\log2^9}{\log 2^{10}}=\frac{\log n-9\log 2}{10\log2}, \end{equation*} so that $1+\zeta=\log(2n)/10\log 2$ and $2n=2^{10(1+\zeta)}$. From the inequality \eqref{eqn:2n3}, we have now \begin{gather*} 2n\log 2\leq3\bigl(1+\sqrt{(2n)}\bigr)\log(2n),\\ 2^{10(1+\zeta)}\log2\leq3(1+2^{5(1+\zeta)})\cdot10(1+\zeta)\log2,\\ 2^{10(1+\zeta)}\leq30(1+2^{5(1+\zeta)})(1+\zeta),\\ 2^{5(1+\zeta)}\leq30(2^{-5(1+\zeta)}+1)(1+\zeta). \end{gather*} Since $\zeta>0$, we have \begin{align*} 2^{5\zeta} &\leq\frac{2^5-2}{2^5}(2^{-5(1+\zeta)}+1)(1+\zeta)\\ &\leq(1-2^{-4})(1+2^{-5})(1+\zeta)\\ &\leq1+\zeta. \end{align*} But this cannot be, since \begin{equation*} 2^{5\zeta}=\me^{5\zeta\log2}\geq1+5\zeta\log2>1+\zeta \end{equation*} because of the series expansion $\me^x=\sum_{j=0}^{\infty}x^j/j!$. \end{proof} Some further theorems about the distribution of primes are stated without their proofs in Appendix~\ref{ch:unproved}. \chapter{Computations with congruences} \section{Exponentiation}\label{sect:exp} Computing powers with respect to a modulus can be achieved by successively squaring and taking residues. This is justified by Theorem~\ref{thm:+.mod-n} on page~\pageref{thm:+.mod-n}. For example, with respect to the modulus $43$, to compute $35^{14}$, we can first note $35\equiv-8$, so \begin{equation*} 35^{14}\equiv(-8)^{14}\equiv(-1)^{14}\cdot 8^{14}\equiv 8^{14}. \end{equation*} Also, $14=8+4+2=2^3+2^2+2^1$, so $8^{14}=8^8\cdot8^4\cdot8^2$; and \begin{align*} 8^2&=64\equiv21,& 21^2&=441\equiv11,& 11^2&=121\equiv-8, \end{align*} so that \begin{equation*} 35^{14}\equiv-8\cdot11\cdot21 \equiv-88\cdot21 \equiv-2\cdot21 \equiv-44\equiv1. \end{equation*} \section{Inversion}\label{sect:inversion} A special case of Theorem~\ref{thm:+.mod-n} is the implication \begin{equation}\label{eqn:abn} a\equiv b\pmod n\implies ac\equiv bc\pmod n. \end{equation} The converse fails, because, for example, possibly $c\equiv 0\pod n$. Even if this case is excluded, the converse still fails: \begin{align}\label{eqn:1410} 1\cdot4&\equiv10\cdot 4\pmod 6,& 1&\not\equiv10\pmod 6. \end{align} The reason why we cannot cancel $4$ here is that $4$ and $6$ have a nontrivial common divisor, in this case $2$. %We have $1\cdot4\equiv10\cdot 4\pmod 2$ (since both sides are %congruent to $0$), but $1\not\equiv10\pmod2$. The converse of~\eqref{eqn:abn} does hold if $c$ and $n$ are co-prime: \begin{theorem}\label{thm:-->inv} If $\gcd(c,n)=1$, then \begin{equation*} ac\equiv bc\bmod n\implies a\equiv b\bmod n. \end{equation*} \end{theorem} \begin{proof} The claim is a restatement of Theorem~\ref{thm:a|bc} on page~\pageref{thm:a|bc}. \end{proof} Hence, considering~\eqref{eqn:1410} again, since $1\cdot4\equiv10\cdot4\pod 3$, we have \begin{equation*} 1\equiv10\pmod 3. \end{equation*} The general result is the following: \begin{theorem} For all positive moduli $n$, for all integers $a$, $b$, and $c$, \begin{equation*} ac\equiv bc\bmod n\iff a\equiv b\bmod \frac n{\gcd(c,n)}. \end{equation*} \end{theorem} \begin{proof} Let $d=\gcd(c,n)$. Then $\gcd(c/d,n/d)=1$ by Theorem~\ref{thm:gcd-div}. Hence \begin{align*} ac\equiv bc\bmod n &\implies\frac{ac}d\equiv\frac{bc}d\bmod{\frac nd}\\ &\implies a\equiv b\bmod{\frac nd} \end{align*} by the last theorem. 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.\qedhere \end{align*} \end{proof} For example, $6x\equiv 6\pod 9\iff x\equiv 1\pod 3$. A longer problem is to solve \begin{equation*} 70x\equiv18\pmod{134}. \end{equation*} This reduces to \begin{equation}\label{eqn:70} 35x\equiv9\pmod{67}, \end{equation} and solutions of this correspond to solutions to the Diophantine equation \begin{equation}\label{eqn:35,67} 35x+67y=9. \end{equation} By B\'ezout's Lemma (the corollary to Theorem~\ref{thm:gcd} on page~\pageref{thm:gcd}), this is soluble if and only if $\gcd(35,67)\divides9$. We find $\gcd(35,67)$ by 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$. To find the solutions to~\eqref{eqn:35,67}, or rather to $35x+67y=1$, we rearrange the computations, getting \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, \begin{equation}\label{eqn:35.23} 35\cdot23\equiv1\pmod{67}, \end{equation} so $\gcd(23,67)=1$, and~\eqref{eqn:70} is equivalent to \begin{gather*} x\equiv23\cdot9\equiv207\equiv6\pmod{67},\\ x\equiv6,73\pmod{134}. \end{gather*} A way to read~\eqref{eqn:35.23} is that $23$ is an \textbf{inverse}% \index{inverse} of $35$ with respect to the modulus $67$. We can express this by \begin{equation*} 23\equiv\frac1{35}\pmod{67}. \end{equation*} In particular, $35$ is invertible as an element of $\Zmod[67]$. We have in general \begin{theorem}\label{thm:inv} With respect to a modulus, a number is invertible if and only if it is prime to the modulus. \end{theorem} \begin{proof} The following are equivalent by B\'ezout's Lemma (the corollary to Theorem~\ref{thm:gcd}): \begin{compactenum} \item $a$ is invertible \emph{modulo} $n$, \item the congruence $ax\equiv1\pmod n$ is soluble, \item the diophantine equation $ax+ny=1$ is soluble, \item $\gcd(a,n)=1$.\qedhere \end{compactenum} \end{proof} \section{Chinese remainder problems} The first known example of a so-called \textbf{Chinese remainder problem}% \index{Chinese remainder problem} is 3.26 in the \emph{Sunzi suan jing}\label{Sunzi} (\emph{Mathematical Classic of Master Sun}), which is `most probably a work of the fourth or early fifth century \textsc{ce}'~\cite[p.~295]{Katz}. The problem and its supplied `solution' read thus: \begin{quote} Now there are an unknown number of things. If we count by threes, there is a remainder $2$; if we count by fives, there is a remainder $3$; if we count by sevens, there is a remainder $2$. Find the number of things. Answer: $23$. Method: If we count by threes and there is a remainder $2$, put down $140$. If we count by fives and there is a remainder $3$, put down $63$. If we count by sevens and there is a remainder $2$, put down $30$. Add them to obtain $233$ and subtract $210$ to get the answer. If we count by threes and there is a remainder $1$, put down $70$. If we count by fives and there is a remainder $1$, put down $21$. If we count by sevens and there is a remainder $1$, put down $15$. When [a number] exceeds $106$, the result is obtained by subtracting $105$.\hfill\cite[p.~299]{Katz} \end{quote} In our terms, the problem is to solve three congruences simultaneously: \begin{align*} x&\equiv2\pmod3,& x&\equiv3\pmod5,& x&\equiv2\pmod7. \end{align*} Note that $3\cdot5\cdot7=105$. The given solution is \begin{equation*} x\equiv2\cdot70+3\cdot21+2\cdot15\pmod{105}. \end{equation*} This \emph{is} a solution, because \begin{align*} 70&\equiv1\pmod3,&21&\equiv0\pmod3,&15&\equiv0\pmod3,\\ 70&\equiv0\pmod5,&21&\equiv1\pmod5,&15&\equiv0\pmod5,\\ 70&\equiv0\pmod7,&21&\equiv0\pmod7,&15&\equiv1\pmod7. \end{align*} This is the \emph{only} solution, by the corollary to Theorem~\ref{thm:lcm} on page~\pageref{thm:lcm}. The key to the solution is finding the numbers $70$, $21$, and $15$. Note that \begin{align*} 70&=(5\cdot7)\cdot2,&21&=(3\cdot7)\cdot1,&15=(3\cdot5)\cdot1. \end{align*} So the real problem is to find the coefficients $2$, $1$, and $1$, which are, respectively, inverses of $5\cdot7$, $3\cdot7$, and $3\cdot5$, with respect to $3$, $5$, and $7$. When they exist, such inverses can be found by means of the Euclidean algorithm, as in the previous section. The general problem is now solved as follows: \begin{theorem}\label{thm:crp} If moduli $n_1$, \dots, $n_k$ are given, each being prime to the rest, then every system of congruences \begin{align}\label{eqn:crt} x&\equiv a_1\bmod{n_1},& x&\equiv a_2\bmod{n_2},& &\dots,& x&\equiv a_k\bmod{n_k}, \end{align} has a solution, which is unique \emph{modulo} the product $N$ of the moduli. This solution is given by \begin{equation*} x\equiv a_1\cdot\frac N{n_1}\cdot m_1+\dotsb+a_k\cdot\frac N{n_k}\cdot m_k\pmod N, \end{equation*} where $m_i$ is an inverse of $N/n_i$ with respect to $n_i$. \end{theorem} This theorem will be discussed more theoretically in \S\ref{sect:CRT-again}. Meanwhile, we have given the theorem in a `self-proving' formulation: the proposed solution is easily seen to be a solution, and as noted above, there can be no others.\footnote{The notion of a \emph{self-proving theorem} is introduced and discussed by Barry Mazur \cite{Mazur-Th-pub}.} It may be useful to consider the case of two congruences, \begin{align}\label{eqn:crt-2} x&\equiv a\pmod n,& x&\equiv b\pmod m, \end{align} where $\gcd(n,m)=1$. For some $r$ and $s$, we have \begin{align}\label{eqn:crt-3} nr&\equiv1\pmod m,&ms&\equiv1\pmod n, \end{align} so that the solution to~\eqref{eqn:crt-2} is \begin{equation*} x\equiv ams+bnr\pmod{nm}. \end{equation*} In finding this solution, we \emph{could} choose $r$ and $s$ by means of the Euclidean algorithm, so that \begin{equation*} nr+ms=1; \end{equation*} but all we really need is~\eqref{eqn:crt-3}. Moreover, we need not actually calculate both $r$ and $s$. Indeed, the solutions of~\eqref{eqn:crt-2} are just those sums $a+nt$ in which $t$ is such that $m\divides a-b+nt$, that is, \begin{equation}\label{eqn:a-b} b-a\equiv nt\pmod m; \end{equation} so $t\equiv r(b-a)\pmod m$. We need not even calculate $r$; we can just hunt through a complete set of residues with respect to $m$ for a value of $t$ as in~\eqref{eqn:a-b}. For example, the following problem is attributed to Brahmagupta:\footnote{My source for the problem is \url{http://www.chinapage.com/math/crt.html} (accessed December 14, 2010), where the problem is prefaced with the remark, `Oystein Ore mentions another puzzle with a dramatic element from Brahma-Sphuta-Siddhanta (Brahma's Correct System) by Brahmagupta (born 598 AD)'. The page also gives the problem of Sunzi [Master Sun] quoted on page~\pageref{Sunzi} above. The Brahmagupta problem is the basis of an exercise in Burton~\cite[Prob.~4.4.8--9, p.~83]{Burton}. But the problem is not among the works of Brahmagupta given in the Katz volume~\cite{Katz}.} \begin{quote} An old woman goes to market and a horse steps on her basket and crushes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had? \end{quote} If $x$ is that number, then \begin{align*} x&\equiv1\pmod{2,3,4,5,6},& x&\equiv0\pmod7. \end{align*} Since $\lcm(2,3,4,5,6)=60$, the problem is to find the least positive solution to \begin{align*} x&\equiv1\pmod{60},& x&\equiv0\pmod7. \end{align*} so $x=1+60t$, where $t$ is least such that $7\divides 1+60t$, that is, \begin{equation*} -1\equiv60t\equiv4t\pmod7. \end{equation*} By trial, $t=5$, and therefore $x=301$. \chapter{Powers of two} \section{Perfect numbers} Of the 13 books of Euclid's \emph{Elements,} Books VII, VIII and IX concern numbers. The last proposition in these books is about \textbf{perfect}% \index{perfect number}% \index{number!perfect ---} numbers, namely those numbers that are the sums of their (positive) proper divisors. For example, $6$ and $28$ are perfect since \begin{align*} 6&=1+2+3,& 28&=1+2+4+7+14. \end{align*} Euclid gives a sufficient condition for being perfect. The proof uses that \begin{equation*} 1+2+4+\dots+2^{k-1}=2^k-1. \end{equation*} \begin{theorem}[Euclid, IX.36] \index{theorem!Euclid's Th---}% \index{Euclid!---'s Theorem} If $2^k-1$ is prime, then $2^{k-1}\cdot(2^k-1)$ is perfect. \end{theorem} \begin{proof} If $2^k-1$ is prime, then the positive divisors of $2^{k-1}\cdot(2^k-1)$ are the divisors of $2^{k-1}$, perhaps multiplied by $2^k-1$; namely, they are: \begin{align*} &1,& &2,& &4,& &\dots,& &2^{k-1},\\ &2^k-1,& &2\cdot(2^k-1),& &4\cdot(2^k-1),& &\dots,& &2^{k-1}\cdot(2^k-1). \end{align*} The sum of these is $(1+2+4+\dotsb+2^{k-1})\cdot2^k$, which is $(2^k-1)\cdot 2^k$. Subtracting the improper divisor $2^{k-1}\cdot(2^k-1)$ leaves the same. \end{proof} Theorem~\ref{thm:a|bc} has a partial converse:\footnote{According to Dickson~\cite[p.~19]{Dickson}, Euler's proof of this was published posthumously in 1849.} \begin{theorem}\label{thm:even-perf} Every \emph{even} perfect number is $2^{k-1}\cdot(2^k-1)$ for some $k$ such that $2^k-1$ is prime. \end{theorem} \begin{proof} Let us write $\msig(n)$ for the sum of the positive divisors of $n$. Suppose $n$ is an even perfect number. Then $n=2^{k-1}m$ for some $k$ and $m$, where $k>1$ and $m$ is odd. Every factor of $n$ is uniquely the product of a factor of $2^{k-1}$ and a factor of $m$, so \begin{equation*} \msig(n) =\msig(2^{k-1})\cdot\msig(m)=(1+2+\cdots+2^{k-1})\cdot\msig(m) =(2^k-1)\cdot\msig(m). \end{equation*} Since we assume $\msig(n)=2n$, we have now \begin{equation*} 2^km=(2^k-1)\cdot\msig(m). \end{equation*} In particular, $2^k\divides\msig(m)$, so $\msig(m)=2^k\cdot\ell$ for some $\ell$. Then \begin{align*} m&=(2^k-1)\cdot\ell=\msig(m)-\ell,& \msig(m)&=m+\ell. \end{align*} Since $m$ and $\ell$ are two distinct factors of $m$, they must be the \emph{only} positive factors. In particular, $\ell=1$, and $m$ is prime, so $n$ is as desired.\footnote{Exercise~\ref{xca:even-perf-why} asks how we have used that $n$ is even.} \end{proof} In his excellent textbook \emph{Elementary Number Theory}~\cite{MR0092794} (first published in German in 1927), Edmund Landau (1877--1938) writes, before proving the foregoing theorems: \begin{quote} This old-fashioned concept of perfect number, and the questions associated with it, are not especially important; we consider them only because, in so doing, we will encounter two questions that remain unanswered to this day: Are there infinitely many perfect numbers? Is there an odd perfect number? Modern mathematics has solved many (apparently) difficult problems, even in number theory; but we stand powerless in the face of such (apparently) simple problems as these. Of course, the fact that they have never been solved is irrelevant to the rest of this work. We will leave no gaps; when we come to a bypath which leads to an insurmountable barrier, we will turn around, rather than---as is so often done---continue on beyond the barrier. \end{quote} The questions that Landau cites are still unanswered. It is also the aim of the present book to leave no gaps (except for the unproved theorems in Appendix~\ref{ch:unproved}, which however we shall never use). \section{Mersenne primes} %\begin{sloppypar} The number $2^n-1$ is called a \textbf{Mersenne number,}% \index{Mersenne}% \index{Mersenne!--- number}% \index{number!Mersenne ---} after Marin Mersenne, 1588--1648; if the number is prime, it is a \textbf{Mersenne prime.}% \index{Mersenne!--- prime}% \index{prime!Mersenne ---} Since we do not know whether there are infinitely many even perfect numbers, we do not know whether there are infinitely many Mersenne primes. However, we do have the following necessary condition for being a Mersenne prime:\footnote{Stated by Fermat in a letter of 1640 to Mersenne, according to Dickson~\cite[p.~12]{Dickson}.} %\end{sloppypar} \begin{theorem}\label{thm:Mp} if $2^n-1$ is prime, then so must $n$ be. \end{theorem} \begin{proof} We have $2^k-1\divides 2^{k\ell}-1$ from the identity \begin{equation*} x^m-1=(x-1)(x^{m-1}+x^{m-2}+\dotsb+x+1).\qedhere \end{equation*} \end{proof} So every Mersenne prime is $2^p-1$ for some $p$; but the converse fails,\footnote{The counterexample $2^{11}=2047=23\cdot89$ was apparently known to Ulrich Regius in 1536~\cite[pp.~III \&\ 7]{Dickson}. However, see Theorem~\ref{thm:psp} on page~\pageref{thm:psp}.} as shown in Table~\ref{tab:Mersenne}.\footnote{I have not personally verified that $2^p-1$ is prime when $p$ is $13$, $17$, or $19$; nor have I verified that $178481$ is prime.} \begin{table}[ht] \begin{equation*} \begin{array}{rrrr} p&2^p-1&\text{factorization}&2^{p-1}(2^p-1)\\\hline 2&3&-&6\\ 3&7&-&28\\ 5&31&-&496\\ 7&127&-&8128\\ 11&2047&23\cdot89&\\ 13&8191&-&33550336\\ 17&131071&-&8589869056\\ 19&524287&-&137438691328\\ 23&8388607&47\cdot178481& \end{array} \end{equation*} \caption{Mersenne primes and perfect numbers}\label{tab:Mersenne} \end{table} For every $p$ in the table such that $2^p-1$ is not prime, we have $2p+1$ is prime, and $2p+1\cong\pm1\pod 8$. A odd prime $p$ such that $2p+1$ is also prime is called a \textbf{Germain prime.}\label{Germain}% \index{Germain, --- prime}% \index{prime! Germain ---}% \footnote{Named for Sophie Germain, 1776--1831.} Later, with Theorem~\ref{thm:Germain} on page~\pageref{thm:Germain}, we shall have that if $2p+1$ is a prime $q$, and $q\cong\pm1\pod8$, then $2^p-1$ is not prime, because $q$ is a factor, that is, \begin{equation*} 2^p\equiv1\pmod q. \end{equation*} \chapter{Prime moduli} \section{Fermat's Theorem}\label{sect:FT} On October 10, 1640, Pierre de Fermat (1601--65) wrote the following in a letter to Bernard Fr\'enicle de Bessy (1605--1675):\footnote{The letter was in French; I take this selection, in translation, from Struik's anthology~\cite[p.~28]{MR858706}. The translator of Gauss assigns to what must be the same letter the date of October 18, 1640~\cite[p.~32, n.~1]{Gauss}.} \begin{quote} Every prime number is always a factor of one of the powers of any [geometric] progression minus $1$, and the exponent of this power is a divisor of the prime number minus $1$. After one has found the first power that satisfies the proposition, all those powers of which the exponents are multiples of the exponent of the first power also satisfy the proposition. \emph{Example:} Let the given progression be \begin{equation*} \begin{array}{*7{r}} 1&2& 3& 4& 5& 6&\\ 3&9&27&81&243&729&\text{etc.} \end{array} \end{equation*} with its exponents written on top. Now take, for instance, the prime number $13$. It is a factor of the third power minus $1$, of which $3$ is the exponent and a divisor of $12$, which is one less than the number $13$, and because the exponent of $729$, which is $6$, is a multiple of the first exponent, which is $3$, it follows that $13$ is also a factor of this power $729$ minus $1$. And this proposition is generally true for all progressions and for all prime numbers, of which I would send you the proof if I were not afraid to be too long. \end{quote} More symbolically, the claim is: \begin{compactenum}[1.] \item For all $p$, for all $a$ [such that $p\ndivides a$---Fermat does not appear to make this condition explicit], there is some positive $n$ such that $p\divides a^n-1$. \item If $k$ is the least such $n$, then $k\divides p-1$. \item In this case, if $k\divides m$, then $p\divides a^m-1$. \end{compactenum} A consequence of the claim is that, if $p\ndivides a$, then $p\divides a^{p-1}-1$. This is called \textsl{Fermat's Theorem.}\footnote{The theorem is sometimes called Fermat's \emph{Little} Theorem, as opposed to the so-called Fermat's \emph{Last} Theorem (see page~\pageref{note:FLT}, note~\ref{note:FLT}).}% \index{Fermat!---'s Theorem}% \index{theorem!Fermat's Th---} A proof of this theorem was found among the writings of Leibniz (1646--1716)~\cite[p.~59]{Dickson}. The first \emph{published} proof was by Euler, in 1736.\footnote{This is stated by Gauss in the \emph{Disquisitiones Arithmeticae}~\cite[\P50]{Gauss} and confirmed by Dickson~\cite[p.~60]{Dickson} and Struik~\cite[p.~35, n.~2]{MR858706}.} This proof uses the following: \begin{lemma} If $0inv} on page~\pageref{thm:-->inv}. \end{proof} Induction normally proves something true for all \emph{positive} integers. But~\eqref{eqn:F2} holds for \emph{all} integers $a$, and Euler's proof establishes this, since every integer is congruent \emph{modulo} $p$ to a positive integer, and if $a\equiv b\pod p$, then $a^p\equiv b^p\pod p$ by Theorem~\ref{thm:+.mod-n}. Alternatively, we can understand the proof as establishing $a^p=a$ for all $a$ in $\Zmod[p]$. Induction still works here; it just takes us around in a circle, from $1$, to $2$, to $3$, and so on up to $p$, and then back to $1$. (See Figure~\ref{fig:13}.) In particular, $\Zmod[p]$ is one of the sets mentioned after the Axiom in \S\ref{sect:N}, in which only part of the Axiom is satisfied. Indeed, $\Zmod[p]$ allows induction, but here $1$ is the successor of $p$. \begin{figure}[ht] \centering \psset{unit=2cm} \begin{pspicture}(-1,-1)(1,1) \rput(0,1){$13$} \rput(0.465,0.885){$1$} \rput(-0.465,0.885){$12$} \rput(0.823,0.568){$2$} \rput(-0.823,0.568){$11$} \rput(0.993,0.121){$3$} \rput(-0.993,0.121){$10$} \rput(0.935,-0.355){$4$} \rput(-0.935,-0.355){$9$} \rput(0.663,-0.749){$5$} \rput(-0.663,-0.749){$8$} \rput(0.239,-0.971){$6$} \rput(-0.239,-0.971){$7$} \psarc{<-}(0,0){0.8}{90}{62.3} \end{pspicture} \caption{The integers \emph{modulo} $13$, or $\Zmod[13]$}\label{fig:13} \end{figure} Euler later proved the more general claims of Fermat in the quotation above.\footnote{Euler's treatment can be read in Struik~\cite[pp.~31--5]{MR858706}.} In particular, he showed that, if $p\ndivides a$, then there is some $\lambda$ such that $\lambda>1$ and $p\divides a^{\lambda}-1$. The \emph{least} such $\lambda$ is what we shall call the \textsl{order}% \index{order} of $a$ \emph{modulo} $p$ in \S\ref{sect:order}. If $\lambda$ is this order, then Euler showed $\lambda\divides p-1$, and then $p\divides a^{p-1}-1$. He later generalized this result, establishing what is called Euler's Theorem (Theorem~\ref{thm:Euler} on page~\pageref{thm:Euler}).\footnote{An account of this is in Dickson~\cite[p.~61]{Dickson}.} There is yet another proof of Fermat's Theorem, published by James Ivory in 1806 \cite{Ivory}.\footnote{According to Dickson~\cite[p.~65]{Dickson}, this proof was later rediscovered and published by Dirichlet in 1828. Landau~\cite[p.~50]{MR0092794} uses the proof. Hardy and Wright~\cite[p.~63]{MR568909} also use it, but the historical information that they supply about Fermat's and Euler's theorems does not address this proof.} Perhaps it is the best. If $\gcd(a,p)=1$, then the products $a$, $2a$, \dots, $(p-1)a$ are all incongruent \emph{modulo} $p$, since \begin{equation*} ia\equiv ja\bmod p\implies i\equiv j\bmod p \end{equation*} by Theorem~\ref{thm:-->inv}. But $1$, $2$, \dots, $p-1$ are also incongruent. By Theorem~\ref{thm:res}, there are only $p-1$ numbers that are incongruent with each other and $0$ \emph{modulo} $p$; so the numbers $a$, $2a$, \dots, $(p-1)a$ are congruent respectively to $1$, $2$, \dots, $p-1$ in some order. Now multiply the numbers on each side together: \begin{equation*} (p-1)!\cdot a^{p-1}\equiv(p-1)!\pmod p. \end{equation*} Since $(p-1)!$ and $p$ are co-prime, we can conclude~\eqref{eqn:F}. This implies~\eqref{eqn:F2} in case $p\ndivides a$; but if $p\divides a$, then~\eqref{eqn:F2} is obvious. With Fermat's Theorem, we can compute residues of large powers easily. For example, \begin{equation*} 6^{58}\equiv 6^{48+10}\equiv(6^{16})^3\cdot 6^{10}\equiv 6^{10}\pmod{17}. \end{equation*} We can continue the computation as in \S\ref{sect:exp}, by analyzing the exponent $10$ as a sum of powers of $2$. Since $10=8+2$, we have $6^{10}=6^8\cdot 6^2$; but $6^2\equiv36\equiv2\pod{17}$, so $6^8\equiv(6^2)^4\equiv2^4\equiv16\equiv-1\pod{17}$, and hence \begin{equation*} 6^{58}\equiv -2\pmod{17}. \end{equation*} A contrapositive formulation of Fermat's Theorem is that, if $a^n\not\equiv a\pmod n$, then $n$ must not be prime. For example, to see whether $133$ is prime, we may note that $133=128+4+1=2^7+2^2+1$, so $2^{133}=2^{2^7}\cdot 2^{2^2}\cdot 2$. Also, \begin{align}\notag 2^2&=4;\\\notag 2^{2^2}&=4^2=16;\\\notag 2^{2^3}&=16^2=256\equiv123\equiv-10\pmod{133};\\\notag 2^{2^4}&\equiv(-10)^2=100\equiv-33;\\\notag 2^{2^5}&\equiv(-33)^2=1089\equiv25;\\\notag 2^{2^6}&\equiv25^2=625\equiv-40;\\\label{eqn:1600} 2^{2^7}&\equiv(-40)^2=1600\equiv4. \end{align} Therefore $2^{133}\equiv4\cdot16\cdot2\equiv-5\pmod{133}$, so $133$ must not be prime. Note an alternative computation after~\eqref{eqn:1600}: We have $2^{128}=2^{2^7}\equiv4\equiv 2^2$, so $2^{126}\equiv1$, hence $2^{133}=2^{126+7}\equiv2^7=128\equiv-5$. Now, if we just want to know whether $133$ is prime, it is probably easier to use the theorems in \S\ref{sect:sieve}. Indeed, $[\sqrt{133}]=11$, so it is enough to test for divisibility by $2$, $3$, $5$, $7$, and $11$. We find then $133=7\cdot19$. Still, we may raise the theoretical question: Does Fermat's Theorem give us an \emph{infallible} method for testing for primes? Can \emph{every} composite number be detected by means of the theorem? The answer turns out to be no. \section{Carmichael numbers}\label{sect:Car} The converse of Fermat's Theorem fails. It may be that $a^n\equiv a\pmod n$ for all $a$, although $n$ is not prime. To see this, we first define $n$ to be a \textbf{pseudo-prime}% \index{pseudo-prime}% \index{prime!pseudo-{}---} if $n$ is composite, but \begin{equation*} 2^n\equiv 2\pmod n. \end{equation*} To establish an example, we shall use: \begin{theorem} If $p\neq q$, and $a^p\equiv a\pod q$ and $a^q\equiv a\pod p$, then $a^{pq}\equiv a\pod{pq}$. \end{theorem} \begin{proof} Under the hypothesis, we have \begin{gather*} a^{pq}=(a^p)^q\equiv a^q\equiv a\pmod q,\\ a^{pq}=(a^q)^p\equiv a^p\equiv a\pmod p, \end{gather*} and hence $a^{pq}\equiv a\pmod{\lcm(p,q)}$ by Theorem~\ref{thm:lcm} and corollary. \end{proof} Then $341$ is a pseudo-prime, since $341=11\cdot31$, and \begin{align*} 2^{11}&=2048=31\cdot 66+2\equiv 2\pmod{31},\\ 2^{31}&=(2^{10})^3\cdot 2\equiv2\pmod{11}. \end{align*} We can now state and prove what resembles a converse to Theorem~\ref{thm:Mp}: \begin{theorem}\label{thm:psp} If $n$ is a pseudo-prime, then so is $2^n-1$. \end{theorem} \begin{proof} If $n$ is a pseudo-prime, then it is not prime, so by Theorem~\ref{thm:Mp}, neither is $2^n-1$. We also have $2^n\equiv2\pmod n$ by Fermat's Theorem; say $2^n-2=kn$. Then \begin{equation*} 2^{2^n-1}-2=2\cdot(2^{2^n-2}-1)=2\cdot(2^{kn}-1), \end{equation*} which has the factor $2^n-1$; so $2^{2^n-1}\equiv2\pmod{2^n-1}$. \end{proof} %\begin{sloppypar} Pseudo-primes as we defined them can be called more precisely \emph{pseudo-primes of base} $2$. Then a pseudo-prime of base $a$ is a composite number $n$ such that $a^n\equiv a\pmod n$. A composite number that is a pseudo-prime of \emph{every} base can be called an \textbf{absolute pseudo-prime.}% \index{prime!absolute pseudo-{}---}% \index{absolute pseudo-prime}% \index{pseudo-prime!absolute ---} It is also called a \textbf{Carmichael number}\label{Carmichael}% \index{Carmichael, --- number}% \index{number!Carmichael ---} after Robert Daniel Carmichael (1879--1967), who published the first examples of such numbers in 1910~\cite{MR1558896}. If $n$ is a Carmichael number, then \begin{equation*} a^{n-1}\equiv1\pmod n \end{equation*} whenever $\gcd(a,n)=1$. We shall establish the converse of this in Theorem~\ref{thm:Car-char} on page~\pageref{thm:Car-char}. %\end{sloppypar} Meanwhile, $561$ is a Carmichael number. To see this, we first factorize $561$ as $3\cdot11\cdot17$ and note \begin{align*} 3-1&\divides 561-1,& 11-1&\divides 561-1,& 17-1&\divides 561-1, \end{align*} that is, $2\divides 560$, $10\divides 560$, and $16\divides 560$. We now make the following observations. \begin{enumerate} \item If $3\ndivides a$, then $a^2\equiv1\pmod 3$, so $a^{560}\equiv1\pmod 3$. \item If $11\ndivides a$, then $a^{10}\equiv1\pmod 3$, so $a^{560}\equiv1\pmod{11}$. \item If $17\ndivides a$, then $a^{16}\equiv1\pmod 3$, so $a^{560}\equiv1\pmod{17}$. \end{enumerate} Hence if one of $3$, $11$, and $17$ fails to divide $a$, then we have $a^{560}\equiv1\pod{561}$ and therefore \begin{equation}\label{eqn:561} a^{561}\equiv a\pmod{561}. \end{equation} But if each of $3$, $11$, and $17$ divides $a$, then $561\divides a$, so again we have~\eqref{eqn:561}. A positive integer is \textbf{squarefree}% \index{squarefree number}% \index{number!squarefree ---} if it has no divisor $p^2$. The proof that $561$ is an absolute pseudo-prime generalizes to establish the following:\footnote{The proof is Exercise~\ref{xca:Carmichael}.} \begin{theorem}\label{thm:Carmichael} A number $n$ greater than $1$ is a prime or absolute pseudo-prime if it is squarefree and $p-1\divides n-1$ whenever $p\divides n$. \end{theorem} The sufficient condition given by the theorem for being an absolute pseudo-prime is \textbf{Korselt's Criterion,}\label{Korselt}% \index{Korselt's Criterion} so called after Alwin Reinhold Korselt (1864--1947), who proved its sufficiency and necessity in 1899, apparently without actually finding any absolute pseudo-primes. The term \emph{Korselt's Criterion} is used by Alford \emph{et al.}\ in their 1994 paper~\cite{MR1283874}, where they prove that there are infinitely many absolute pseudo-primes. We can prove the necessity of \emph{part} of Korselt's Criterion now; the rest will have to wait until Theorem~\ref{thm:Car-p-1} (p.~\pageref{thm:Car-p-1}), when we have \textsl{primitive roots}% \index{primitive root} of primes. \begin{theorem}\label{thm:Car-sqf} Every absolute pseudo-prime is squarefree. \end{theorem} \begin{proof} Suppose $n$ is an absolute pseudo-prime. If $p^2\divides n$, then \begin{equation*} p^n\equiv p\pmod{p^2}. \end{equation*} But $n>1$ (since it is composite), so $p^n\equiv0\pmod{p^2}$, and therefore $p\equiv0\pmod{p^2}$, which is absurd. \end{proof} \section{Wilson's Theorem}\label{sect:Wilson} Evidently $(p-1)!\not\equiv 0\pmod p$. By the next theorem, the congruence \begin{equation}\label{eqn:W} (p-1)!\equiv x\pmod p \end{equation} has the same solution for all $p$, namely $-1$. This was known to Abu Ali al-Hasan ibn al-Haytham (965--1040)\footnote{According to \url{http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Haytham.html} (accessed December 19, 2010).} and probably also to Leibniz.\index{Leibniz} The theorem was published by Edward Waring (c.~1736--98) in 1770 and attributed to his student John Wilson (1741--93), so it is called Wilson's Theorem. However, the first published \emph{proof} was by Joseph-Louis Lagrange (1736--1813) in 1773.\footnote{The bare facts are in Dickson~\cite[p.~62]{Dickson}.} Lagrange's proof makes use of a result that arises from considering successive differences of powers as in Table~\ref{table:dif} below. %(page~\pageref{table:dif}). \begin{table}[ht] \begin{align*} &\xymatrix@!@=0pt@M=0pt{ 1& &1\\ &0& } &&\xymatrix@!@=0pt@M=0pt{ 0& &1& &2&\\ &1& &1& \\ & &0& & } && \xymatrix@!@=0pt@M=0pt{ 0& &1& &4& &9\\ &1& &3& &5& \\ & &2& &2& & \\ & & &0& & & } && \xymatrix@!@=0pt@M=0pt{ 0& &1& & 8& &27& &64\\ &1& &7& &19& &37& \\ & &6& &12& &18& & \\ & & &6& & 6& & & \\ & & & & 0& & & & } \end{align*} \begin{equation*} \xymatrix@!@=0pt@M=0pt{ 0& & 1& &16& & 81& &256& &625\\ &1& &15& &65& &175& &369& \\ & &14& &50& &110& &194& & \\ & & &36& &60& & 84& & & \\ & & & &24& & 24& & & & \\ & & & & & 0& & & & & } \end{equation*} \begin{equation*} \xymatrix@!@=0pt@M=0pt{ 0& & 1& & 32& &243& &1024& &3125& &7776\\ &1& & 31& &211& &781& &2101& &4651& \\ & &30& &180& &570& &1320& &2550& & \\ & & &150& &390& &750& &1230& & & \\ & & & &240& &360& & 480& & & & \\ & & & & &120& &120& & & & & \\ & & & & & & 0& & & & & & } \end{equation*} \caption{Successive differences of powers}\label{table:dif} \end{table} (However, Lagrange's proof is not the simplest; so the reader may wish to skip ahead.) In each triangular array in the table, the top row is the sequence $0^n$, $1^n$, $2^n$, \dots; then each successive row consists of the differences of consecutive entries in the previous row. Let us number the rows from the top, starting with $0$. If row $0$ consists of $n$th powers, it appears that the entries in row $n$ are $n!$, so that the entries of all further rows are $0$. The appearance is the reality, by induction: First of all it is true when $n=0$. Suppose it is true when $n\leq m$. We consider the array whose top row consists of powers $x^{m+1}$. We compute \begin{equation*} (x+1)^{m+1}-x^{m+1}=(m+1)x^m+\binom{m+1}2x^{m-1}+\binom{m+1}3x^{m-2}+\cdots. \end{equation*} By inductive hypothesis, the only term that will have any effect, $m$ rows later, is $(m+1)x^m$. That is, as far as row $m+1$ is concerned, row $1$ might as well consist of the entries $(m+1)x^m$. So each entry of row $m+1$ is $m+1$ times the corresponding entry of row $m$ of the array whose top row consists of powers of $m$. By inductive hypothesis, every entry of this row $m$ is $m!$. This completes the induction. This result gives us the $(p-1)!$ in Wilson's Theorem; the $-1$ that solves~\eqref{eqn:W} comes from a more general expression for successive differences:\footnote{The lemma appears to be due to Euler~\cite[p.~63]{Dickson}.} \begin{lemma} For all non-negative integers $n$, for all $x$ in $\R$, \begin{equation*} n!= \sum_{k=0}^n(-1)^{n-k}\binom nk(x+k)^n. \end{equation*} \end{lemma} \begin{proof} Given a function $f$ on $\R$, we define the function $\Delta f$ by \begin{equation*} \Delta f(x)=f(x+1)-f(x). \end{equation*} Then by recursion we define \begin{align*} \Delta^0f&=f,& \Delta^{n+1}f&=\Delta^n\Delta f. \end{align*} By induction, \begin{equation*} \Delta^nf(x)=\sum_{k=0}^n(-1)^{n-k}\binom nkf(x+k). \end{equation*} Indeed, the claim holds easily when $n=0$, and if it holds when $n=m$, then by the computations in Table~\ref{table:Delta} (page~\pageref{table:Delta})\label{Delta}, \begin{table}[ht] \hrulefill \begin{align*} &\phantom{{}={}}\Delta^{m+1}f(x)\\ &=\Delta^m\Delta f(x)\\ &=\sum_{k=0}^m(-1)^{m-k}\binom mk\Delta f(x+k)\\ &=\sum_{k=0}^m(-1)^{m-k}\binom mk\bigl(f(x+k+1)-f(x+k)\bigr)\\ &=\sum_{k=0}^m(-1)^{m-k}\binom mkf(x+k+1) -\sum_{k=0}^m(-1)^{m-k}\binom mkf(x+k)\\ &\begin{aligned} =f(x+m+1) &+\sum_{k=0}^{m-1}(-1)^{m-k}\binom mkf(x+k+1)\\ &-\sum_{k=1}^m(-1)^{m-k}\binom mkf(x+k)-(-1)^mf(x) \end{aligned}\\ &\begin{aligned} =f(x+m+1) &+\sum_{k=1}^m(-1)^{m+1-k}\binom m{k-1}f(x+k)\\ &+\sum_{k=1}^m(-1)^{m+1-k}\binom mkf(x+k)+(-1)^{m+1}f(x) \end{aligned}\\ &=f(x+m+1)+\sum_{k=1}^m(-1)^{m+1-k}\binom{m+1}kf(x+k)+(-1)^{m+1}f(x)\\ &=\sum_{k=0}^{m+1}(-1)^{m+1-k}\binom{m+1}kf(x+k), \end{align*} \hrulefill \caption[The inductive step for $\Delta^nf(x)$]{The inductive step for $\Delta^nf(x)$ (see page~\pageref{Delta})}\label{table:Delta} \end{table} it holds when $n=m+1$. Now we consider the special case when $f(x)=x^m$. We shall be done if we show that, if $0\leq m\leq n$, then \begin{equation*} \Delta^n(x^m)=\begin{cases} 0,&\text{ if }m1$. Then $(n-1)!\equiv-1\pmod n$ if and only if\footnote{The \emph{necessity} that $n$ be prime was apparently not part of the original statement of Wilson's Theorem. Lagrange proved it~\cite[p.~63]{Dickson}.} $n$ is prime. \end{theorem} \begin{proof}[Proof (Lagrange).] Suppose $n$ is not prime, so that $n=ab$, where $11. \end{cases} \end{equation*} This is easily a multiplicative function. Both the statement and the proof of the following theorem are important. \begin{theorem}\label{thm:m*1=e} For all $n$, \begin{equation*} \sum_{d\divides n}\mmu(d)=\mep(n). \end{equation*} \end{theorem} \begin{proof} Both sides of the desired equation are multiplicative functions of $n$. \emph{Therefore it is sufficient to prove the equation when $n$ is a prime power.} This is easy: \begin{align*} \sum_{d\divides p^s}\mmu(d) &=\sum_{k=0}^s\mmu(p^k)\\ &=\mmu(1)+\mmu(p)+\dotsb+\mmu(p^s)\\ &=\begin{cases} \mmu(1),&\text{ if }s=0,\\ \mmu(1)+\mmu(p),&\text{ if }s>0 \end{cases}\\ &=\begin{cases} 1,&\text{ if }s=0,\\ 1-1,&\text{ if }s>0 \end{cases}\\ &=\mep(p^s).\qedhere \end{align*} \end{proof} Another important, albeit easy, observation is: \begin{theorem}\label{thm:f*e=f} For all arithmetic functions $f$, \begin{equation*} \sum_{d\divides n}f(d)\cdot\mep\Bigl(\frac nd\Bigr)=f(n). \end{equation*} \end{theorem} Now we can prove that the function $\xi$ above is indeed $(n,d)\mapsto\mmu(n/d)$: \begin{theorem}[M\"obius Inversion]\label{thm:MIF}% \index{Mobius@M\"obius!--- Inversion}% \index{theorem!M\"obius Inversion} If $f$ determines $F$ by the rule~\eqref{eqn:Ff}, namely \begin{equation*} F(n)=\sum_{d\divides n}f(d), \end{equation*} then $F$ determines $f$ by the rule \begin{equation*} f(n)=\sum_{d\divides n}\mmu\Bigl(\frac nd\Bigr)\cdot F(d), \end{equation*} and conversely. \end{theorem} \begin{proof} We just start calculating: \begin{align*} \sum_{d\divides n}\mmu\Bigl(\frac nd\Bigr)\cdot F(d) &=\sum_{d\divides n}\mmu\Bigl(\frac nd\Bigr)\cdot\sum_{e\divides d}f(e)\\ &=\sum_{d\divides n}\sum_{e\divides d}\mmu\Bigl(\frac nd\Bigr)\cdot f(e). \end{align*} Now we want to rearrange indices. For all factors $d$ and $e$ of $n$, we have \begin{equation*} e\divides d\iff\frac nd\divides\frac ne \end{equation*} by Theorem~\ref{thm:den}. So there is a bijection between $\{(d,e)\colon d\divides n\And e\divides d\}$ and $\{(e,c)\colon e\divides n\And c\divides n/e\}$, namely $(d,e)\mapsto(e,n/d)$; the inverse is $(e,c)\mapsto(n/c,e)$. Therefore \begin{align*} \sum_{d\divides n}\mmu\Bigl(\frac nd\Bigr)\cdot F(d) &=\sum_{e\divides n}\sum_{c\divides(n/e)}\mmu(c)\cdot f(e)\\ &=\sum_{e\divides n}f(e)\cdot\sum_{c\divides(n/e)}\mmu(c)\\ &=\sum_{e\divides n}f(e)\cdot\mep\Bigl(\frac ne\Bigr)\\ &=f(n) \end{align*} by the last two theorems. The converse is similar.\footnote{This is Exercise \ref{xca:Moebius-inv}.} \end{proof} \section{Convolution}\label{sect:conv} We can streamline some of the foregoing results. If $f$ and $g$ are arithmetic functions, their \textbf{convolution}% \index{convolution} is the function $f*g$, given by \begin{equation*} (f*g)(n)=\sum_{d\divides n}f(d)\cdot g\Bigl(\frac nd\Bigr). \end{equation*} Now, we have the following general principle: \begin{theorem}\label{thm:dnd} For every arithmetic function $f$, \begin{equation*} \sum_{d\divides n}f(d)=\sum_{d\divides n}f\Bigl(\frac nd\Bigr). \end{equation*} \end{theorem} We shall use this below for an alternative proof of Theorem~\ref{thm:Gauss} (p.~\pageref{thm:Gauss}) and for Theorem~\ref{thm:fnn} (p.~\pageref{thm:fnn}). Meanwhile, we have \begin{equation*} (f*g)(n)=\sum_{d\divides n}f\Bigl(\frac nd\Bigr)\cdot g(d), \end{equation*} or more simply \begin{equation}\label{eqn:f*g=g*f} f*g=g*f. \end{equation} The definition~\eqref{eqn:st} of $\msig$ and $\mtau$ can be written as \begin{align*} \msig&=\id*1,& \mtau&=1*1. \end{align*} Theorem~\ref{thm:f*1} is that if $f$ is multiplicative and $F=f*1$, then $F$ is multiplicative. The proof can be adapted to show that, if $f$ and $g$ are multiplicative, then so is $f*g$. Theorems~\ref{thm:m*1=e} and~\ref{thm:f*e=f} are \begin{align}\label{eqn:m1e,fef} \mmu*1&=\mep,& f*\mep&=f. \end{align} Then Theorem~\ref{thm:MIF}, M\"obius Inversion, is \begin{equation*} F=f*1\iff f=F*\mmu. \end{equation*} We proved this by manipulating indices of summation. Using such manipulations, we can show instead \begin{equation*} f*(g*h)=(f*g)*h. \end{equation*} By this and~\eqref{eqn:f*g=g*f}, Theorem~\ref{thm:MIF} is equivalent to \begin{equation*} f*1*\mmu=f; \end{equation*} but we can now understand this as an \emph{immediate} consequence of Theorems~\ref{thm:m*1=e} and~\ref{thm:f*e=f}, as expressed in~\eqref{eqn:m1e,fef}. By repeated convolution, we have the following equations: \begin{align*} \mmu*1&=\mep,&\mep*\mmu&=\mmu,\\ \mep*1&=1, & 1*\mmu&=\mep,\\ 1*1&=\mtau,&\mtau*\mmu&=1. \end{align*} You can read down the first column, and up the second; each row is an instance of M\"obius inversion. In short, we have a sequence \begin{equation*} \dots,\mmu,\mep,1,\mtau,\dots \end{equation*} where passage to the right is by convolving with $1$; and to the left, $\mmu$. Since $\id*1=\msig$, the corresponding sequence with $\msig$ is \begin{equation*} \dots,\id,\msig,\dots \end{equation*} We now define the entry to the left of $\id$ as $\ephi$. That is, \begin{equation}\label{eqn:ephi} \ephi=\id*\mmu. \end{equation} Then $\ephi$ is multiplicative, and \begin{equation*} \ephi(p^s)= \begin{cases} 1,&\text{ if }s=0,\\ p^s-p^{s-1},&\text{ if }s>0. \end{cases} \end{equation*} This is precisely the size of the set $\{x\colon 0\leq x0$; in any case, $\mpsi_p(d)\leq\ephi(d)$. \end{proof} \begin{corollary} Every prime number has a primitive root. \end{corollary} \begin{proof} $\mpsi_p(p-1)=\ephi(p-1)\geq1$. \end{proof} Now we can prove the necessity of (all of) Korselt's Criterion for being a Carmichael number (p.~\pageref{Korselt}):\index{Korselt's Criterion} \begin{theorem}\label{thm:Car-p-1} If $n$ is a Carmichael number, and $p\divides n$, then $p-1\divides n-1$. \end{theorem} \begin{proof} Given that $n$ is a Carmichael number and $p\divides n$, we let $a$ be a primitive root of $p$. Since $a^n\equiv a\pod n$, we have $a^n\equiv a\pod p$, and therefore $a^{n-1}\equiv1\pod p$. But $\ord pa=p-1$, so $p-1\divides n-1$. \end{proof} So now we know that the Carmichael numbers are \emph{precisely} those squarefree composite numbers $n$ such that $p\divides n\implies p-1\divides n-1$. We shall be able to give another characterization in \S\ref{sect:comp-roots}, once we know that squares of primes have primitive roots. \section{Discrete logarithms} The inverse of the function $\exp$ from $\R$ onto $(0,\infty)$ is the logarithm function\footnote{This function can be denoted by $\ln$, for \textbf{logarithmus naturalis,} in case one happens to want to use $\log$ to denote the inverse of the function $x\mapsto 10^x$.} $\log$, where as noted in \S\ref{sect:B}, $\log x=\int_1^x(\mathrm dt/t)$. We can use similar terminology for the inverse of an isomorphism $x\mapsto b^x$ from $\Zmod[p-1]$ to $\Zmodu[p]$. Here $b$ must be a primitive root of $p$, and if $b^x\equiv y\pod p$, we can write \begin{equation*} x\equiv\log_by\pmod{(p-1)}. \end{equation*} For example, \emph{modulo} $17$, we have Table~\ref{tab:17}. \begin{sidewaystable} \begin{equation*} \begin{array}{*{17}{|r}||l|}\hline k&0&1&2& 3& 4&5& 6& 7& 8& 9&10&11&12&13&14&15&\pmod{16}\\\hline 3^k&1&3&9&10&13&5&15&11&16&14& 8& 7& 4&12& 2& 6&\pmod{17}\\\hline \end{array} \end{equation*} Rearranged: \begin{equation*} \begin{array}{*{17}{|r}||l|}\hline 3^k&1& 2&3& 4&5& 6& 7& 8&9&10&11&12&13&14&15&16&\pmod{17}\\\hline k&0&14&1&12&5&15&11&10&2& 3& 7&13& 4& 9& 6& 8&\pmod{16}\\\hline \end{array} \end{equation*} \caption{Powers of $3$ \emph{modulo} $17$}\label{tab:17} \end{sidewaystable} 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\cdot14\equiv3^0\equiv1\pmod{17}$. We can define logarithms for any modulus that has a primitive root; then the base of the logarithms will be a primitive root. If $b$ is a primitive root of a modulus $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} $\ephi(n)$. Indeed, by Theorem~\ref{thm:ord}, \begin{equation*} b^x\equiv b^y\pmod n\iff x\equiv y\pmod{\ephi(n)}. \end{equation*} Then $\log_ba$ can be defined as the least non-negative such $s$. Another application of logarithms, besides multiplication problems, is congruences of the form \begin{equation*} x^d\equiv a\pmod n, \end{equation*} again where $n$ has a primitive root $b$. The last congruence is then equivalent to \begin{gather*} \log_b(x^d)\equiv\log_ba\pmod{\ephi(n)},\\ d\log_bx\equiv\log_ba\pmod{\ephi(n)}. \end{gather*} If this is to have a solution, then we must have \begin{equation*} \gcd(d,\ephi(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 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}{|c|*{10}{|r}||c|}\hline k& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9&\log_2\ell\pod{10}\\\hline 2^k\pod{11}&1 & 2& 4&-3& 5&-1&-2&-4& 3&-5&\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, $\gcd(a,n)=1$, and \begin{equation*} d=\gcd(k,\ephi(n)). \end{equation*} The following are equivalent: \begin{enumerate} \item\label{item:x^k} The congruence \begin{equation}\label{eqn:cong} x^k\equiv a\pmod n \end{equation} is soluble. \item\label{item:d} The congruence~\eqref{eqn:cong} has $d$ solutions. \item\label{item:a^phi} $a^{\ephi(n)/d}\equiv1\pmod n$. \end{enumerate} \end{theorem} \begin{proof} The following are equivalent: \begin{gather*} x^k\equiv a\text{ is soluble }\pmod n;\\ k\log x\equiv \log a\text{ is soluble }\pmod{\ephi(n)};\\ d\divides\log a;\\ \ephi(n)\divides\frac{\ephi(n)}d\cdot\log a; \end{gather*} \begin{gather*} \frac{\ephi(n)}d\cdot\log a\equiv0\pmod{\ephi(n)};\\ \log(a^{\ephi(n)/d})\equiv0\pmod{\ephi(n)};\\ a^{\ephi(n)/d}\equiv1\pmod n. \end{gather*} Thus~\eqref{item:x^k}$\Leftrightarrow$\eqref{item:a^phi}. Trivially,~\eqref{item:d}$\Rightarrow$\eqref{item:x^k}. Finally, assume~\eqref{item:x^k}, so that $d\divides\log a$, as above. Letting $r$ be the base of the logarithms, we have \begin{align*} x^k\equiv a\pmod n &\iff k\log x\equiv\log a\pmod{\ephi(n)}\\ &\iff\frac kd\cdot\log x\equiv\frac{\log a}d\pmod{\frac{\ephi(n)}d}\\ &\iff\log x\equiv\frac{\log a}k\pmod{\frac{\ephi(n)}d}\\ &\iff\begin{aligned}[t] \log x&\equiv\frac{\log a}k+\frac{\ephi(n)}d\cdot j\pmod{\ephi(n)},\\ & \text{ where }j\in\{0,1,\dots,d-1\} \end{aligned}\\ &\iff \begin{aligned}[t] x&\equiv r^{(\log a)/k}\cdot(r^{\ephi(n)/d})^j\pmod n,\\ &\text{ where }j\in\{0,1,\dots,d-1\}. \end{aligned} \end{align*} Finally, these $d$ solutions are incongruent. Indeed, since $\ord nr=\ephi(n)$, the powers $(r^{\ephi(n)/d})^j$ are incongruent; and $r^{(\log a)/k}$ is invertible. \end{proof} \section{Composite numbers with primitive roots}\label{sect:comp-roots} We know that all primes have primitive roots. Now we show that the numbers with primitive roots are precisely: \begin{align*} &2,&&4,&&p^s,&&2\cdot p^s, \end{align*} 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\ephi(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, $\ephi(k)=2^s-2^{s-1}=2^{s-1}$, which is even. In the second case, $\ephi(k)=\ephi(p^s)\cdot\ephi(m)$, which is even, since $\ephi(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{align*} a^{\ephi(m)}&\equiv 1\pmod m,& a^{\ephi(n)}&\equiv 1\pmod n, \end{align*} Therefore $a^{\lcm(\ephi(m),\ephi(n))}\equiv 1$ \emph{modulo} $m$ and $n$, and hence \emph{modulo} $\lcm(m,n)$, which is $mn$. By the lemma, $2$ divides both $\ephi(m)$ and $\ephi(n)$, so \begin{equation*} \lcm(\ephi(m),\ephi(n))\divides\frac{\ephi(m)\ephi(n)}2, \end{equation*} that is, $\lcm(\ephi(m),\ephi(n))\divides\ephi(mn)/2$. Therefore \begin{equation*} \ord{mn}a\leq\frac{\ephi(mn)}2, \end{equation*} so $a$ is not a primitive root of $mn$. \end{proof} \begin{theorem} If $k\geq1$, then $2^{2+k}$ has no primitive root. \end{theorem} \begin{proof} Any primitive root of $2^{2+k}$ must be odd. Let $a$ be odd. We shall show by induction that \begin{equation*} a^{\ephi(2^{2+k})/2}\equiv1\pmod{2^{2+k}}. \end{equation*} Since $\ephi(2^{2+k})=2^{2+k}-2^{1+k}=2^{1+k}$, it is enough to show \begin{equation*} a^{2^k}\equiv1\pmod{2^{2+k}}. \end{equation*} The claim is true when $k=1$, since $a^2\equiv1\pmod8$ for all odd numbers $a$. Suppose the claim is true when $k$ is \emph{some} positive integer $\ell$, that is, \begin{equation*} a^{2^{\ell}}\equiv1\pmod{2^{2+\ell}}. \end{equation*} This means \begin{equation*} a^{2^{\ell}}=1+2^{2+\ell}\cdot m \end{equation*} for some $m$. Now square: \begin{align*} a^{2^{1+\ell}} =(a^{2^{\ell}})^2 =(1+2^{2+\ell}\cdot m)^2 =&1+2^{3+\ell}\cdot m+2^{4+2\ell}\cdot m^2\\ =&1+2^{3+\ell}\cdot m\cdot(1+2^{1+\ell}\cdot m). \end{align*} Hence $a^{2^{1+\ell}}\equiv1\pmod{2^{3+\ell}}$, so our claim is true when $k=\ell+1$. \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$ and $\ell\geq1$, so that $p\divides\binom p2$ and $2\ell\geq1+\ell$, we have \begin{equation*} r^{(p-1)\cdot p^{\ell}} \equiv1+p^{1+\ell}\cdot m \not\equiv 1\pmod{p^{2+\ell}}. \end{equation*} Therefore we must have \begin{equation*} \ord{p^{2+\ell}}r=(p-1)\cdot p^{1+\ell}=\ephi(p^{2+\ell}), \end{equation*} which means $r$ is a primitive root of $p^{2+\ell}$. \end{proof} 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$, by Theorem~\ref{thm:p^2}. In fact, both are. Using $5\equiv-4\pmod9$, we have: \begin{equation*} \begin{array}{|c|r|r|}\hline k&2&3\\\hline 2^k\pmod9&4&-1\\\hline (-4)^k\pmod9&-2&-1\\\hline \end{array}, \end{equation*} so the order of $2$ and $-4$ is not $2$ or $3$ \emph{modulo} $9$; hence it must be $6$, since this is $\ephi(9)$. By Theorem~\ref{thm:p^n} then, $27$ has $6$ non-congruent primitive roots, each congruent \emph{modulo} $9$ to one of $2$ and $-4$; those roots then are $-13$, $-7$, $-4$, $2$, $5$, and $11$. Indeed, $\ephi(27)=18$ and we have \begin{equation*} \begin{array}{|c|*{7}{|r}|r|}\hline k& 2& 3& 4& 5& 6& 7& 8& 9\\\hline (-13)^k\pmod{27}& 7&-10& -5& 11& -8& -4& -2&-1\\\hline (-4)^k\pmod{27}&-11&-10& 13& 2& -8& 5& 7&-1\\\hline 5^k\pmod{27}& -2&-10& 4& -7& -8&-13&-11&-1\\\hline (-7)^k\pmod{27}& -5& 8& -2& 13& 10&-11& 4&-1\\\hline 2^k\pmod{27}& 4& 8&-11& 5& 10& -7& 13&-1\\\hline 11^k\pmod{27}& 13& 8& 7& -4& 10& 2& -5&-1\\\hline \end{array} \end{equation*} But does $18$ have a primitive root? The numbers $2$ and $-4$ cannot be primitive roots of $18$, since they are not prime to it; but $\ephi(18)=6$ and we have \begin{equation*} \begin{array}{|c|r|r|}\hline k&2&3\\\hline (-7)^k\pmod{18}&-5&-1\\\hline 5^k\pmod{18}&7&-1\\\hline \end{array} \end{equation*} so $-7$ and $5$ are primitive roots of $18$. \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$. Then $\gcd(r,2p^s)=1$, so $r$ has an order \emph{modulo} $2p^s$. Since also $\ord{p^s}r=\ephi(p^s)$, we have \begin{equation*} \ephi(p^s)\divides\ord{2p^s}r. \end{equation*} But also $\ord{2p^s}r\divides\ephi(2p^s)$; and $\ephi(p^s)=\ephi(2p^s)$. Hence $\ord{2p^s}r=\ephi(2p^s)$. \end{proof} \chapter{Quadratic reciprocity}\label{ch:qr} \section{Quadratic equations}%\asterism{} If $p\ndivides a$, then the linear congruence \begin{equation*} ax+b\equiv 0\pmod p \end{equation*} is always soluble. The next step is to consider quadratic congruences, \begin{equation}\label{eqn:gen-quad} ax^2+bx+c\equiv0\pmod p, \end{equation} where still $p\ndivides a$. For example, let us try to solve \begin{equation}\label{eqn:2,-8,9} 2x^2-8x+9\equiv0\pmod{11}. \end{equation} We cannot factorize the polynomial $2x^2-8x+9$ over $\Z$ (or even $\R$), since $8^2-4\cdot 2\cdot9=-8$, which is not a square (or even positive). However, after replacing coefficients with residues \emph{modulo} $11$, we may be able to factorize. Still, a better method of solution is \textbf{completing the square.} We have, \emph{modulo} $11$, \begin{align*} 2x^2-8x+9\equiv0 &\iff x^2-4x\equiv-\frac92\\ &\iff x^2-4x+4\equiv 4-\frac92\\ &\iff(x-2)^2\equiv-\frac12\equiv\frac{10}2\equiv 5. \end{align*} (We did not need to compute the inverse of $2$ \emph{modulo} $11$, although we may see easily enough that it is $6$.) If $5$ is a square \emph{modulo} $11$, then~\eqref{eqn:2,-8,9} has a solution; if not, not. One way to settle the question is by hunting: we have $5\equiv16\equiv4^2$, so \begin{align*} 2x^2-8x+9\equiv0 &\iff(x-2)^2\equiv4^2\\ &\iff x-2\equiv\pm4\\ &\iff x\equiv 2\pm 4\equiv6\text{ or }9. \end{align*} Note that we have used Lagrange's Theorem (Theorem~\ref{thm:Lagrange-n}) to conclude that the congruence has exactly two solutions. We now know \begin{equation*} 2x^2-8x+9\equiv2(x-6)(x+2)\equiv2(x-6)(x-9). \end{equation*} Possibly, with some cleverness, we might have been able to see this from the beginning. But suppose we want to solve \begin{equation}\label{eqn:1,-4,2} x^2-4x-3\equiv0\pmod{11}. \end{equation} We find \begin{align*} x^2-4x-3\equiv0 &\iff x^2-4x+4\equiv 7\iff(x-2)^2\equiv7. \end{align*} Now, if $7\equiv k^2$, then we may assume $-5\leq k<5$. The positive integers that are congruent to $7$ and are less than or equal to $5^2$ are $7$ and $18$, and neither of them is a square. Therefore the congruence~\eqref{eqn:1,-4,2} is insoluble. In particular, the polynomial $x^2-4x-3$ has no factorization over $\Zmod[11]$; so it would have been futile to hunt for a factorization. Completing the square is the way to go. Another way to see that $7$ has no square root \emph{modulo} $11$ is to note first that $2$ is a primitive root of $11$. Since $11\ndivides7$, but $7\equiv-4$, the following table shows that $7$ is not a square \emph{modulo} $11$, because $-4$ does not appear as an even power of $2$ (that is, a power of $2$ with even exponent): \begin{equation*} \begin{array}{|r|*5{|r}||l|}\hline k &0&1&2& 3&4&\operatorname{mod}5\\\hline 2^{2k}&1&4&5&-2&3&\operatorname{mod}11\\\hline \end{array} \end{equation*} Indeed, $2^m\equiv2^n\pod{11}$ if and only if $m\equiv n\pod{10}$, by Theorem~\ref{thm:ord}. Since $10$ is even, the only numbers prime to $11$ that are squares \emph{modulo} $11$ are the even powers of $2$. Considering the general quadratic congruence~\eqref{eqn:gen-quad}, and assuming $p$ is odd (so that $2$ is invertible \emph{modulo} $p$), we have \begin{align*} ax^2+bx+c\equiv 0 &\iff x^2+\frac bax\equiv-\frac ca\\ &\iff x^2+\frac bax+\frac{b^2}{4a^2}\equiv\frac{b^2}{4a^2}-\frac ca\\ &\iff\Bigl(x+\frac b{2a}\Bigr)^2\equiv \frac{b^2-4ac}{(2a)^2}, \end{align*} just as when one derives the usual quadratic formula. Working over $\R$, one knows that the equation $ax^2+bx+c=0$ (where $a\neq0$) is soluble if and only if $b^2-4ac\geq0$. Another way to express this condition is that the discriminant $b^2-4ac$ must be a \emph{square} in $\R$. It is the same \emph{modulo} $p$: the congruence~\eqref{eqn:gen-quad} is soluble if and only if $b^2-4ac$ is a square \emph{modulo} $p$. In the terminology introduced in \S\ref{sect:Wilson}, this condition is that $b^2-4ac$ either is divisible by $p$ or is a \textbf{quadratic residue}% \index{quadratic!--- residue}% \index{residue!quadratic ---} of $p$. As we have just observed, assuming $p\ndivides b^2-4ac$, one way to tell whether $b^2-4ac$ is a quadratic residue is first to find its least positive residue, say $m$, and then to check whether any of the residues $m+kp$ is a square, where $0\leq k$ and also $m+kp\leq((p-1)/2)^2$, that is, \begin{equation*} m+kp\leq\upvarpi^2, \end{equation*} in the notation of~\eqref{eqn:varpi} in \S\ref{sect:Wilson} (p.~\pageref{eqn:varpi}). So it is sufficient to check when $0\leq k<\upvarpi/2$. This could still be a lot of work if $p$ is large. We shall develop a way to test for quadratic residues that is more practical as well as theoretically interesting. \section{Quadratic residues}\label{sect:qr} We have just seen that the quadratic residues of $11$ are the even powers of $2$, namely $1$, $4$, $5$, $-2$, and $3$, or rather $1$, $4$, $5$, $9$, and $3$. The \textbf{quadratic non-residues}% \index{quadratic!--- non-residue}% \index{residue!quadratic non-{}---}% \index{non-residue, quadratic} are the odd powers: $2$, $-3$, $-1$, $-4$, and $-5$, that is, $2$, $8$, $10$, $7$, and $6$. So there are five residues, and five non-residues. (The general formulation of this equality will be Theorem~\ref{thm:eq}.) \begin{theorem}[Euler's Criterion]% \index{Euler!---'s Criterion}% \index{theorem!Euler's Criterion} %\sloppy 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}\label{eqn:1} a^{(p-1)/2}\equiv a^{\upvarpi}\equiv1\pmod p, \end{equation} and $a$ is a quadratic non-residue of $p$ if and only if \begin{equation}\label{eqn:-1} a^{\upvarpi}\equiv-1\pmod p. \end{equation} \end{theorem} \begin{proof} Let $r$ be a primitive root of $p$. Any solution of $x^2\equiv a\pmod p$ is $r^k$ for some $k$, and then \begin{equation*} a^{\upvarpi}\equiv(r^{2k})^{\upvarpi}\equiv(r^k)^{p-1}\equiv1\pmod{p} \end{equation*} by Fermat's Theorem (Theorem~\ref{thm:Fermat}). In any case, $a\equiv r^{\ell}\pmod p$ for some $\ell$. Suppose $a^{\upvarpi}\equiv1\pmod p$. Then \begin{equation*} 1\equiv(r^{\ell})^{\upvarpi}\equiv r^{\ell\cdot\upvarpi}\pmod p, \end{equation*} so $\ord pr\divides \ell\cdot\upvarpi$, that is, \begin{equation*} p-1\divides\ell\cdot\upvarpi. \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$. Since $a^{p-1}\equiv1\pmod p$, by Fermat's Theorem, we have $a^{\upvarpi}\equiv\pm1\pmod p$, so the second part of the claim follows. \end{proof} Another way to prove the theorem arises from the following considerations, which also lead to the alternative proof of Wilson's Theorem promised at the end of \S\ref{sect:Wilson} (p.~\pageref{Wilson}). 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 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_{\upvarpi})$ recursively. If $b_k$ has been chosen when $k<\ell<\upvarpi$, then let $b_{\ell}$ be the least element of $\{1,\dots,p-1\}\setminus\{b_1,a/b_1,\dots,b_{\ell-1},a/b_{\ell-1}\}$. Note then that $a/b_{\ell}$ must be in this set too, since otherwise $a/b_{\ell}=b_k$ for some $k$ such that $k<\ell$, and then $b_{\ell}=a/b_k$. We now have \begin{equation*} \Bigl\{b_1,\frac a{b_1},\dots,b_{\upvarpi},\frac a{b_{\upvarpi}}\Bigr\}=\{1,\dots,p-1\}. \end{equation*} Now multiply everything together: \begin{equation}\label{eqn:p-1} a^{\upvarpi}\equiv(p-1)!\pmod p. \end{equation} If we have Wilson's Theorem (Theorem~\ref{thm:Wilson}, p.~\pageref{thm:Wilson}), we can conclude~\eqref{eqn:-1}. Conversely, this and~\eqref{eqn:p-1} give us Wilson's Theorem. Now suppose $a$ is a quadratic residue of $p$. We choose the $b_k$ as before, except this time let $b_1$ be the least positive solution of $x^2\equiv a\pmod p$, and replace $a/b_1$ with the next least positive solution, which is $p-b_1$. We have then \begin{equation*} \Bigl\{b_1,p-b_1,b_2,\frac a{b_2},\dots,b_{\upvarpi},\frac a{b_{\upvarpi}}\Bigr\}=\{1,\dots,p-1\}, \end{equation*} and multiplication now gives us \begin{equation*} -a^{\upvarpi}\equiv(p-1)!\pmod p. \end{equation*} Now~\eqref{eqn:1} is equivalent to Wilson's Theorem. Since we do have~\eqref{eqn:1} when $a=1$, Wilson's Theorem holds.\footnote{This is the first proof of Wilson's Theorem given by Hardy and Wright~\cite[p.~68]{MR568909}.} \section{The Legendre symbol} Again, $p$ is an odd prime, and $p\ndivides a$. Euler's Criterion can be abbreviated by \begin{equation}\label{eqn:Leg-comp} a^{\upvarpi}\equiv\ls ap\pmod p, \end{equation} where $(a/p)$ is called the \textbf{Legendre symbol.}% \index{Legendre}% \index{Legendre!--- symbol}% \footnote{Named for Adrien-Marie Legendre, 1752--1833.} More precisely, we have \begin{equation*} \ls ap= \begin{cases} 1,&\text{ if $a$ is a quadratic residue of $p$};\\ -1,&\text{ if $a$ is a quadratic non-residue of $p$}. \end{cases} \end{equation*} \begin{theorem}\label{thm:ls} If $p$ is an odd prime not dividing $a$ or $b$, then: \begin{gather}\notag \ls{a\pm kp}p=\ls ap,\\\notag \ls{a^2}p=1,\\\notag \ls1p=1,\\\label{eqn:cases} \ls{-1}p= \begin{cases} 1,&\text{ if }p\equiv 1\pmod 4,\\ -1,&\text{ if }p\equiv3\pmod 4, \end{cases}\\\notag \ls{ab}p=\ls ap\ls bp. \end{gather} \end{theorem} \begin{proof} The first three equations follow immediately from the definitions; the others, from Euler's Criterion as summarized by~\eqref{eqn:Leg-comp}. (Also~\eqref{eqn:cases} is equivalent to Theorem~\ref{thm:Wilson-app} on page~\pageref{thm:Wilson-app}.) \end{proof} 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^{\upvarpi}\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\mod{19}, \end{gather*} so $(50/19)=-1$, which means the congruence $x^2\equiv50\pmod{19}$ has no solution. We may ask whether~\eqref{eqn:cases} has a simpler form, owing to the existence of only finitely many $p$ satisfying one of the cases. This possibility fails. \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} A similar argument \emph{fails} to show that there are infinitely many primes $p$ such that $p\equiv1\pod4$. For, even though $4q_1\cdot q_2\dotsm q_n-3\equiv1\pod4$, possibly all prime factors of $4q_1\cdot q_2\dotsm q_n-3$ are congruent to $3$. (This is the case when $n=1$ and $q_1=3$, for example.) 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$, which is distinct from each of the $q_k$. This means $s^2+1\equiv0\pmod p$, so $s$ is a solution of the congruence $x^2\equiv-1\pmod p$. Then $(-1/p)=1$, so $p\equiv 1\pmod 4$, by~\eqref{eqn:cases} above. \end{proof} From the rules so far, we obtain the following table: \begin{equation*} \begin{array}{|c*{12}{|r}|}\hline a&1&2&3&4&5&6&7&8&9&10&11&12\\\hline (a/13)&1& &1&1& & & & &1& 1& & 1\\\hline \end{array} \end{equation*} Indeed, under the squares $1$, $4$, and $9$, we put $1$. Also $4^2=16\equiv3$, so $(3/13)=1$. Finally, by~\eqref{eqn:cases}, we have $(-1/13)=1$; or we can just compute this: $(-1)^{\upvarpi}=(-1)^6=1$. Hence the table will be symmetric; that is, $(13-a/13)=(-a/13)=(-1/13)\cdot(a/13)=(a/13)$. In particular, $(10/13)=1$ and $(12/13)=1$. So half of the slots have been filled with $1$. The other half must take $-1$, by the following. \begin{theorem}\label{thm:eq} For all odd primes $p$, \begin{equation*} \sum_{k=1}^{p-1}\ls kp=0. \end{equation*} \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*} But $(r/p)=-1$, because $r$ is a primitive root and therefore $r^{\upvarpi}\equiv-1\pmod p$. Hence \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.\qedhere \end{equation*} \end{proof} So now we can complete the table above: \begin{equation*} \begin{array}{|c*{12}{|r}|}\hline a&1& 2&3&4& 5& 6& 7& 8&9&10&11&12\\\hline (a/13)&1&-1&1&1&-1&-1&-1&-1&1& 1&-1& 1\\\hline \end{array} \end{equation*} \section{Gauss's Lemma} Again, $p$ is an odd prime. Given an integer $k$, we have \begin{gather*} \Bigl[\frac kp\Bigr]\leq\frac kp<\Bigl[\frac kp\Bigr]+1,\\ p\cdot\Bigl[\frac kp\Bigr]\leq kp/2. \end{cases} \end{equation} Then $0\leq\size k_p

p/2$. whose least positive residues exceed $p/2$. \end{theorem} \begin{proof}%[Proof of Gauss's Lemma] If $\size{ka}_p=\size{\ell a}_p$, then $ka\equiv\pm\ell a\pod p$, so $k=\pm\ell\pod p$. Therefore \begin{equation*} \{1,2,\dots,\upvarpi\}=\{\size a_p,\size{2a}_p,\dots,\size{\upvarpi a}_p\}, \end{equation*} so \begin{equation*} \prod_{k=1}^{\upvarpi}k = \prod_{k=1}^{\upvarpi}\size{ka}_p. \end{equation*} Also $\size{ka}_p\equiv\pm ka\pod p$, and $\size{ka}_p\equiv-ka\pod p$ if and only if $ka$ has least positive residue exceeding $p/2$. Therefore, with $n$ as in the statement, we have \begin{equation*} \upvarpi!\cdot a^{\upvarpi} \equiv\prod_{k=1}^{\upvarpi}(ka) \equiv(-1)^n\cdot\prod_{k=1}^{\upvarpi}\size{ka}_p \equiv(-1)^n\cdot\prod_{k=1}^{\upvarpi}k \equiv(-1)^n\cdot\upvarpi!\mod p, \end{equation*} which yields the claim by Euler's Criterion. \end{proof} For example, to find $(3/19)$, we can look at \begin{align*} &3,&& 6,&& 9,&& 12,&& 15,&& 18,&& 21,&& 24,&& 27, \end{align*} whose remainders on division by $19$ are, respectively, \begin{align*} &3,&& 6,&& 9,&& 12,&& 15,&& 18,&& 2,&& 5,&& 8. \end{align*} Of these, only $12$, $15$, and $18$ exceed $19/2$, and they are three; so \begin{equation*} \ls3{19}=(-1)^3=-1. \end{equation*} 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 the following, which we shall also need in order to take full advantage of the Law of Quadratic Reciprocity: \begin{theorem}\label{thm:8} 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 $2\cdot1$, $2\cdot2$, \dots, $2\cdot\upvarpi$. 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}(-1,0)(4.5,0) \psline{->}(0,-1)(0,3.5) \psline(3.5,0)(3.5,2.5)(0,2.5) \uput[dl](0,0){$A$} \uput[ur](3.5,0){$B$} \uput[ur](3.5,2.5){$C$} \uput[ur](0,2.5){$D$} \psline(0,0)(3.5,2.5) \psline[linestyle=dotted](2,0)(2,1.429)(0,1.429) \uput[d](3.5,0){$\displaystyle\frac p2$} \uput[l](0,2.5){$q/2$} \uput[d](2,0){$k$} \uput[l](0,1.429){$kq/p$} \end{pspicture} \caption{Two ways of counting, for the Law of Quadratic Reciprocity}\label{fig:qr} \end{figure} The number of points in the interior of $ABCD$ with integral coordinates is $[p/2]\cdot[q/2]$, that is, $\upvarpi(p)\cdot\upvarpi(q)$. None of these points lie on the diagonal $AC$. The number of points in the interior of triangle $ABC$ with first coordinate $k$ and second coordinate integral is $[kp/q]$. Therefore the number of points in the interior of $ABC$ with integral coordinates is $\sum_{k=1}^{\upvarpi(p)}[kq/p]$. A similar consideration of triangle $ACD$ yields the claim. \end{proof} For example, suppose $p=13$ and $q=7$. The points that we count in the proof are shown in Figure~\ref{fig:qr2}. \begin{figure}[ht] \centering \begin{pspicture}(-1,-1)(7.5,4.5) \multips(1,0)(1,0){6}{\psdots[dotsize=1pt 1](0,1)(0,2)(0,3)} \psline{->}(-1,0)(7.5,0) \psline{->}(0,-1)(0,4.5) \psline(6.5,0)(6.5,3.5)(0,3.5) \uput[dl](0,0){$A$} \uput[ur](6.5,0){$B$} \uput[ur](6.5,3.5){$C$} \uput[ur](0,3.5){$D$} \psline(0,0)(6.5,3.5) \uput[d](6.5,0){$\displaystyle\frac{13}2$} \uput[l](0,3.5){$7/2$} \end{pspicture} \caption{Example of the proof of quadratic reciprocity}\label{fig:qr2} \end{figure} Counted in columns, the number of points inside $ABC$ is $0+1+1+2+2+3$, which is \begin{equation*} \Bigl[\frac7{13}\Bigr]+ \Bigl[\frac{14}{13}\Bigr]+ \Bigl[\frac{21}{13}\Bigr]+ \Bigl[\frac{28}{13}\Bigr]+ \Bigl[\frac{35}{13}\Bigr]+ \Bigl[\frac{42}{13}\Bigr]. \end{equation*} Counted in rows, the number of points inside $ACD$ is $1+3+5$, which is \begin{equation*} \Bigl[\frac{13}7\Bigr]+ \Bigl[\frac{26}7\Bigr]+ \Bigl[\frac{39}7\Bigr]. \end{equation*} The more useful form of the Law of Quadratic Reciprocity 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*} It is important to remember here that both $p$ and $q$ are \emph{odd primes.} We have not defined the symbol $(a/n)$ except when $n$ is an odd prime not dividing $a$. In this case, we can reduce the computation to computation of symbols $(p/q)$ by means of Theorems~\ref{thm:ls} and~\ref{thm:8}. \begin{table}[ht] \begin{align*} \ls{365}{941} &=\ls{5}{941}\ls{73}{941}&&\text{[factorizing]}\\ &=\ls{941}5\ls{941}{73}&&[5,73\equiv1\pod 4]\\ &=\ls15\ls{65}{73}&&\text{[dividing]}\\ &=\ls5{73}\ls{13}{73}&&\text{[factorizing]}\\ &=\ls{73}5\ls{73}{13}&&[5,13\equiv1\pod 4]\\ &=\ls35\ls8{13}&&\text{[dividing]}\\ &=\ls53\ls2{13}^3&&\text{[$5\equiv1\pod 4$; factorizing]}\\ &=\ls23\ls2{13}&&[(p/q)^2=1]\\ &=(-1)(-1)=1&&[3\equiv3\And13\equiv-3\pod 8]. \end{align*} \caption{Computation of $(365/941)$}\label{table:(365/941)} \end{table} For example, we can compute one Legendre symbol as in Table~\ref{table:(365/941)}. Similarly, we have \begin{equation*} \ls{47}{199} =-\ls{199}{47} =-\ls{11}{47} =\ls{47}{11} =\ls3{11} =-\ls{11}3 =-\ls23=1. \end{equation*} Thus we can compute any Legendre symbol $(a/p)$, as long as we can recognize which numbers less than $p$ are prime. The value of $(2/p)$ cannot be computed by the Law of Quadratic Reciprocity; we need Theorem~\ref{thm:8}. We \emph{can} use the Law to compute $(3/p)$ when we need it; but we can also compute it once for all as follows. \begin{theorem} For all primes greater than $3$, \begin{equation*} \ls 3p= \begin{cases} 1,&\text{ if }p\equiv\pm1\pmod{12},\\ -1,&\text{ if }p\equiv\pm5\pmod{12}. \end{cases} \end{equation*} \end{theorem} \begin{proof} We have \begin{gather*} \ls 3p= \begin{cases} \ls p3,&\text{ if }p\equiv1\pmod 4,\\ -\ls p3,&\text{ if }p\equiv 3\pmod 4, \end{cases}\\ \ls p3= \begin{cases} 1,&\text{ if }p\equiv1\pmod 3,\\ -1,&\text{ if }p\equiv2\pmod 3. \end{cases} \end{gather*} It is a Chinese remainder problem to compute \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}.\qedhere \end{align*} \end{proof} One could find a similar rule for $(q/p)$ for any fixed $q$. \section{Composite moduli}%\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{align*} x^2&\equiv a\pmod m,& x^2&\equiv a\pmod n \end{align*} 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{align*} x^2&\equiv365\pmod{23},& x^2&\equiv365\pmod{29}. \end{align*} 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{align*} x^2&\equiv2\pmod{11},&x^2&\equiv7\pmod{11} \end{align*} 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{align*} x^2&\equiv16\pmod{23},&x^2&\equiv13\pmod{29}. \end{align*} 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\equiv\pm19, \pm280\pmod{667}$, or alternatively \begin{equation*} x\equiv648,280,387,19\pmod{667}. \end{equation*} So now $x^2\equiv a\pmod n$ is soluble if and only if the congruences \begin{equation*} x^2\equiv a\pmod{p^{n(p)}} \end{equation*} are soluble, where $n=\prod_{p\divides n}p^{n(p)}$. \begin{theorem} If $p$ is odd, $p\ndivides a$, and $(a/p)=1$, then the congruence \begin{equation}\label{eqn:x2a} x^2\equiv a\pmod{p^k} \end{equation} has two solutions for each positive $k$. \end{theorem} \begin{proof} The set $\{x^2\colon x\in\Zmodu[p^k]\}$ consists of those $a$ in $\Zmodu[p^k]$ such that~\eqref{eqn:x2a} is soluble. For such $a$, we have $(a/p)=1$. Thus \begin{equation*} \{x^2\colon x\in\Zmodu[p^k]\}\included\{a\in\Zmodu[p^k]\colon(a/p)=1\}. \end{equation*} But we have also \begin{equation*} \size{\{a\in\Zmodu[p^k]\colon(a/p)=1\}}=\frac{\ephi(p^k)}2. \end{equation*} Indeed, this formula is correct when $k=1$, by Theorem~\ref{thm:eq} on page~\pageref{thm:eq}. Moreover, for every element $a$ of $\Zmod[p]$, exactly $p^{k-1}$ elements of $\Zmodu[p^k]$ have the residue $a$ \emph{modulo} $p$: those elements are $a$, $a+p$, $a+2p$, \dots, $a+(p^{k-1}-1)\cdot p$. This yields the claim for arbitrary positive $k$, since the value of $(a/p)$ depends only on the residue of $a$ \emph{modulo} $p$. Each congruence~\eqref{eqn:x2a} has at most $2$ solutions, and therefore \begin{equation*} \size{\{x^2\colon x\in\Zmodu[p^k]\}}\geq\frac{\ephi(p^k)}2. \end{equation*} For, if $x^2=y^2\pmod{p^k}$, then $p\divides(x+y)(x-y)$, but if $p$ divides both $x+y$ and $x-y$, then $p$ divides $2x$ and therefore $x$, and similarly $p\divides y$. Assuming we have neither of these conclusions, we have $p^k\divides x\pm y$, that is, $x\equiv\pm y\pod{p^k}$. Combining what we have so far yields \begin{equation*} \size{\{x^2\colon x\in\Zmodu[p^k]\}} =\size{\{a\in\Zmodu[p^k]\colon(a/p)=1\}}=\frac{\ephi(p^k)}2. \end{equation*} But we have also shown that the function $x\mapsto x^2$ from $\Zmodu[p^k]$ to itself sends at most two elements to the same element. Since $\Zmodu[p^k]$ has just $\ephi(p^k)$ elements, the squaring function must send \emph{exactly} two elements to the same element. This just means~\eqref{eqn:x2a} has exactly two solutions when $(a/p)=1$. \end{proof} In this proof, we have used a kind of pigeonhole principle:\index{Pigeonhole Principle}% \index{theorem!Pigeonhole Principle} If the $\ephi(p^k)$-many elements of $\Zmodu[p^k]$ are pigeons, and the squares of those elements are pigeon-holes, then there are at most two pigeons for each hole, so there are at least $\ephi(p^k)/2$-many holes; but there are at most $\ephi(p^k)/2$-many holes, therefore there are exactly that many, and there are two pigeons for each hole. An alternative argument that~\eqref{eqn:x2a} is soluble is by induction. Suppose $b^2\equiv a\pod{p^{k}}$ for some positive $k$. This means \begin{equation*} b^2=a+c\cdot p^{k} \end{equation*} for some $c$. Then \begin{align*} (b+p^{k}\cdot y)^2 &=b^2+2bp^{k}\cdot y+p^{2k}\cdot y^2\\ &=a+(c+2by)p^{k}+p^{2k}\cdot y^2 \end{align*} Therefore $(b+p^{k}\cdot y)^2\equiv a\pmod{p^{k+1}} \iff c+2by\equiv0\pmod p$. But the latter congruence is soluble, since $p$ is odd. We must finally consider powers of $2$. \begin{theorem} Suppose $a$ is odd. \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:all} $x^2\equiv a\pmod{2^{2+k}}$ is soluble for all positive $k$; \item\label{item:some} $x^2\equiv a\pmod{2^{2+k}}$ is soluble for some positive $k$; \item\label{item:8} $x^2\equiv a\pmod 8$ is soluble; \item\label{item:a18} $a\equiv 1\pmod 8$. \end{enumerate} \end{enumerate} \end{theorem} \begin{proof} The only hard part is to show that, if $a\equiv1\pod 8$, then for all positive $k$, the congruence $x^2\equiv a\pod{2^{2+k}}$ is soluble. We prove this by induction. It is easily true when $k=1$. Suppose it is true when $k=\ell$, and in fact $b^2\equiv a\pmod{2^{2+\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} $2^{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} \chapter{Sums of squares} Now we shall show that, if $n$ is a natural number, then the Diophantine equation \begin{equation}\label{eqn:4} x^2+y^2+z^2+w^2=n \end{equation} is soluble. This is easy when $n$ is $1$ or $2$, since \begin{align*} 1^2+0^2+0^2+0^2&=1,&1^2+1^2+0^2+0^2&=2. \end{align*} We continue by showing: \begin{compactenum}[1)] \item for each odd prime $p$,~\eqref{eqn:4} is soluble when $n=mp$ for some $m$ where $m{0}$, then $\{a+bn\colon n\in\N\}$ contains infinitely many primes. \end{theorem} That is in an arithmetic progression whose initial term is prime to the common difference, there are infinitely many primes. It is moreover possible to find arbitrary long arithmetic progressions consisting entirely of primes:\footnote{This theorem is not mentioned in Burton \cite{Burton}.} \begin{theorem}[Ben Green and Terence Tao, 2004 \cite{Green--Tao}] 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} 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 \textbf{twin primes}% \index{twin primes}% \index{prime!twin ---s} 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 cannot prove it. We do have: \begin{theorem}[Goldston, Pintz, Y\i ld\i r\i m, 2005 \cite{GPY}] For every positive real number $\epsilon$, there are primes~$p$ and~$q$ such that ${0}3$. (This exercise is used in Exercise~\ref{xca:perf-6}.) \end{xca} \begin{xca} If $p\equiv1\pmod3$ then $p\equiv1\pmod6$. \end{xca} \begin{xca} If $n\equiv2\pmod3$, then $n$ has a factor $p$ such that $p\equiv2\pmod3$. \end{xca} \begin{xca} Find all primes of the form $n^3-1$. \end{xca} \begin{xca} Find all $p$ such that $3p+1$ is square. \end{xca} \begin{xca} Find all $p$ such that $p^2+2$ is prime. \end{xca} \begin{xca} $n^4+4$ is composite unless $n=\pm1$. \end{xca} \begin{xca} If $n$ is positive, then $8^n+1$ is composite. \end{xca} \begin{xca} Find all integers $n$ such that the equation \begin{equation*} x^2=ny^2 \end{equation*} has only the zero solution. Prove your findings. \end{xca} \begin{xca} If $p_1<\dotsb1$), but $\{n\colon\msig(n)=k\}$ is finite. \end{xca} \begin{xca} Let $m\in\Z$. The number-theoretic function $n\mapsto n^m$ is multiplicative. \end{xca} \begin{xca}\label{xca:div-p} Let $\upomega(n)$ be the number of \emph{distinct} prime divisors of $n$, and let $m$ be a non-zero integer. Then $n\mapsto m^{\upomega(n)}$ is multiplicative. \end{xca} \begin{xca}\label{xca:Moebius-inv} Prove the other half of the M\"obius Inversion Theorem (Theorem~\ref{thm:MIF} on page~\pageref{thm:MIF}): if $F$ and $f$ are arithmetic functions such that \begin{equation*} f(n)=\sum_{d\divides n}\mmu\Bigl(\frac nd\Bigr)\cdot F(d), \end{equation*} then \begin{equation*} F(n)=\sum_{d\divides n}f(d). \end{equation*} \end{xca} \begin{xca}\label{xca:Mangoldt-2} Let $\Lambda$ be the Mangoldt function defined in Exercise~\ref{xca:Mangoldt}. \begin{compactenum} \item $\log n=\displaystyle\sum_{d\divides n}\Lambda(d)$. \item $\Lambda(n)=\displaystyle\sum_{d\divides n}\mmu\Bigl(\frac nd\Bigr)\log d$. \item $\Lambda(n)=-\displaystyle\sum_{d\divides n}\mmu(d)\log d$. \end{compactenum} \end{xca} \begin{xca} $\prod_{p\divides n}(1-p)=\sum_{d\divides n}\mmu(d)\cdot d$. \end{xca} \begin{xca}\label{ex:f-mult} If $f$ is multiplicative and non-zero, then \begin{equation*} \sum_{d\divides n}\mmu(d)\cdot f(d)=\prod_{p\divides n}(1-f(p)). \end{equation*} \end{xca} \begin{xca} If $\upomega$ is as in Exercise \ref{xca:div-p}, then $\displaystyle\sum_{d\divides n}\mmu(d)\cdot\mtau(d)=(-1)^{\upomega(n)}$. \end{xca} %\section{Exercise Set} %set VII \begin{xca} $f(568)=f(638)$ when $f\in\{\mtau,\msig,\ephi\}$. \end{xca} \begin{xca} Solve: \begin{compactenum} \item $n=2\ephi(n)$. \item $\ephi(n)=\ephi(2n)$. \item $\ephi(n)=12$. (Do this without a table. There are 6 solutions.) \end{compactenum} \end{xca} \begin{xca} Find a sequence $(a_n\colon n\in\N)$ of positive integers such that \begin{equation*} \lim_{n\to\infty}\frac{\ephi(a_n)}{a_n}=0. \end{equation*} (If you assume that there \emph{is} an answer to this problem, then it is not hard to see what the answer must be. To actually \emph{prove} that the answer is correct, recall that, formally, \begin{equation*} \sum_n\frac 1n=\prod_p\frac1{1-\frac1p}, \end{equation*} so $\displaystyle\lim_{n\to\infty}\prod_{k=1}^n\frac1{1-\frac1{p_k}}=\infty$ if $(p_k\colon k\in\N)$ is the list of primes.) \end{xca} \begin{xca} Prove $\displaystyle\sum_{d\divides n}\mmu(d)\ephi(d)=\prod_{p\divides n}(2-p)$. (This is a special case of Exercise~\ref{ex:f-mult}.) \end{xca} \begin{xca} If $n$ is squarefree, and $k\geq0$, show \begin{equation*} \sum_{d\divides n}\msig(d^k)\ephi(d)=n^{k+1}. \end{equation*} \end{xca} \begin{xca} $\displaystyle\sum_{d\divides n}\msig(d)\ephi\Bigl(\frac nd\Bigr)=n\mtau(n)$. \end{xca} \begin{xca} $\displaystyle\sum_{d\divides n}\mtau(d)\ephi\Bigl(\frac nd\Bigr)=\msig(n)$. \end{xca} \begin{xca} \begin{compactenum} \item Show $a^{100}\equiv1\pmod{1000}$ if $\gcd(a,1000)=1$. \item Find $n$ such that $n^{101}\not\equiv n\pmod{1000}$. \end{compactenum} \end{xca} \begin{xca}\label{ex:a13} \begin{compactenum} \item Show $a^{24}\equiv1\pmod{35}$ if $\gcd(a,35)=1$. \item\label{a13} Show $a^{13}\equiv a\pmod{35}$ for all $a$. \item Is there $n$ such that $n^{25}\not\equiv n\pmod{35}$? \end{compactenum} \end{xca} \begin{xca} If $\gcd(m,n)=1$, show $m^{\ephi(n)}\equiv n^{\ephi(m)}\pmod{mn}$. \end{xca} \begin{xca} If $n$ is odd, and is not a prime power, and if $\gcd(a,n)=1$, show $a^{\ephi(n)/2}\equiv 1\pmod n$. (This generalizes Exercise~\ref{ex:a13}\eqref{a13}.) \end{xca} \begin{xca} Solve $5^{10000}x\equiv1\pmod{153}$. \end{xca} %\section{Exercise Set} %set VIII \begin{xca} We have $(\pm3)^2\equiv2\pmod7$. Compute the orders of $2$, $3$, and~$-3$, \emph{modulo} $7$. \end{xca} \begin{xca} Suppose $\ord na=k$, and $b^2\equiv a\pmod n$. \begin{compactenum} \item Show that $\ord nb\in\{k,2k\}$. \item Find an example for each possibility of $\ord nb$. \item Find a condition on $k$ such that $\ord nb=2k$. \end{compactenum} \end{xca} \begin{xca} This is about $23$: \begin{compactenum} \item\label{part:a} Find a primitive root of least absolute value. \item How many primitive roots are there? \item Find these primitive roots as powers of the root found in~\eqref{part:a}. \item Find these primitive roots as elements of $[-11,11]$. \end{compactenum} \end{xca} \begin{xca} Assuming $\ord pa=3$, show: \begin{compactenum} \item $a^2+a+1\equiv0\pmod3$; \item $(a+1)^2\equiv a\pmod 3$; \item $\ord p{a+1}=6$. \end{compactenum} \end{xca} \begin{xca} Find all elements of $[-30,30]$ having order $4$ \emph{modulo} $61$. \end{xca} \begin{xca} $f(x)\equiv0\pmod n$ may have more than $\deg(f)$ solutions: \begin{compactenum} \item Find four solutions to $x^2-1\equiv0\pmod{35}$. \item Find conditions on $a$ such that the congruence $x^2-a^2\equiv0\pmod{35}$ has four distinct solutions, and find these solutions. \item If $p$ and $q$ are odd primes, find conditions on $a$ such that the congruence $x^2-a^2\equiv0\pmod{pq}$ has four distinct solutions, and find these solutions. \end{compactenum} \end{xca} \begin{xca} If $\ord na=n-1$, then $n$ is prime. \end{xca} \begin{xca} If $a>1$, show $n\divides\ephi(a^n-1)$. \end{xca} \begin{xca} If $2\ndivides p$ and $p\divides n^2+1$, show $p\equiv1\pmod4$. \end{xca} \begin{xca}\mbox{} \begin{compactenum} \item Find conditions on $p$ such that, if $r$ is a primitive root of $p$, then so is $-r$. \item If $p$ does not meet these conditions, then what is $\ord p{-r}$? \end{compactenum} \end{xca} %\section{Exercise Set} %set IX \begin{xca}\label{IX.1} For $(\Z/(17))^{\times}$: \begin{compactenum} \item\label{IX.1(a)} construct a table of logarithms using $5$ as the base; \item\label{IX.1(b)} using this (or some other table, with a different base), solve: \begin{compactenum} \item $x^{15}\equiv14\pmod{17}$; \item $x^{4095}\equiv14\pmod{17}$; \item $x^4\equiv4\pmod{17}$; \item $11x^4\equiv7\pmod{17}$. \end{compactenum} \end{compactenum} \end{xca} \begin{xca} If $n$ has primitive roots $r$ and $s$, and $\gcd(a,n)=1$, prove \begin{equation*} \log_sa\equiv\frac{\log_ra}{\log_rs}\pmod{\ephi(n)}. \end{equation*} \end{xca} \begin{xca} In $(\Z/(337))^{\times}$, for any base, show \begin{equation*} \log(-a)\equiv\log a+168\pmod{336}. \end{equation*} \end{xca} \begin{xca} Solve $4^x\equiv13\pmod{17}$. \end{xca} \begin{xca}\label{xca:ord-prod} \begin{compactenum} \item If $\ord ra$ and $\ord rb$ are relatively prime, show \begin{equation*} \ord r{ab}=\lcm(\ord ra,\ord rb). \end{equation*} \item Show that this may fail if $\ord ra$ and $\ord rb$ are not relatively prime. \end{compactenum} \end{xca} \begin{xca} How many primitive roots has $22$? Find them. \end{xca} \begin{xca}\label{IX.6} Find a primitive root of $1250$. \end{xca} \begin{xca} Define the function $\uplambda$ by the rules \begin{align*} \uplambda(2^k)&= \begin{cases} \ephi(2^k),&\text{ if }00;\\ 0,&\text{ if }n\leq02$). \item We could also let $\ell$ be a factor of $1965$, and then let $k$ be a factor of $\ell$. \item Finally, since $11\ndivides 1965$, we have by Fermat $1965^{10}\equiv1\pmod{11}$, so we could let $k=11$ and $\ell=10$. \end{compactenum} \end{remark} \begin{problem} Find two positive integers $a$ and $b$ such that, for all integers $m$ and $n$, the integer $am-bn$ is a solution of the congruences \begin{align*} x&\equiv m\pmod{999},& x\equiv n\pmod{1001}. \end{align*} \end{problem} \begin{solution} A solution of the congruences takes the form \begin{equation*} x\equiv m\cdot 1001s+n\cdot 999t\pmod{999\cdot 1001}, \end{equation*} where $1001s\equiv1\pmod{999}$ and $999t\equiv 1\pmod{1001}$. So we want \begin{align*} 2s&\equiv 1,&s&\equiv 500\pmod{999},& -2t&\equiv1,&t&\equiv500\pmod{1001}. \end{align*} Then the solution to the original congruences is \begin{equation*} x\equiv m\cdot 1001\cdot 500+n\cdot 999\cdot 500 \equiv 1001\cdot 500m-999\cdot 501n\pmod{999\cdot 1001}. \end{equation*} So we can let \fbox{$a=1001\cdot500$, $b=999\cdot 501$.} \end{solution} \begin{remark} This is just a Chinese Remainder Theorem problem with letters instead of numbers. \end{remark} \begin{problem} Letting $n=\sum_{j=1}^{408}j$, find an integer $k$ such that $0\leq k<409$ and \begin{equation*} 408!\equiv k\pmod n. \end{equation*} \end{problem} \begin{solution} We have $n=409\cdot 408/2$; also $409$ is prime, so by Wilson's Theorem $408!\equiv-1\pmod{409}$. Then $408!\equiv 408$ \emph{modulo} both $409$ and $408$, hence \emph{modulo} any divisor of the least common multiple of these. But $n$ is such a divisor. Thus we can let \fbox{$k=408$.} \end{solution} \begin{remark} This problem is based on Exercise %49(a) \ref{xca:p-1}. A number of people argued as follows. \begin{quote} Since $408!\equiv-1\pod{409}$, we must have $k\equiv-1\pod{409}$. Since it is required that $0\leq k<409$, it must be that $k=408$. \end{quote} But this argument does \emph{not} prove $408!\equiv408\pod n$. Maybe I made a mistake, and there is \emph{no} $k$ meeting the stated conditions. \end{remark} \begin{problem} With justification, find an integer $n$, greater than $1$, such that, for all integers $a$, \begin{equation*} a^n\equiv a\pmod{1155}. \end{equation*} \end{problem} \begin{solution} We have $1155=3\cdot 5\cdot 7\cdot 11$, and $\gcd(3-1,5-1,7-1,11-1)=\gcd(2,4,6,10)=60$. Then we can let \fbox{$n=61$.} Indeed, by Fermat, \begin{compactitem} \item If $3\ndivides a$, then $a^2\equiv1\pod 3$, so $a^{60}\equiv1\pod3$. \item If $5\ndivides a$, then $a^4\equiv1\pod 5$, so $a^{60}\equiv1\pod5$. \item If $7\ndivides a$, then $a^6\equiv1\pod 7$, so $a^{60}\equiv1\pod7$. \item If $11\ndivides a$, then $a^{10}\equiv1\pod{11}$, so $a^{60}\equiv1\pod{11}$. \end{compactitem} Therefore, for all $a$, we have $a^{61}\equiv a$ \emph{modulo} any of $3$, $5$, $7$, and $11$, hence \emph{modulo} their least common multiple, which is $1155$. \end{solution} \begin{remark} This problem is related to Exercise %43 \ref{xca:13} and our discussion of absolute pseudoprimes. \end{remark} \begin{problem} Let $\N=\{1,2,3,\dots\}$. Suppose all we know about this set is: \begin{compactenum}[(i)] \item proofs by induction are possible; \item addition can be defined on $\N$, and it satisfies \begin{align*} x+y&=y+x,&x+(y+z)&=(x+y)+z; \end{align*} \item multiplication can be defined by \begin{align*} x\cdot 1&=x,&x\cdot(y+1)&=x\cdot y+x. \end{align*} \end{compactenum} Prove \begin{equation*} x\cdot y=y\cdot x. \end{equation*} \end{problem} \begin{solution} We use induction on $y$. As the base step, we show $x\cdot 1=1\cdot x$ for all $x$. We do \emph{this} by induction: Trivially, $1\cdot1=1\cdot 1$. Suppose, as an inductive hypothesis, $x\cdot1=1\cdot x$ for some $x$. Then \begin{align*} 1\cdot(x+1)&=1\cdot x+1&&\text{[by definition of multiplication]}\\ &=x\cdot 1+1&&\text{[by inductive hypothesis]}\\ &=x+1&&\text{[by definition of multiplication]}\\ &=(x+1)\cdot 1.&&\text{[by definition of multiplication]} \end{align*} By induction then, $x\cdot1=1\cdot x$. Next we assume $x\cdot y=y\cdot x$ for all $x$, for some $y$, and we prove $x\cdot(y+1)=(y+1)\cdot x$. We do \emph{this} by induction on $x$. By what we have already shown, $1\cdot(y+1)=(y+1)\cdot1$. Suppose, as an inductive hypothesis, $x\cdot(y+1)=(y+1)\cdot x$ for some $x$. Then \begin{align*} (x+1)\cdot(y+1) &=(x+1)\cdot y+x+1&&\text{[by definition of multiplication]}\\ &=y\cdot(x+1)+x+1&&\text{[by the first inductive hypothesis]}\\ &=y\cdot x+y+x+1&&\text{[by definition of multiplication]}\\ &=x\cdot y+x+y+1&&\text{[by the first inductive hypothesis]}\\ &=x\cdot(y+1)+y+1&&\text{[by definition of multiplication]}\\ &=(y+1)\cdot x+y+1&&\text{[by the second inductive hypothesis]}\\ &=(y+1)\cdot(x+1).&&\text{[by definition of multiplication]} \end{align*} This completes the proof that $x\cdot(y+1)=(y+1)\cdot x$ for all $x$. \emph{This} completes the proof that $x\cdot y=y\cdot x$ for all $x$ and $y$. \end{solution} \begin{remark} This is part of Exercise \ref{xca:A}. I tried to write out a ``first generation'' proof: one you might write without thinking of how to break it into parts. A proof that is easier to follow is perhaps the ``second generation'' proof that goes as follows (see Lemma A.3 and Theorem A.3): First show \begin{equation}\label{eqn:x1} x\cdot1=1\cdot x \end{equation} by induction on $x$, then show \begin{equation}\label{eqn:y+1} (y+1)\cdot x=y\cdot x+x \end{equation} by induction on $x$, and finally show $x\cdot y=y\cdot x$ by induction on $x$. In fact, almost all students just \emph{assumed} that~\eqref{eqn:x1} and~\eqref{eqn:y+1} were known; but they were \emph{not} among the propositions that the problem allowed you to use. \end{remark} \section{In-term examination} \begin{problem} Exactly one of $1458$ and $1536$ has a primitive root. Which one, and why? Find a primitive root of the number that has one. \end{problem} \begin{solution} $1458=2\cdot729=2\cdot 3^6$ and $1536=3\cdot 512=3\cdot 2^9$. The numbers with primitive roots are just $2$, $4$, $p^k$, and $2\cdot p^k$, where $p$ is an \emph{odd} prime. Therefore $1458$, but not $1536$, has a primitive root. $\upphi(9)=6$, and \begin{equation*} \begin{array}{*8{|r}|}\hline k&1&2&3&4&5&6&\\\hline 5^k&5&-2&-1&4&2&1&\bmod 9\\\hline \end{array} \end{equation*} so $5$ is a primitive root of $9$. Then $5$ is a primitive root of $3^6$. Since $5$ is odd, it is a primitive root of $1458$. \end{solution} \begin{remark} \begin{asparaenum}[1.] \item A number of people computed $\upphi(1458)$ and $\upphi(1536)$, but this is of no practical use in this problem. \item Some people pointed out that if $a$ is a primitive root of $n$, then $a^{\upphi(n)}\equiv1\pmod n$. This is logically correct, but useless, since by Euler's Theorem we have $a^{\upphi(n)}\equiv1\pmod n$ whenever $\gcd(a,n)=1$ (not just when $a$ is a primitive root). \item Our sequence of theorems about primitive roots of composite numbers is the following. Throughout, $p$ is an odd prime. \begin{compactenum}[(i)] \item If $r$ is a primitive root of $p$, then $r$ or $r+p$ is a primitive root of $p^2$. \item If $r$ is a primitive root of $p^2$, then $r$ is a primitive root of $p^s$ whenever $s\geqslant2$. \item If $r$ is a primitive root of $p^s$ (where $s\geqslant2$), then $r$ or $r+p^s$ (whichever is odd) is a primitive root of $2p^s$. \end{compactenum} Some people misremembered this sequence, or wrongly combined two of its theorems. For example, some wrote `If $r$ is a primitive root of $p$, then $r$ or $r+p^s$ (whichever is odd) is a primitive root of $2p^s$.' This assertion is false. It would be correct to say for example, `If $r$ is a primitive root of $p^2$, then $r$ or $r+p^2$ (whichever is odd) is a primitive root of $2p^s$.' Using this, one might observe that $2$ is a primitive root of $9$, and therefore $11$ is a primitive root of $1458$. \end{asparaenum} \end{remark} \begin{problem} Remembering that $p$ is always prime, define the arithmetic function $\upomega$ by \begin{equation*} \upomega(n)=\sum_{p\divides n}1. \end{equation*} \begin{enumerate} \item Define $\upmu$, preferably using $\upomega$. \item Prove that, if $m$ and $n$ are co-prime, then $\upomega(mn)=\upomega(m)+\upomega(n)$. \item Prove that \begin{equation*} \sum_{d\divides n}\uptau(d)\cdot\upmu(d)=(-1)^{\upomega(n)}. \end{equation*} \item Find a simple description of the function $f$ given by \begin{equation*} f(n)=\sum_{d\divides n}\upomega(d)\cdot\upmu\Bigl(\frac nd\Bigr). \end{equation*} \end{enumerate} \end{problem} \begin{solution} \begin{asparaenum} \item $\mu(n)=\begin{cases} 0,&\text{ if }p^2\divides n \text{ for some }p,\\ (-1)^{\upomega(n)},&\text{ if }p^2\divides n \text{ for no }p. \end{cases}$. \item Assume $m$ and $n$ are co-prime. If $p\divides mn$, then \begin{equation*} p\divides m\iff p\ndivides n. \end{equation*} Therefore \begin{equation*} \upomega(mn)=\sum_{p\divides mn}1=\sum_{p\divides m}1+\sum_{p\divides n}1 =\upomega(m)+\upomega(n). \end{equation*} \item Each side of the equation is multiplicative, and \begin{equation*} \sum_{d\divides p^k}\uptau(d)\cdot\upmu(d)=\uptau(1)\cdot\upmu(1)+\uptau(p)\cdot\upmu(p)=1-2=(-1)^{\upomega(p^k)}. \end{equation*} \item By M\"obius inversion, \begin{equation*} \upomega(n)=\sum_{d\divides n}f(d). \end{equation*} Since also $\upomega(n)=\sum_{p\divides n}1$, we have \begin{equation*} f(n)=\begin{cases} 1,&\text{ if $n$ is prime},\\ 0,&\text{ if $n$ is not prime.} \end{cases} \end{equation*} \end{asparaenum} \end{solution} \begin{remark} \begin{asparaenum}[1.] \item In my solution to part a, the condition `$p^2\divides n$ for no $p$' is equivalent to `$p^2\ndivides n$ for all $p$'. Similarly in part d. \item For part a, some people wrote (as part of their answer) `$\upmu(n)=(-1)^s$ if $n=p_1\dotsm p_s$'. Strictly, one must specify that the $p_i$ are all distinct. The best way that I know to do this is to say $p_1<\cdots