\documentclass[11pt]{article} \usepackage{amsmath,amssymb,amsthm,amsfonts,verbatim} \usepackage{microtype} \usepackage{url} \addtolength{\evensidemargin}{-.6in} \addtolength{\oddsidemargin}{-.6in} \addtolength{\textwidth}{1.0in} \addtolength{\textheight}{2.1in} \addtolength{\topmargin}{-.8in} \theoremstyle{plain} \theoremstyle{definition} \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{challenge}[theorem]{Challenge Problem} \newtheorem*{theoremp}{Theorem~\ref{squaremodp}} \title{\vspace{-20pt}Elementary Number Theory\\ \normalsize Math 175, Section 30, Autumn 2010\\ \large Shmuel Weinberger ({\tt shmuel@math.uchicago.edu})\\ Tom Church ({\tt tchurch@math.uchicago.edu})\\ \url{www.math.uchicago.edu/~tchurch/teaching/175/}} \author{} \date{} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\C}{\mathbb{C}} % \DeclareMathOperator{\sin}{sin} %% just an example (it's already defined) \DeclareMathOperator{\norm}{norm} \renewcommand{\baselinestretch}{1.2} \begin{document} \maketitle \setcounter{section}{3} \vspace{15pt} \begin{center} {\huge \bf Script 3: Congruence in the Integers} \end{center} \vspace{40pt} \renewcommand{\baselinestretch}{1.5} \begin{definition} Fix $n\in\Z$ with $n>1$. We say that two integers $a$ and $b$ are {\em congruent modulo $n$} and write $a\equiv b\pmod{n}$ provided that $n\,|\,(b-a)$. \end{definition} \begin{theorem} Fix $n>1$. Then congruence modulo $n$ is an equivalence relation on $\Z$. That is: \begin{enumerate} \item[(i)] If $a\in \Z$, then $a\equiv a\pmod{n}$. \item[(ii)] If $a, b\in \Z$, then $a\equiv b\pmod{n}$ if and only if $b\equiv a\pmod{n}$. \item[(iii)] If $a, b, c\in \Z$ and $a\equiv b\pmod{n}$ and $b\equiv c\pmod{n}$, then $a\equiv c\pmod{n}$. \end{enumerate} \end{theorem} \begin{theorem} If $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then \begin{enumerate} \item[(i)] $a+c\equiv b+d\pmod{n}$ \item[(ii)] $a\cdot c\equiv b\cdot d\pmod{n}$ \end{enumerate} \end{theorem} \begin{theorem} If $a\equiv b\pmod{n}$, then $ac\equiv bc\pmod{nc}$ for any $c>0$. \end{theorem} \begin{theorem} If $(a, n)=1$, then there exists $b\in\Z$ such that $a\cdot b \equiv 1\pmod{n}$. \end{theorem} \begin{theorem} Given $c\in\Z$, if $(a, n)=1$, then the congruence $ax\equiv c\pmod{n}$ has a solution for $x$ in the integers. \end{theorem} \pagebreak \begin{exercise} Solve the following congruences for $x$: \begin{enumerate} \item[a)] $3x\equiv 1\pmod{7}$ \item[b)] $8x\equiv 11\pmod{23}$ \item[c)] $25x+1\equiv 0\pmod{126}$ \item[d)] $22x\equiv 2\pmod{178}$ \end{enumerate} \end{exercise} \begin{theorem} If $a$ and $n$ are relatively prime, then \vskip-20pt \[ax\equiv ay\pmod{n} \quad\text{if and only if}\quad x\equiv y\pmod{n}.\] \end{theorem} \begin{theorem} If $m=(a, n)$, then \vskip-20pt \[ax\equiv ay\pmod{n} \quad\text{if and only if}\quad x\equiv y\pmod{\frac{n}{m}}.\] \end{theorem}\vskip20pt \begin{definition} A number system (a collection of elements equipped with an addition operation and a multiplication operation) is called a \emph{commutative ring with identity} (\mbox{sometimes} just called a \emph{ring} if the context is clear) if it satisfies Axioms A1--A5, M1--M4, and D. \end{definition} \begin{definition} A number system is called a \emph{field} if it satisfies Axioms A1--A5, M1--M4, and D (i.e. it is a ring), and in addition satisfies Axiom M5, which states that every nonzero element has a multiplicative inverse: \begin{enumerate} {\bf \item[M5.] (Multiplicative Inverses)} For each nonzero element $a\neq 0$, there is a unique element $a^{-1}$ such that $a\cdot a^{-1}=1$ and $a^{-1}\cdot a=1$. \end{enumerate} \end{definition} \vskip20pt \begin{definition} Fix $n\in \Z$ with $n>1$. For an integer $a\in \Z$, the \emph{residue class of $a$ modulo $n$}, or sometimes just the \emph{residue class of $a$}, is the set of all integers congruent to $a$ (mod $n$): \[[a]=\big\{b\in \Z\ \big\vert\ a\equiv b\pmod{n}\big\}\] \end{definition} \begin{exercise} Given $a,b\in \Z$, we have \[[a]=[b]\quad\text{if and only if}\quad a\equiv b\pmod{n}\] \end{exercise} \begin{theorem} The number of distinct residue classes modulo $n$ is $n$. \end{theorem} \begin{theorem} If $[a]=[b]$, then $(a,n)=(b,n)$. \end{theorem} \begin{definition} Fix $n>1$. We define the number system $\Z/n\Z$ to be the set of residue classes modulo $n$. We define addition and multiplication in $\Z/n\Z$ as follows: \begin{align*} [a]+[b]&=[a+b]\qquad\qquad\text{ for $a,b\in \Z$}\\ [a]\cdot[b]\ \,&=[a\cdot b]\qquad\qquad\ \,\text{ for $a,b\in \Z$} \end{align*} \end{definition} \begin{theorem} Show that addition and multiplication are well-defined in $\Z/n\Z$. \end{theorem} \begin{exercise} Check that $\Z/n\Z$ is a commutative ring with identity for any $n>1$. \end{exercise} \begin{theorem} Show that $\Z/p\Z$ is a field if and only if $p$ is prime. \end{theorem}\vskip20pt \begin{theorem} If $p$ is prime and $a,b\in \Z/p\Z$, then $a\neq 0$ and $b\neq 0$ implies $ab\neq 0$. \end{theorem} \begin{definition}If $R$ is a commutative ring with identity, then an element $x\in R$ is called a \emph{unit} if $x$ has a multiplicative inverse in $R$. We write $R^{\times}$ (pronounced ``R-cross'') for the set of invertible elements: \[R^\times=\big\{x\in R\big|x\cdot y=1\text{ for some }y\in R\big\}\] \end{definition} \begin{theorem} For any ring $R$, the set $R^\times$ is closed under multiplication. \end{theorem}\vskip20pt \begin{theorem}[Wilson's Theorem] If $p$ is prime, then $(p-1)!\equiv -1\; \pmod{p}$.\newline (It may be helpful to consider $p=2$ as a separate case.) \end{theorem} \begin{exercise} If $p$ is prime and $a\in \Z/p\Z$ is nonzero, the sets\newline \phantom{x}\qquad\qquad\qquad$\big\{x\big|x\in \Z/p\Z, x\neq 0\big\}$\quad and\quad $\big\{ax\big|x\in \Z/p\Z, x\neq 0\}$\quad are equal. \end{exercise} \begin{theorem} If $p$ is prime and $a\in\Z$ with $p\not| \,a$, then $a^{p-1}\equiv 1\; \pmod{p}$. \end{theorem} \begin{theorem}[Fermat's Little Theorem] If $p$ is prime and $a\in\Z$, then $a^p\equiv a\; \pmod{p}$. \end{theorem}\vskip20pt \begin{theorem} Let $p$ be prime. Then $x^2\equiv 1\; \pmod{p}$ if and only if $x\equiv \pm 1\; \pmod{p}$. \end{theorem} \begin{theorem} Let $p$ be an odd prime. Then the congruence $x^2\equiv -1\; \pmod{p}$ has solutions if and only if $p\equiv 1\pmod{4}$. \end{theorem} \begin{exercise} If $q$ is prime and $q\equiv 3\pmod{4}$, and $d\in \Z/q\Z$, then $d$ and $-d$ cannot both be squares\footnote{As you would expect, an element of a ring is called a \emph{square} if it is equal to $y^2$ for some element $y$.} in $\Z/q\Z$. \end{exercise} \begin{theorem} \label{squaremodq} Let $q$ be a prime factor of $a^2+b^2$. If $q\equiv 3\pmod{4}$, then $q|a$ and $q|b$. \end{theorem} \pagebreak We state the next theorem before giving a sequence of lemmas that leads to its proof. \begin{theorem} \label{squaremodp} If $p$ is a prime such that $p\equiv 1\pmod{4}$, there exist integers $a, b$ such that \[p=a^2+b^2.\] \end{theorem}\vskip10pt \noindent For Lemmas~\ref{firstlemma} through \ref{lastlemma}, assume the following: \begin{itemize} \item[] Let $p$ be prime such that $p\equiv 1\; \pmod{4}$. \vspace{-10pt} \item[] Let $k$ be the greatest integer less than $\sqrt{p}$, and let $S=\{0, 1, \ldots, k\}$. \vspace{-10pt} \item[] Let $x$ be an integer such that $x^2\equiv -1\; \pmod{p}$ (as per Thm.\ 30). \end{itemize} \begin{lemma}\label{firstlemma} $|S\times S|>p$. \end{lemma} \begin{lemma} There exist two distinct pairs $(u_1, v_1), (u_2, v_2)\in S\times S$ such that $$u_1+xv_1\equiv u_2+xv_2\; \pmod{p}.$$ \end{lemma} With $u_1, u_2, v_1, v_2$ from the preceding lemma, let $a=u_1-u_2$ and $b=v_1-v_2$. \begin{lemma} $a^2+b^2\equiv 0\; \pmod{p}$ . \end{lemma} \begin{lemma}\label{lastlemma} $0