Back in my post from March 25, 2014,<\/a> I explain that “mod” means remainder: for instance, 7 mod 3 = 1.<\/p>\n Two numbers that, divided by a number n, give the same remainder, are called congruent mod n<\/em>. For example, 24 mod 5 = 4, and also 29 mod 5 = 4. Therefore, 24 is congruent to 29 mod 5. This can be written<\/p>\n 24 ≡ 29 mod 5<\/p>\n Example: question 10a, page 41, from Underwood Dudley<\/strong>:<\/p>\n Consider the system of linear congruences<\/p>\n x + 2y ≡ 3 (mod 9) Solution: The first congruence suggests that <\/p>\n x + 2y = 9k + 3 for some integer k<\/p>\n ⇒ x = 9k + 3 – 2y<\/p>\n Substituting into the second congruence, we get<\/p>\n 3(9k + 3 – 2y) + y ≡ 2 (mod 9)<\/p>\n then<\/p>\n 27k + 9 -6y + y ≡ 2 (mod 9)<\/p>\n which means<\/p>\n 27k + 9 -5y = 9m + 2 for some integer m.<\/p>\n -5y = 9m + 2 – 27k – 9<\/p>\n Therefore,<\/p>\n -5y = 9(m -3k -1) + 2 ≡ 2 (mod 9)<\/p>\n From<\/p>\n -5y ≡ 2 (mod 9)<\/p>\n we can multiply both sides by -1 to arrive at<\/p>\n 5y ≡ -2 (mod 9)<\/p>\n Since -2 + 9 = 7, we can rewrite the congruence as<\/p>\n 5y ≡ 7 (mod 9)<\/p>\n Mod 9, there are only the integers 0 to 8. Trying each one, we realize y = 5:<\/p>\n 5(5) ≡ 7 (mod 9) since 25 mod 9 = 7<\/p>\n If y=5, we can sub it into the first equation<\/p>\n x + 2(5) ≡ 3 (mod 9)<\/p>\n x + 10 ≡ 3 (mod 9)<\/p>\n Subtracting 10 from both sides gives<\/p>\n x ≡ -7 (mod 9)<\/p>\n meaning<\/p>\n x ≡ 2 (mod 9)<\/p>\n So we have x = 9p + 2 and y = 9q +5, for any integers p,q.<\/p>\n I’ll be discussing more about linear congruences in future posts:)<\/p>\n Source:<\/p>\n Dudley, Underwood. Elementary Number Theory<\/u>,
3x + y ≡ 2 (mod 9)<\/p>\n
second edition. New York: W H Freeman and Company, 1978.<\/p>\n