MATH135 Lecture Notes - Chinese Remainder Theorem, Prime Number

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Wentang Kuo

Document Summary

If p is a prime number that p (cid:45) a, then ap 1 1 (mod p) If p (cid:45) 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). Due to the fact that gcd(p, (p 1)!) = 1, by cd, we get ap 1 1 (mod p) (cid:4) Again, this is a hard proof, and most nal exams didn"t contain this type of question. Remark: for any integer a and any prime p, ap a (mod p) Case i: p | a for that a 0 (mod p)