MATH 1190 Lecture Notes - Diophantine Equation, Euclidean Algorithm, Multiplication Table
6 Feb 2013
School
Department
Course
Professor
Document Summary
7-23-2006: a is congruent to b mod n means that n | a b. Notation: a = b (mod n): congruence mod n is an equivalence relation. Hence, congruences have many of the same properties as ordinary equations: congruences provide a convenient shorthand for divisibility relations. Let a, b, and m be integers. a is congruent to b mod m if m | a b; that is, if a b = km for some integer k. Write a = b (mod m) to mean that a is congruent to b mod m. m is called the modulus of the congruence; i will almost always work with positive moduli. Notice that a = 0 (mod m) is equivalent to m | a. Thus, divisibility is a special case of congruence. In many cases, this means that you can reduce proving results about congruences to results about divisibility that were proved earlier.
