Class Notes
(811,170)

Canada
(494,539)

University of Waterloo
(18,179)

Mathematics
(1,874)

MATH 135
(334)

Wentang Kuo
(7)

Lecture

# MATH 135 Algebra Notes V (Oct 14 - Oct 25): Congruence

Unlock Document

University of Waterloo

Mathematics

MATH 135

Wentang Kuo

Fall

Description

MATH 135: Algebra for Honours Mathematics
Notes V
Michael Brock Li
Computational Mathematics IA
October MXIII
Concordia Cum Veritate
I: Congruence
Let m be a ▯xed m > 0 integer. If a;b 2 Z, we say that a is congruent to b
modulo m. Symbolically,
a ▯ b (mod m)
If mj(a ▯ b), we write
a 6▯ b (mod m)
Example I
m = 10
We see that picking two numbers of a and b, 2 ▯ 8 (mod 10), since 10 j (▯2▯8) =
▯10.
Proposition: (Congruence Is An Equivalence Relation (CER))
Let a;b;c 2 Z. Then,
1: a ▯ a (mod m) Re
exivity
2: a ▯ b (mod m) ) b ▯ a (mod m) Symmetry
3: a ▯ b (mod m) ) b ▯ c (mod m) ) a ▯ c (mod m) Transitivity
In general, a relation satis▯es these three conditions is called a equivalence
relation.
Proof.
1. 8a 2 Z;
(a ▯ a) = 0 = 0(m)
Thus, m j (a ▯ a) and a ▯ a (mod m)
2. Let m j (a ▯ b);m j (b ▯ c). By DIC, m j 1(a ▯ b) + 1(b ▯ c) = (a ▯ c)
) a ▯ c (mod m). ▯
1 i: Congruence class(relation)
An equivalence relation on a set can give this set a partition such that every
element in one part is equivalent to each other. Each part is called an equivalence
class. Consider m = 5. Now partition this into 5 pieces consist of integers (5
equivalence classes).
[05 = f0;▯5;▯10;▯15:::g = f5n j n 2 Zg
[1]5= f1;6;11;▯4;▯9:::g = f5n + 1 j n 2 Zg
[2]5= f2;7;12;▯3;▯8:::g = f5n + 2 j n 2 Zg
[3]5= f3;8;13;▯2;▯7:::g = f5n + 3 j n 2 Zg
[4]5= f4;9;▯1:::g = f5n + 4 j n 2 Zg
We see from here that [a] is the equivalence classes which contains a.
m
The de▯nition for equivalence relation is 8a 2 Z;[a] m = fn(m) + a j n 2 Zg
Proposition: (Congruent I▯ Same Remainder (CISR))
9 k 2 Z;a = km + b () a and b have the same remainders divided by m.
Proposition: (Properties of Congruence (PC))
Let a;a ;b;b 2 Z;m 2 Z;m > 0. If a ▯ a (mod m), b ▯ b (mod m), then
0 0
1: a ▯ b ▯ a ▯ b (mod m)
0 0
2: ab ▯ a b (mod m)
Proof. Since a ▯ a (mod m), there exists an integer j such that a = mj +
0 0 0
a . Since b ▯ b (mod m), there exists an integer h such that b = mh + b .
Multiplying them together gives us ab = (mjh + jb + a h)m + a b . Since 0 0
0 0 0 0
(mjh + jb + a h) is an integer, ab ▯ a b (mod m) as required. ▯
Proposition: (Congruences and Division (CD))
If ac ▯ bc (mod m) and gcd(c;m) = 1, then a ▯ b (mod m).
Proof. We know that m j c(a▯b). By Coprimeness and Divisibility, m j (a▯b).
Thus a ▯ b (mod m). ▯
Example II:
Find the last digit of 263 212.
2 Solution
Select any number for m, m = 10 for now. Since we know 263 ▯ 3 (mod 10).
Thus,
3 ▯ 9 (mod 10)
3 2
3 ▯ 3 (3) ▯ 9(3) ▯ 27 ▯ 7 (mod 10)
4 3
3 ▯ 3 (3) ▯ 7(3) ▯ 21 ▯ 1 (mod 10)
2 4 53 53
3 12 ▯ (3 ) ▯ 1 ▯ 1

More
Less
Related notes for MATH 135