Class Notes (811,170)
Mathematics (1,874)
MATH 135 (334)
Lecture

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

5 Pages
150 Views

School
University of Waterloo
Department
Mathematics
Course
MATH 135
Professor
Wentang Kuo
Semester
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

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.