Everything You Need to Know About Modular Arithmetic

1 Everything You Need to Know About Modular 135, February 7, 2006 DefinitionLetm>0 be a positive integer called themodulus. We say that two integersaandbarecongruent modulomifb ais divisible bym. In other words,a b(modm) a b=m kfor some integerk.(1)Note:1. The notation ?? ??(modm) works somewhat in the same way as the familiar ?? =??. be congruent to many numbers modulomas the following example 1 The equationx 16(mod10)has solutionsx=.., 24 14, 4,6,16,26,36, 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 notationa(MODm)DefinitionThe symbola(MODm)(2)denotes the smallest positive numberxsuch thatx a(modm).In other words,a(MODm) is the remainder whenais divided bymas many times as possible. Hence inexample 1 we have6 = 16(MOD10) and 6 = 24(MOD10) between x bmodm and x=bMODm x bmodmis an EQUIVALENCE relation with many solutions forxwhilex=bMODmis an one can think of the relationship between the two as followsx=b(MODm) is the smallest positive solution to the equationx b(modm).

2 Since0<b(MODm)<mit is convention to take these numbers as the representatives for the class of numbersx b(modm).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 in Modular arithmeticWe have the following rules for Modular Arithmetic :Sum rule:IFa b(modm) THENa+c b+c(modm).(3)Multiplication Rule:IFa b(modm) and ifc d(modm) THENac bd(modm).(4)DefinitionAn inverse toamodulomis a integerbsuch thatab 1(modm).(5)By definition (1) this means thatab 1 =k mfor some integerk. As before, there are may be manysolutions to this equation but we choose as a representative the smallest positive solution and say that theinversea 1is given bya 1=b(MODm).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 does not have an inverse modulo 10.

3 If 5 b 1(mod 10) then this means that 5 b 1 = 10 kfor somek. In other words5 b= 10 k 1 which is for an inverse ofato exist modulomDefinitionTwo numbers are relatively primeif their prime factorizations have no factors in 2 be an integer andaa number in the range 1 a m 1 ( a standard rep. of anumber modulom). Thenahas a multiplicative inverse modulomifaandmare relatively 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 5We can compute which numbers will have inverses modulo 10 by computing which are relatively primeto 10 = 5 2. These numbers arex= 1,3,7,9. It is easy to see that the following table gives inverses module10:2 Table 1: inverses modulo 10x1379x 1 MOD 101739Ex 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 exampleWe calculate the table of inverses modulo 26.

4 First note that26 = 13 2so that the only numbers that will have inverses are those which are rel. prime to they contain nofactors of 2 or 13:1,3,5,7,9,11,15,17,19,21,23, we write some multiples of 2626,52,78,104,130,156,182,208, numberahas an inverse modulo 26 if there is absuch thata b 1(mod 26)ora b= 26 k+ we are looking for numbers whose products are 1 more than a multiple of 26. We create the followingtableTable 2: inverses modulo 26x1357911151719212325x 1(MODm)1921153197231151725since (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 + we can solvey= 17 x+ 12(MOD 26)forxby 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 writex= 23 (y 12)(MOD 26).

5 The difference between23 (y 12) x(mod 26)andx= 23 (y 12)(MOD 26)is simply that in the first equation, a choice ofywill yield many different solutionsxwhile in the secondequation a choice ofygives the valuexsuch thatxis the smallest positive the smallest positivesolution to the first