Definition.
(Page 54)
Let $n$ be a positive integer. Integers $a$ and $b$
are said to be
congruent modulo $n$
if $a-b$ is divisible by $n.$
This is written $a\equiv b\pmod{n}.$
Note.
(Page 54)
When working with congruences, it helps to be able to move
easily among the following equivalent statements.
\begin{array}{l}
a\equiv b \pmod n \\
n\mid (a-b) \\
a-b=un \quad \text{ for some } u \in \Z \\
a=b+un \quad \text{ for some } u \in \Z
\end{array}
Problem 10.21
Prove the equivalence of the four mod $n$ equivalences.
Also prove that $a\equiv b \pmod n$
iff $a$ and $b$ leave the same remainder on
division by $n.$
Guevara Note.
Thus, for some $r\in\Z,$ $0\le r \lt n,$
add the following statements to the list
of mod $n$ equivalences:
\begin{array}{l}
a=nq+r \quad \text{ for some } q\in\Z \\
b=nq+r \quad \text{ for some } q\in\Z \\
\end{array}
Theorem 10.1.
Congruence modulo $n$ is an equivalence relation
on the set of integers, for each positive integer $n.$
Definition.
(Page 55)
The equivalence classes for this equivalence relation
are called
congruence classes mod $n,$
or simply
congruence classes
if $n$ is clear from the context.
(These classes are sometimes called
residue classes,
but we will not use this term.)
Example 10.1.
-
There are two congruence classes mod $2$: the even integers, and the odd integers.
-
There are four congruence classes mod $4$:
\begin{array}{l}
\{\ldots,-8,-4,0,4,8,\ldots\} \\
\{\ldots,-7,-3,1,5,9,\ldots\} \\
\{\ldots,-6,-2,2,6,10,\ldots\} \\
\{\ldots,-5,-1,3,7,11,\ldots\}
\end{array}
In the language of section 9, $\{0,1,2,3\}$ is a complete
set of equivalence class representatives.
Least Integer Principle.
(Page 55)
Every nonempty set of positive integers contains a least element.
Division Algorithm.
(Page 56)
If $a$ and $b$ are integers with $b\gt0$
then there exist unique integers
$q$ and $r$ such that
\[
a=bq+r,\ 0\le r\lt b.
\]
Theorem 10.2.
Let $n$ be a positive integer. Then
each integer is congruent modulo $n$
to precisely one of the integers
$0,1,2,\ldots,n-1.$
Alex Notes