Class Notes (808,123)
Mathematics (1,874)
MATH 135 (334)
Lecture

# MATH 135 Algebra Notes VI (Oct 28 - Nov 11): Fermate Little Theorem, Linear Congruences, Chinese Remainder Theorem

8 Pages
86 Views

School
University of Waterloo
Department
Mathematics
Course
MATH 135
Professor
Wentang Kuo
Semester
Fall

Description
MATH 135: Algebra for Honours Mathematics Notes VI Michael Brock Li Computational Mathematics IA October : Mid-November MXIII Concordia Cum Veritate I: Fermat Little Theorem If p is a prime number that p - a, then ap▯1 ▯ 1 (mod p) A simple theorem...a hard proof. Analyze this: Proof. If p - a, we show that a;2a;3a;:::(p ▯ 1)a are distinct modulo p. Suppose, ra ▯ sa (mod p);1 ▯ r < s ▯ (p ▯ 1) Since, gcd(a;p) = 1, by CD, r ▯ s (mod p) But it is not possible for 1 ▯ r < s ▯ (p ▯ 1). Since a;2a;3a;:::(p ▯ 1)a are distinct modulo p, they must be ▯ to 1;2;3;:::;(p ▯ 1). Multiply these integers together, we get a ▯ (2a) ▯ (3a) ▯ ::: ▯ (p ▯ 1)a ▯ 1 ▯ 2 ▯ 3 ▯ ::: ▯ (p ▯ 1) (mod p) p▯1 (p ▯ 1)!a ▯ (p ▯ 1)! (mod p) Due to the fact that gcd(p;(p ▯ 1)!) = 1, by CD, we get p▯1 a ▯ 1 (mod p) ▯ 1 Again, this is a hard proof, and most ▯nal exams didn’t contain this type of question. As a follow up for this theorem, Remark: For any integer a and any prime p, p a ▯ a (mod p) Proof. Case I: p j a for that a ▯ 0 (mod p) p ) a ▯ 0 (mod p) ) a ▯ a (mod p) Case II: if p - a by FlT, ap▯1 ▯ 1 (mod p) but a ▯ a (mod p), thus p▯1 ) a a ▯ 1a (mod p) ) a ▯ a (mod p) ▯ Remark: (Existence of Inverses in Z (INV Z )) p p Let p be a prime number. If [a] is any non-zero element inpZ , then there exist an element [b] 2 p such that [a][b] = [1] Example I: Allow p = 29 and a = 18. Then thus by FlT, 1828▯ 1 (mod 29) Example II: Find p such that II: Linear Congruences It has the form ax ▯ c (mod m) A solution to such linear congruence is an intege0 x such that ax 0 c (mod m) 2 Remark: If ax ▯ c (mod m) has a solution () 9 x 2 Z;ax ▯ c (mod m) 0 0 () 9 x0;0 2 Z;ax0+ my =0c () gcd(a;m) j c Thus we approach to a new theorem of linear congruences: i: Linear Congruence Theorem Let gcd(a;m) = d 6= 0. The linear congruence equation ax ▯ c (mod m) or [a][x] = [c] 2mZ has a solution () gcd(a;m) j c Moreover, the single solution is when x ▯ x . However, if there is more than 0 one solution, it’s representation can be expressed as follows m m x x ▯ x0;x0+ ;x0+ 2 ;:::0x + (d ▯ 1)(mod m) d d d or m m x f[0 ];[0 + ];[0 + 2 ];:::;0x + (d ▯ 1) ]g m Z d d d Example I: Solve 3x ▯ 5 (mod 6). Solution: gcd(3;6) = 3 - 5 Thus, there is no solution. 3 Example II: Solve 4x ▯ 6 (mod 6) Solution: gcd(4;10) = 2 j 6 Thus, there is a solution, and by inspection, x = 4 is a solution. Since, 10 is a small modulus, let’s test all ten possibilities in modulo 10. x (mod 10) 0 1 2 3 4 5 6 7 8 9 4x (mod 10) 0 4 8 2 6 0 4 8 2 6 We get x ▯ 4 or 9 (mod 10) III: Chinese Remainder Theorem This theorem was posed due to the fact that we need to ▯nd a solution in simultaneous linear congruences. Imagine you are in a classroom with students, and all of the sudden after a few days, students are dropping out. Assume you do not have a calculator, calculate how many students are left in the classroom (without counting every each one of them). But if you do count them all, 30 students wouldn’t be so bad. But imagine you have 5000 students in one classroom. Thus, this theorem will come in handy. i: Chinese Remainder Theorem (CRT) Let a1;a2;m 1m 22Z with m ;m 1 1.2If gcd(m ;m ) 1 1,2then ( x ▯ a 1mod m ) 1 (1) x ▯ a 2mod m ) 2 has a unique solution x ▯ x (mod m m ) 0 1 2 Proof. x ▯ a1(mod m ) 1 () x = a1+ m y1y 2 Z Set x = a + m y;y 2 Z 1 1 into x ▯ a1(mod m )1 and we get, a1+ m y1▯ a (2od m ) 2 () a 1 m y1= a ▯2m z;z22 Z 4 () m 1 + m z2= a ▯2a ;y1z 2 Z Since gcd(m 1m )2= 1 j (a 2 a )1 then by Linear Dolphantine Equation Part 1, m 1 + m z2= a ▯2a ;y1z 2 Z has a solution. Thus the complete solution is m 2 y = y 0 n
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.