Class Notes (1,100,000)
CA (620,000)
UW (20,000)
MATH (2,000)
MATH135 (300)
Lecture 1

MATH135 Lecture 1: Congruence classes and Z_m

Course Code
Roxane Itier Itier

This preview shows pages 1-3. to view the full 9 pages of the document.
MATH 135 Winter 2015
Congruence Classes;
Arithmetic in Zm
Throughout this note, the modulus mPNis fixed. By treating integers which are congruent
modulo mas if they were identical, we condense the infinite set Zinto a new, algebraic system Zm
that is finite. This finiteness is key to the proof of Fermat’s Little Theorem. Our goal is to survey
the four basic modular operations - addition, subtraction, multiplication and division - on Zm.
1 Definition of congruence classes
Definition 1. (a) For any aPZ, the congruence class of amodulo mis defined as the set
rasm: nPZ|napmod mq(.
If mis understood from the context, we simply write rasinstead of rasm.
(b) The set of all congruence classes modulo mis denoted by Zm. In symbols,
Zm: rasm|aPZ(.
(c) Let cPZmbe any congruence class. Any element aPcis called a representative of the
class c.
General picture of the congruence classes:
In this example, take m4. We list (part of) the integers according to their remainders when
divided by 4:
t. . . , 8,4,0,4,8, . . .ut4k|kPZu  r0s4,
t. . . , 7,3,1,5,9, . . .ut4k1|kPZur1s4,
t. . . , 6,2,2,6,10, . . .ut4k2|kPZur2s4,
t. . . , 5,1,3,7,11, . . .ut4k3|kPZur3s4.
We see that Zis partitioned into four mutually disjoint congruence classes.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

(a) For any aPZ,
rasm akm
kPZ( xPZ
xand ahave the same remainder when divided by m(.
This follows immediately from the definition of congruence and CISR.
(b) For any a, b PZ, the following hold:
(i) aP rasm.
(ii) abpmod mq ðñ rasm rbsm.
(iii) abpmod mq ðñ rasmX rbsm.
These are consequences of the fact that congruence is an equivalence relation. The proofs
are left to the reader (see Question 6 of Assignment 6). We proceed to explain their
Statement (i) means that every aPZis contained in some congruence class. Also, every
congruence class is non-empty.
Statements (ii) and (iii) together guarantee that any two congruence classes are
either disjoint or equal (i.e., they cannot partially overlap). In addition, if cPZm
is a congruence class, then c rnsmfor any nPc. This allows us to “rename” the
congruence class using any representative at will. For instance,
r0s4 r8s4,r1s4 r3s4,r2s4 r6s4,r3s4 r1s4.
If aPZhas remainder rP t0,1, . . . , m1uwhen divided by m, then arpmod mqand
hence rasm rrsm. Also, for any two distinct r, s P t0,1, . . . , m 1u,rspmod mq
and hence rrsm rssm. Therefore,
Zm r0sm,r1sm,...,rm1sm(.
We conclude that there are precisely mdistinct congruence classes modulo m. As we
shall see, the fact that Zmis finite distinguishes modular arithmetic from ordinary
arithmetic on Z. Many algebraic results about Zm(such as Fermat’s Little Theorem
and the behaviour of invertible elements) are connected to this finiteness property.
Finally, it follows from the preceding remarks that Zis the union of mdisjoint sets:
Z r0smY r1smY   Y rm1sm.

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Exercise 1. True or False? Please explain:
(a) 2 PZ3.
(b) Z8Z.
(c) r2s5 r2s7.
(d) r2s5X r3s7.
2 Modular arithmetic on Zm
For any xPZ, we write rxsrxsmfor simplicity. We want to impose modular addition and
multiplication on Zmaccording to the two rules below. For arbitrary x, y PZ,
rxsrys  rxys,
rxsrys  rxys.
The idea is to add or multiply the representatives of the two classes in the usual way, and then pass
to the congruence class which contains the result. Sounds simple, right? Well, here’s a catch:
Example 1. Let m7. Choose two of your favourite congruence classes c1, c2PZ7, say,
c1 r3s7, c2 r6s7.
c1c2 r36s7 r9s7 r2s7,(1)
c1c2 r36s7 r18s7 r4s7.(2)
Question: If we now change the representatives of c1and c2, such as
c1 r314s7 r11s7, c2 r67s7 r1s7,
and compute c1c2and c1c2again, can we expect that the results remain the same as before?
Let’s take a look:
r11s7 r1s7 rp11q  p1qs7 r12s7 r2s7,(1’)
r11s7 r1s7 rp11q  p1qs7 r11s7 r4s7.(2’)
Thus, (1) and (1’) agree, and so are (2) and (2’). Is this to be expected in general?
You're Reading a Preview

Unlock to view full version