Skip to main content
Contents Dark Mode Prev Up Next \( \renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\T}{{\mathbb T}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\PP}{{\mathbb P}}
\newcommand{\HH}{{\mathbb H}}
\newcommand{\compose}{\circ}
\newcommand{\bolda}{{\mathbf a}}
\newcommand{\boldb}{{\mathbf b}}
\newcommand{\boldc}{{\mathbf c}}
\newcommand{\boldd}{{\mathbf d}}
\newcommand{\bolde}{{\mathbf e}}
\newcommand{\boldi}{{\mathbf i}}
\newcommand{\boldj}{{\mathbf j}}
\newcommand{\boldk}{{\mathbf k}}
\newcommand{\boldn}{{\mathbf n}}
\newcommand{\boldp}{{\mathbf p}}
\newcommand{\boldq}{{\mathbf q}}
\newcommand{\boldr}{{\mathbf r}}
\newcommand{\bolds}{{\mathbf s}}
\newcommand{\boldt}{{\mathbf t}}
\newcommand{\boldu}{{\mathbf u}}
\newcommand{\boldv}{{\mathbf v}}
\newcommand{\boldw}{{\mathbf w}}
\newcommand{\boldx}{{\mathbf x}}
\newcommand{\boldy}{{\mathbf y}}
\newcommand{\boldz}{{\mathbf z}}
\newcommand{\boldzero}{{\mathbf 0}}
\newcommand{\boldmod}{\boldsymbol{ \bmod }}
\newcommand{\boldT}{{\mathbf T}}
\newcommand{\boldN}{{\mathbf N}}
\newcommand{\boldB}{{\mathbf B}}
\newcommand{\boldF}{{\mathbf F}}
\newcommand{\boldS}{{\mathbf S}}
\newcommand{\boldE}{{\mathbf E}}
\newcommand{\boldG}{{\mathbf G}}
\newcommand{\boldK}{{\mathbf K}}
\newcommand{\boldL}{{\mathbf L}}
\DeclareMathOperator{\ch}{char}
\DeclareMathOperator{\lns}{lns}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\Span}{span}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\NS}{null}
\DeclareMathOperator{\RS}{row}
\DeclareMathOperator{\CS}{col}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\range}{range}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\nullity}{nullity}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\Arg}{Arg}
\DeclareMathOperator{\Log}{Log}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Int}{Int}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Arcsin}{Arcsin}
\DeclareMathOperator{\Arccos}{Arccos}
\DeclareMathOperator{\Arctan}{Arctan}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\Fix}{Fix}
\DeclareMathOperator{\Aff}{Aff}
\DeclareMathOperator{\Frac}{Frac}
\DeclareMathOperator{\Ann}{Ann}
\DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\mdeg}{mdeg}
\DeclareMathOperator{\Lt}{Lt}
\DeclareMathOperator{\Lc}{Lc}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator{\Frob}{Frob}
\DeclareMathOperator{\adj}{adj}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\curl}{curl}
\DeclareMathOperator{\grad}{grad}
\DeclareMathOperator{\diver}{div}
\DeclareMathOperator{\flux}{flux}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Isom}{Isom}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\ML}{M}
\DeclareMathOperator{\Syl}{Syl}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\ab}{ab}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\len}{len}
\DeclareMathOperator{\proj}{proj}
\newcommand{\surjects}{\twoheadrightarrow}
\newcommand{\injects}{\hookrightarrow}
\newcommand{\bijects}{\leftrightarrow}
\newcommand{\isomto}{\overset{\sim}{\rightarrow}}
\newcommand{\floor}[1]{\lfloor#1\rfloor}
\newcommand{\ceiling}[1]{\left\lceil#1\right\rceil}
\newcommand{\mclass}[2][m]{[#2]_{#1}}
\newcommand{\val}[2][]{\left\lvert #2\right\rvert_{#1}}
\newcommand{\abs}[2][]{\left\lvert #2\right\rvert_{#1}}
\newcommand{\valuation}[2][]{\left\lvert #2\right\rvert_{#1}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\anpoly}{a_nx^n+a_{n-1}x^{n-1}\cdots +a_1x+a_0}
\newcommand{\anmonic}{x^n+a_{n-1}x^{n-1}\cdots +a_1x+a_0}
\newcommand{\bmpoly}{b_mx^m+b_{m-1}x^{m-1}\cdots +b_1x+b_0}
\newcommand{\pder}[2]{\frac{\partial#1}{\partial#2}}
\newcommand{\normalin}{\trianglelefteq}
\newcommand{\angvec}[1]{\langle #1\rangle}
\newcommand{\varpoly}[2]{#1_{#2}x^{#2}+#1_{#2-1}x^{#2-1}\cdots +#1_1x+#1_0}
\newcommand{\varpower}[1][a]{#1_0+#1_1x+#1_1x^2+\cdots}
\newcommand{\limasto}[2][x]{\lim_{#1\rightarrow #2}}
\newcommand{\abcdmatrix}[4]{\begin{bmatrix}#1\amp #2\\ #3\amp #4 \end{bmatrix}
}
\newenvironment{amatrix}[1][ccc|c]{\left[\begin{array}{#1}}{\end{array}\right]}
\newenvironment{linsys}[2][m]{
\begin{array}[#1]{@{}*{#2}{rc}r@{}}
}{
\end{array}}
\newcommand{\eqsys}{\begin{array}{rcrcrcr}
a_{11}x_{1}\amp +\amp a_{12}x_{2}\amp +\cdots+\amp a_{1n}x_{n}\amp =\amp b_1\\
a_{21}x_{1}\amp +\amp a_{22}x_{2}\amp +\cdots+\amp a_{2n}x_{n}\amp =\amp b_2\\
\amp \vdots\amp \amp \vdots \amp \amp \vdots \amp \\
a_{m1}x_{1}\amp +\amp a_{m2}x_{2}\amp +\cdots +\amp a_{mn}x_{n}\amp =\amp b_m
\end{array}
}
\newcommand{\numeqsys}{\begin{array}{rrcrcrcr}
e_1:\amp a_{11}x_{1}\amp +\amp a_{12}x_{2}\amp +\cdots+\amp a_{1n}x_{n}\amp =\amp b_1\\
e_2: \amp a_{21}x_{1}\amp +\amp a_{22}x_{2}\amp +\cdots+\amp a_{2n}x_{n}\amp =\amp b_2\\
\amp \vdots\amp \amp \vdots \amp \amp \vdots \amp \\
e_m: \amp a_{m1}x_{1}\amp +\amp a_{m2}x_{2}\amp +\cdots +\amp a_{mn}x_{n}\amp =\amp b_m
\end{array}
}
\newcommand{\homsys}{\begin{array}{rcrcrcr}
a_{11}x_{1}\amp +\amp a_{12}x_{2}\amp +\cdots+\amp a_{1n}x_{n}\amp =\amp 0\\
a_{21}x_{1}\amp +\amp a_{22}x_{2}\amp +\cdots+\amp a_{2n}x_{n}\amp =\amp 0\\
\amp \vdots\amp \amp \vdots \amp \amp \vdots \amp \\
a_{m1}x_{1}\amp +\amp a_{m2}x_{2}\amp +\cdots +\amp a_{mn}x_{n}\amp =\amp 0
\end{array}
}
\newcommand{\vareqsys}[4]{
\begin{array}{ccccccc}
#3_{11}x_{1}\amp +\amp #3_{12}x_{2}\amp +\cdots+\amp #3_{1#2}x_{#2}\amp =\amp #4_1\\
#3_{21}x_{1}\amp +\amp #3_{22}x_{2}\amp +\cdots+\amp #3_{2#2}x_{#2}\amp =\amp #4_2\\
\vdots \amp \amp \vdots \amp \amp \vdots \amp =\amp \\
#3_{#1 1}x_{1}\amp +\amp #3_{#1 2}x_{2}\amp +\cdots +\amp #3_{#1 #2}x_{#2}\amp =\amp #4_{#1}
\end{array}
}
\newcommand{\genmatrix}[1][a]{
\begin{bmatrix}
#1_{11} \amp #1_{12} \amp \cdots \amp #1_{1n} \\
#1_{21} \amp #1_{22} \amp \cdots \amp #1_{2n} \\
\vdots \amp \vdots \amp \ddots \amp \vdots \\
#1_{m1} \amp #1_{m2} \amp \cdots \amp #1_{mn}
\end{bmatrix}
}
\newcommand{\varmatrix}[3]{
\begin{bmatrix}
#3_{11} \amp #3_{12} \amp \cdots \amp #3_{1#2} \\
#3_{21} \amp #3_{22} \amp \cdots \amp #3_{2#2} \\
\vdots \amp \vdots \amp \ddots \amp \vdots \\
#3_{#1 1} \amp #3_{#1 2} \amp \cdots \amp #3_{#1 #2}
\end{bmatrix}
}
\newcommand{\augmatrix}{
\begin{amatrix}[cccc|c]
a_{11} \amp a_{12} \amp \cdots \amp a_{1n} \amp b_{1}\\
a_{21} \amp a_{22} \amp \cdots \amp a_{2n} \amp b_{2}\\
\vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots\\
a_{m1} \amp a_{m2} \amp \cdots \amp a_{mn}\amp b_{m}
\end{amatrix}
}
\newcommand{\varaugmatrix}[4]{
\begin{amatrix}[cccc|c]
#3_{11} \amp #3_{12} \amp \cdots \amp #3_{1#2} \amp #4_{1}\\
#3_{21} \amp #3_{22} \amp \cdots \amp #3_{2#2} \amp #4_{2}\\
\vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots\\
#3_{#1 1} \amp #3_{#1 2} \amp \cdots \amp #3_{#1 #2}\amp #4_{#1}
\end{amatrix}
}
\newcommand{\spaceforemptycolumn}{\makebox[\wd\boxofmathplus]{\ }}
\newcommand{\generalmatrix}[3]{
\left(
\begin{array}{cccc}
#1_{1,1} \amp #1_{1,2} \amp \ldots \amp #1_{1,#2} \\
#1_{2,1} \amp #1_{2,2} \amp \ldots \amp #1_{2,#2} \\
\amp \vdots \\
#1_{#3,1} \amp #1_{#3,2} \amp \ldots \amp #1_{#3,#2}
\end{array}
\right) }
\newcommand{\colvec}[2][c]{\begin{amatrix}[#1] #2 \end{amatrix}}
\newcommand{\rowvec}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 1.2 Modular arithmetic
Subsection 1.2.1 Congruence
Definition 1.2.1 . Divisibilty.
Given integers
\(a,b\in \Z\) we say that
\(a\) divides \(b\) (or that
\(b\) is a
multiple of
\(a\) ) if there is an integer
\(q\in \Z\) satisfying
\(b=qa\text{.}\) In this case,
\(q\) is called the
quotient of
\(b\) by
\(a\text{.}\)
Definition 1.2.2 . Congruence modulo \(n\) .
Let \(n\) be a positive integer. Integers \(a\) and \(b\) are congruent modulo \(n\) , denoted \(a\equiv b\pmod n\text{,}\) if one of the two following equivalent conditions holds:
\begin{align}
n \amp \mid a-b\tag{1.2.1}\\
b \amp =a+qn \text{ for some } q\in \Z\text{.}\tag{1.2.2}
\end{align}
The congruence class (or residue class ) of \(a\) modulo \(n\text{,}\) denoted \(\overline{a}\) (or \([a]_n\) ) is the set of all integers congruent to \(a\) modulo \(n\text{:}\) i.e.,
\begin{align*}
\overline{a}=[a]_n \amp = \{b\in \Z\mid a\equiv b \pmod n\}\\
\amp = \{a+qn\mid q\in \Z\}\text{.}
\end{align*}
Elements of a congruence class \([a]_n\) are called representatives (or residues ) of that class.
The set of all congruence classes modulo \(n\) is denoted \(\Z/n\Z\text{:}\) i.e.,
\begin{equation*}
\Z/n\Z=\{[a]_n\mid a\in \Z\}\text{.}
\end{equation*}
The integer \(n\) in all the settings above is called a modulus .
Example 1.2.3 . Congruence modulo \(3\) .
Consider the modulus \(n=3\text{.}\)
Compute
\([5]_3\) and
\([-1]_3\text{.}\)
Find a finite list of integers
\(a_1,a_2,\dots, a_r\) such that
\begin{equation*}
\Z/3\Z=\{[a_1]_3, [a_2]_3,\dots, [a_r]_3\}\text{.}
\end{equation*}
Compute
\(\abs{\Z/3\Z}\text{.}\)
Solution .
We have
\begin{equation*}
[5]_3=[-1]_3=[2]_3=\{\dots, -3,-1,2,5,\dots \}\text{.}
\end{equation*}
It is not difficult to show that for any \(a\in \Z\) we have \([a]_3=[k]_3\) for some \(k\in \{0,1,2\}\text{.}\) (See theory below more generally.) Thus
\begin{equation*}
\Z/3\Z=\{[0]_3,[1]_3,[2]_3\}\text{.}
\end{equation*}
The sets
\begin{align*}
[0]_3 \amp = \{\dots, -3,0,3,6,\dots\}\\
[1]_3 \amp = \{\dots,-2,1,4,7,\dots\}\\
[2]_3 \amp =\{\dots, -1,2,5,8,\dots\}
\end{align*}
are clearly all distinct from one another. Thus \(\abs{\Z/3\Z}=3\text{.}\)
Theorem 1.2.5 . Congruence.
Fix a modulus \(n\text{.}\)
The congruence modulo \(n\) relation is an equivalence relation: i.e.,
Reflexivity.
\(a\equiv a\pmod n\) for all
\(a\in \Z\text{.}\)
Reflexivity. If
\(a\equiv b\pmod n\text{,}\) then
\(b\equiv a\pmod n\text{.}\)
Transitivity. If
\(a\equiv b\pmod n\) and
\(b\equiv c\pmod n\text{,}\) then
\(a\equiv c\pmod n\text{.}\)
The following statements are equivalent.
\(a\equiv b\pmod n\text{.}\)
The congruence classes modulo \(n\) form a partition of \(\Z\text{:}\) i.e., we have
\begin{equation*}
\Z=\bigcup_{a\in \Z}[a]_n\text{,}
\end{equation*}
and if \([a]_n\ne [b]_n\text{,}\) then \([a]_n\cap [b]_n=\emptyset\text{.}\) Using logical notation:
\begin{equation}
[a]_n\ne [b]_n\implies [a]_n\cap [b]_n=\emptyset\text{.}\tag{1.2.3}
\end{equation}
Assume \(n\) is positive. For every \(a\in \Z\text{,}\) there is a unique \(k\in \{0,1,\dots, n-1\}\) such that
\begin{equation*}
[a]_n=[k]_n\text{.}
\end{equation*}
Equivalently,
\begin{equation}
\Z/n\Z=[0]_n\cup [1]_n\cup \dots \cup [n-1]_n\tag{1.2.4}
\end{equation}
and
\begin{equation*}
[j]_n=[k]_n \text{ if and only if} j=k
\end{equation*}
for all \(0\leq j,k\leq n-1\text{.}\) As a consequence,
\begin{equation}
\abs{\Z/n\Z}=n\text{.}\tag{1.2.5}
\end{equation}
Proof.
See text for (1). Statements (2)-(3) then follow from general properties about equivalence relations and their corresponding equivalence classes. Statement (4) follows from (2) and the following observation:
\begin{equation*}
0< \abs{a-b} < n \implies n\nmid a-b\text{.}
\end{equation*}
Definition 1.2.6 . Least residue modulo \(n\) .
Fix a positive modulus
\(n\text{.}\) Given an integer
\(a\) the
least residue of
\(a\) modulo
\(n\text{,}\) denoted
\(a\bmod n\) is the unique
\(r\in \{0,1,2,\dots, n-1\}\) satisfying
\(a\equiv r\pmod n\text{.}\)
Theorem 1.2.8 . Division algorithm.
Given any integer \(a, b\in \Z\) with \(b\) nonzero, there is a unique pair of integers \((q,r)\) satisfying the following properties:
\(0\leq r< \abs{b}\text{.}\)
We call the integers \(q\) and \(r\) satisfying these properties the quotient and remainder upon dividing \(a\) by \(b\text{.}\)
Proposition 1.2.9 . Least residue.
Let \(n\) be a positive integer, and let \(a,r\in \Z\text{.}\) The following statements are equivalent.
\([a]_n=[r]_n\) and
\(r\in \{0,1,2\dots, n-1\}\text{.}\)
\(r\) is the remainder upon division of
\(a\) by
\(n\text{.}\)
Subsection 1.2.2 Ring structure of \(\Z/n\Z\)
Proposition 1.2.10 . Modular arithmetic.
Fix a modulus \(n\text{.}\) Assume integers \(a,a',b,b'\) satisfy
\begin{align*}
a \amp \equiv a' \pmod n \amp b\amp \equiv b'\pmod n\text{.}
\end{align*}
We have
\begin{align}
a+b \amp \equiv a'+b'\pmod n \amp \tag{1.2.6}\\
a b\amp \equiv a' b' \pmod n \amp \text{.}\tag{1.2.7}
\end{align}
It follows from this that
\begin{align}
[a+b]_n \amp = [a'+b']_n \amp \tag{1.2.8}\\
[ab]_n\amp = [a'b']_n \text{.}\tag{1.2.9}
\end{align}
Corollary 1.2.11 . Ring structure of \(\Z/n\Z\) .
Fix a modulus \(n\text{.}\) We have well-defined binary operations \(+\) and \(\cdot\) defined on \(\Z/n\Z\) as follows:
\begin{align*}
\Z/n\Z\times \Z/n\Z \amp\xrightarrow{\phantom{X}+\phantom{X}} \Z/n\Z \amp
\Z/n\Z\times \Z/n\Z \amp\xrightarrow{\phantom{X}\bullet\phantom{X}} \Z/n\Z\\
([a]_n,[b]_n) \amp \longmapsto [a+b]_n
\amp
([a]_n,[b]_n) \amp \longmapsto [ab]_n\text{.}
\end{align*}
Example 1.2.12 . Modular arithmetic.
Fix the modulus \(n=8\text{.}\) Find a representative \(r\in \{0,1,\dots, 7\}\) for the congruence class
\begin{equation*}
\overline{43}(\overline{23}\, \overline{11}+\overline{17}) \text{.}
\end{equation*}
Example 1.2.13 . Least residue.
Let
\(n=50\) and let
\(a=99^{1233}(7^8+ 1)\text{.}\) Compute
\(a\bmod n\text{.}\)
Specimen 4 . Additive group \(\Z/n\Z\) .
Fix a positive integer
\(n\text{.}\) The pair
\((\Z/n\Z, +)\) is a group, where
\(+\) is the addition operation defined in
Corollary 1.2.11 .
The group identity of
\(\Z/n\Z\) is the congruence class
\(\overline{0}=[0]_n\text{.}\)
Given
\(\overline{a}\in \Z/n\Z\text{,}\) its group inverse is
\(\overline{-a}\text{,}\) denoted
\(-\overline{a}\text{.}\)
Definition 1.2.14 . Multiplicative units in \(\Z/n\Z\) .
Fix a modulus \(n\text{.}\) An element \(\overline{a}\in \Z/n\Z\) is a unit (or (multiplicatively) invertible ) if there is an element \(\overline{b}\in \Z/n\Z\) satisfying
\begin{equation*}
\overline{a}\overline{b}=\overline{b}\overline{a}=\overline{1}\text{.}
\end{equation*}
The element \(\overline{b}\) in this case is called the multiplicative inverse of \(\overline{a}\text{,}\) denoted \(\overline{a}^{-1}\text{.}\) The set of all units of \(\Z/n\Z\) is denoted \((\Z/n\Z)^*\text{:}\) i.e.,
\begin{equation}
(\Z/n\Z)^*=\{\overline{a}\in \Z/n\Z\mid \overline{a}\overline{b}=\overline{1} \text{ for some } \overline{b}\in \Z/n\Z\}\text{.}\tag{1.2.10}
\end{equation}
Specimen 5 . Units modulo \(n\) .
Fix a modulus
\(n\text{.}\) The pair
\(((\Z/n\Z)^*, \cdot)\) is a group, where
\(\cdot\) is the operation defined in
Corollary 1.2.11 .
The group identity of
\((\Z/n\Z)^*\) is
\(\overline{1}\text{.}\)
Given
\(\overline{a}\in (\Z/n\Z)^* \text{,}\) its group inverse is its multiplicative inverse
\(\overline{a}^{-1}\text{.}\)
Example 1.2.15 . Modulus \(n=5\) .
Compute group tables for both
\(\Z/5\Z\) and
\((\Z/5\Z)^*\text{.}\) Naturally, for the latter you should first determine the units of
\(\Z/5\Z\text{.}\)
Example 1.2.16 . Units modulo \(9\) .
Compute a group table for
\((\Z/9\Z)^*\text{.}\)
Definition 1.2.17 . Greatest common divisor.
Let \(a\) and \(b\) be integers, at least one of which is nonzero. The greatest common divisor of \(a\) and \(b\text{,}\) denoted \(\gcd(a,b)\text{,}\) is the greatest positive integer dividing both \(a\) and \(b\text{:}\) i.e.,
\begin{equation}
\gcd(a,b)=\max\{q\in \Z_{> 0}\mid q\mid a \text{ and } q\mid b\}\text{.}\tag{1.2.11}
\end{equation}
