Everything You Need to Know About Modular Arithmetic...Math 135, February 7, 2006Definition Let m > 0 be a positive integer called the modulus. We say that two integers a and b arecongruent modulo m if b − a is divisible by m. In other words,a ≡ b(modm) ⇐⇒ a − b = m · k for some integerk. (1)Note:1. The notation ?? ≡??(modm) works somewhat in the same way as the familiar ?? =??.2. a can be congruent to many numbers modulo m as the following example illustrates.Ex. 1 The equationx ≡ 16(mod10)has solutions x = . . . , −24 − 14, −4, 6, 16, 26, 36, 46 . . . . This follows from equation (1) since any of thesenumbers minus 16 is divisible by 10. So we can writex ≡ · · · − 24 ≡ −14 ≡ −4 ≡ 6 ≡ 16 ≡ 26 ≡ 36 ≡ 46(mod10).Since such equations have many solutions we introduce the notation a(MODm)Definition The symbola(MODm) (2)denotes the smallest positive number x such thatx ≡ a(modm).In other words, a(MODm) is the remainder when a is divided by m as many times as possible. Hence inexample 1 we have6 = 16(MOD10) and 6 = −24(MOD10) etc....Relation between ”x ≡ b mod m” and ”x = b MOD m”x ≡ b mod m is an EQUIVALENCE relation with many solutions for x while x = b MOD m is an EQUALITY.So one can think of the relationship between the two as followsx = b(MOD m) is the smallest positive solution to the equation x ≡ b(mod m).Since0 < b(MOD m) < mit is convention to take these numbers as the representatives for the class of numbers x ≡ b(mod m).1Ex. 2 The standard representatives for all possible numbers modulo 10 are given by0, 1, 2, 3, 4, 5, 6, 7, 8, 9although, for example, 3 ≡ 13 ≡ 23(mod 10), we would take the smallest positive such number which is 3.Inverses in Modular arithmeticWe have the following rules for modular arithmetic:Sum rule: IF a ≡ b(mod m) THEN a + c ≡ b + c(mod m). (3)Multiplication Rule: IF a ≡ b(mod m) and if c ≡ d(mod m) THEN ac ≡ bd(mod m). (4)Definition An inverse to a modulo m is a integer b such thatab ≡ 1(mod m). (5)By definition (1) this means that ab − 1 = k · m for some integer k. As before, there are may be manysolutions to this equation but we choose as a representative the smallest positive solution and say that theinverse a−1is given bya−1= b (MOD m).Ex 3. 3 has inverse 7 modulo 10 since 3 · 7 = 21 shows that3 · 7 ≡ 1(mod 10) since 3 · 7 − 1 = 21 − 1 = 2 · 10.5 does not have an inverse modulo 10. If 5 · b ≡ 1(mod 10) then this means that 5 · b − 1 = 10 · k for somek. In other words5 · b = 10 · k − 1 which is impossible.Conditions for an inverse of a to exist modulo mDefinition Two numbe rs are relatively prime if their prime factorizations have no factors in common.Theorem Let m ≥ 2 be an integer and a a number in the range 1 ≤ a ≤ m − 1 (i.e. a standard rep. of anumber modulo m). Then a has a multiplicative inverse modulo m if a and m are relatively prime.Ex 4 Continuing with example 3 we can write 10 = 5 · 2. Thus, 3 is relatively prime to 10 and has an inversemodulo 10 while 5 is not relatively prime to 10 and therefore has no inverse modulo 10.Ex 5 We can compute which numbers will have inverses modulo 10 by computing which are relatively primeto 10 = 5 · 2. These numbers are x = 1, 3, 7, 9. It is easy to see that the following table gives inverses module10:2Table 1: inverses m odulo 10x 1 3 7 9x−1MOD 10 1 7 3 9Ex 6: We can solve the equation 3 · x + 6 ≡ 8(mod 10) by using the sum (3) and multiplication (4) rulesalong with the above table:3 · x + 6 ≡ 8(mod 10) =⇒3 · x ≡ 8 − 6 ≡ 2(mod 10) =⇒(3−1) · 3 · x ≡ (3−1) · 2(mod 10) =⇒x ≡ 7 · 2(mod 10) ≡ 14(mod 10) ≡ 4(mod 10)Final example We calculate the table of inverses modulo 26. First note that26 = 13 · 2so that the only numbers that will have inverses are those which are rel. prime to 26...i.e. they contain nofactors of 2 or 13:1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.Now we write some multiples of 2626, 52, 78, 104, 130, 156, 182, 208, 234...A number a has an inverse modulo 26 if there is a b such thata · b ≡ 1(mod 26)or a · b = 26 · k + 1.thus we are looking for numbers whose products are 1 more than a multiple of 26. We create the followingtableTable 2: inverses m odulo 26x 1 3 5 7 9 11 15 17 19 21 23 25x−1(MOD m) 1 9 21 15 3 19 7 23 11 5 17 25since (using the list of multiples of 26 above)1 · 1 = 1 = 26 · 0 + 13 · 9 = 27 = 26 + 15 · 21 = 105 = 104 + 17 · 15 = 105 = 104 + 111 · 19 = 209 = 208 + 117 · 23 = 391 = 15 · 26 + 125 · 25 = 625 = 26 · 24 + 1.3So we can solvey = 17 · x + 12(MOD 26)for x by first considering the congruence equationy ≡ 17 · x + 12(mod 26)and performing the following calculation (similar to ex 6) using the above table:y ≡ 17 · x + 12(mod 26) =⇒y − 12 ≡ 17 · x(mod 26) =⇒(17−1)(y − 12) ≡ (17−1) · 17 · x(mod 26) =⇒(23)(y − 12) ≡ (23) · 17 · x(mod 26) =⇒23 · (y − 12) ≡ x(mod 26)We now write x = 23 · (y − 12)(MOD 26).The difference between23 · (y − 12) ≡ x(mod 26)andx = 23 · (y − 12)(MOD 26)is simply that in the first equation, a choice of y will yield many different solutions x while in the se condequation a choice of y gives the value x such that x is the smallest positive solution...i.e. the smallest positivesolution to the first