Class Notes (1,100,000)

CA (620,000)

UW (20,000)

MATH (2,000)

MATH135 (300)

Roxane Itier Itier (10)

Lecture 1

School

University of WaterlooDepartment

MathematicsCourse Code

MATH135Professor

Roxane Itier ItierLecture

1This

**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 ﬁxed. By treating integers which are congruent

modulo mas if they were identical, we condense the inﬁnite set Zinto a new, algebraic system Zm

that is ﬁnite. This ﬁniteness 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 Deﬁnition of congruence classes

Deﬁnition 1. (a) For any aPZ, the congruence class of amodulo mis deﬁned 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, . . .ut4k|kPZu r0s4,

t. . . , 7,3,1,5,9, . . .ut4k1|kPZur1s4,

t. . . , 6,2,2,6,10, . . .ut4k2|kPZur2s4,

t. . . , 5,1,3,7,11, . . .ut4k3|kPZur3s4.

We see that Zis partitioned into four mutually disjoint congruence classes.

1

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

Observations:

(a) For any aPZ,

rasm akm

kPZ( xPZ

xand ahave the same remainder when divided by m(.

This follows immediately from the deﬁnition 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

signiﬁcance.

•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 r3s4,r2s4 r6s4,r3s4 r1s4.

•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 ﬁnite 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 ﬁniteness property.

•Finally, it follows from the preceding remarks that Zis the union of mdisjoint sets:

Z r0smY r1smY Y rm1sm.

2

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 rxsrxsmfor simplicity. We want to impose modular addition and

multiplication on Zmaccording to the two rules below. For arbitrary x, y PZ,

rxsrys rxys,

rxsrys 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.

Then

c1c2 r36s7 r9s7 r2s7,(1)

c1c2 r36s7 r18s7 r4s7.(2)

Question: If we now change the representatives of c1and c2, such as

c1 r314s7 r11s7, c2 r67s7 r1s7,

and compute c1c2and c1c2again, can we expect that the results remain the same as before?

Let’s take a look:

r11s7 r1s7 rp11q p1qs7 r12s7 r2s7,(1’)

r11s7 r1s7 rp11q p1qs7 r11s7 r4s7.(2’)

Thus, (1) and (1’) agree, and so are (2) and (2’). Is this to be expected in general?

3

###### You're Reading a Preview

Unlock to view full version