Definiton. Let a, b, and m be integers. a is
congruent to b mod m if
; that is, if
Notation: means that a is congruent to b
mod m. m is called the modulus of the
congruence; I will almost always work with positive moduli.
Note that if and only if
. Thus, modular arithmetic gives you another way of
dealing with divisibility relations.
For example:
because
.
because
.
Proposition. Congruence mod m is an equivalence relation:
(a) ( Reflexivity) for all a.
(b) ( Symmetry) If , then
.
(c) ( Transitivity) If and
, then
.
Proof. Since , it follows that
.
Suppose . Then
, so
. Hence,
.
Suppose and
. Then there are integers j and k such that
Add the two equations:
This implies that .
Example. (a) List the elements of the equivalence classes relative to congruence mod 3.
(b) Using 0, 1, and 2 to represent these equivalence classes, construct addition and multiplication tables mod 3.
(a) The equivalence classes are the 3 congruence classes:
Each integer belongs to exactly one of these classes. Two integers in a given class are congruent mod 3.
(If you know some group theory, you probably recognize this as
constructing from
.)
(b)
For example, , because
as integers, and the congruence class of 3 is
represented by 0. Likewise,
as integers,
and the congruence class of 4 is represented by 1.
I could have chosen different representatives for the classes --- say
3, -4, and 4. A choice of representatives, one from each class, is
called a complete system of residues mod 3.
But working mod 3 it's natural to use the numbers 0, 1, and 2 as
representatives --- and in general, if I'm working mod n, the obvious
choice of representatives is the set . This set is called the standard residue system mod n, and it is the set
of representatives I'll usually use. Thus, the standard residue
system mod 6 is
.
Theorem. Suppose and
. Then:
(a) and
.
(b) .
Proof. I'll prove the first congruence as an
example. Suppose and
. Then
and
for some
, so
This implies that .
Example. Solve the congruence
There are no "fractions" mod 11. I want to divide by 3, and
to do this I need to multiply by the multiplicative inverse of 3. So
I need a number k such that .
A systematic way of finding such a number is to use the Extended Euclidean algorithm. In this case, I just
use trial and error. Obviously,
and
won't work, so I'll start at
:
Thus, I need to multiply the equation by 4:
Definition. x and y are
multiplicative inverses mod n if .
Notation: or
. Do not use fractions.
Example. (a) Find .
(b) Prove that 6 does not have a multiplicative inverse mod 8.
(a) , so
.
(b) Suppose . Then
This contradiction shows that 6 does not have a multiplicative
inverse mod 8.
Example. Reduce to a number in
.
Example. Reduce to a number in
.
, so
Example. Show that if p is prime, then
By the Binomial Theorem,
A typical coefficient is divisible by p for
. So going mod p, the only terms that remain are
and
.
For example
The result is not true if the modulus is not prime. For example,
Copyright 2020 by Bruce Ikenaga