Solving Congruences Sec 4

Linear Congruences Definition: A congruence of the form ax ≡ b( mod m), where m is a positive integer, a and b are integers, and x is a variable, is called a linear congruence. The solutions to a linear congruence ax ≡ b( mod m) are all integers x that satisfy the congruence. Definition: An integer ā such that āa ≡ 1( mod m) is said to be an inverse of a modulo m. Example: 5 is an inverse of 3 modulo 7 since 5∙3 = 15 ≡ 1(mod 7) One method of solving linear congruences makes use of an inverse ā, if it exists. Although we can not divide both sides of the congruence by a, we can multiply by ā to solve for x. © 2019 McGraw-Hill Education Inverse of a modulo m The following theorem guarantees that an inverse of a modulo m exists whenever a and m are relatively prime. Two integers a and b are relatively prime when gcd(a,b) = 1. Theorem 1: If a and m are relatively prime integers and m > 1, then an inverse of a modulo m exists. Furthermore, this inverse is unique modulo m. (This means that there is a unique positive integer ā less than m that is an inverse of a modulo m and every other inverse of a modulo m is congruent to ā modulo m.) Proof: Since gcd(a,m) = 1, by Theorem 6 of Section 4.3, there are integers s and t such that sa + tm = 1. • • • • Hence, sa + tm ≡ 1 ( mod m). Since tm ≡ 0 ( mod m), it follows that sa ≡ 1 ( mod m) Consequently, s is an inverse of a modulo m. The uniqueness of the inverse is Exercise 7. © 2019 McGraw-Hill Education Finding Inverses 1 The Euclidean algorithm and Bézout coefficients gives us a systematic approaches to finding inverses. Example: Find an inverse of 3 modulo 7. Solution: Because gcd(3,7) = 1, by Theorem 1, an inverse of 3 modulo 7 exists. • Using the Euclidian algorithm: 7 = 2∙3 + 1. • From this equation, we get −2∙3 + 1∙7 = 1, and see that −2 and 1 are Bézout coefficients of 3 and 7. • Hence, −2 is an inverse of 3 modulo 7. • Also every integer congruent to −2 modulo 7 is an inverse of 3 modulo 7, i.e., 5, −9, 12, etc. © 2019 McGraw-Hill Education Finding Inverses 2 Example: Find an inverse of 101 modulo 4620. Solution: First use the Euclidian algorithm to show that gcd(101,4620) = 1. 42620 = 45∙101 + 75 Working Backwards: 101 = 1∙75 + 26 1 = 3 − 1∙2 75 = 2∙26 + 23 1 = 3 − 1∙(23 − 7∙3) = − 1 ∙23 + 8∙3 26 = 1∙23 + 3 1 = −1∙23 + 8∙(26 − 1∙23) = 8∙26 − 9 ∙23 23 = 7∙3 + 2 1 = 8∙26 − 9 ∙(75 − 2∙26 )= 26∙26 − 9 ∙75 3 = 1∙2 + 1 1 = 26∙(101 − 1∙75) − 9 ∙75 2 = 2∙1 Since the last nonzero remainder is 1, gcd(101,4260) = 1 Bézout coefficients : − 35 and 1601 © 2019 McGraw-Hill Education = 26∙101 − 35 ∙75 1 = 26∙101 − 35 ∙(42620 − 45∙101) = − 35 ∙42620 + 1601∙101 1601 is an inverse of 101 modulo 42620 Using Inverses to Solve Congruences We can solve the congruence ax≡ b( mod m) by multiplying both sides by ā. Example: What are the solutions of the congruence 3x≡ 4( mod 7). Solution: We found that −2 is an inverse of 3 modulo 7 (two slides back). We multiply both sides of the congruence by −2 giving −2 ∙ 3x ≡ −2 ∙ 4(mod 7). Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7), it follows that if x is a solution, then x ≡ −8 ≡ 6 (mod 7) We need to determine if every x with x ≡ 6 (mod 7) is a solution. Assume that x ≡ 6 (mod 7). By Theorem 5 of Section 4.1, it follows that 3x ≡ 3 ∙ 6 = 18 ≡ 4( mod 7) which shows that all such x satisfy the congruence. The solutions are the integers x such that x ≡ 6 (mod 7), namely, 6,13,20 … and −1, − 8, − 15,… © 2019 McGraw-Hill Education