2 Modular arithmetic On page 1 of his masterpiece on number theory, Disquisitiones Arithmeticae, Gauss intro- duced the notion of"congruence". Now, Gauss is another guy who managed to cough up a half-decent idea every now and then, so let's take a look at this one. Gauss said that a is congruent to b modulo n if n (a-b). This is denoted a= b(mod n). For example 29= 15(mod 7) because 7(29-15) Intuitively, the symbol is sort of like an=sign, and the mod 7 describes the specific sense in which 29 is equal-ish to 15. Thus, even though(mod 7) appears over on the right side, it is in no sense more strongly associated with the 15 than the 29; in fact, it actually defines the meaning of the sign Here's another way to think about congruences: congruence modulo n defines a partition of the integers into n sets so that congruent numbers are all in the same set. For example, suppose that were working modulo 3. Then we can partition the integers into 3 sets as follows 0,3,6,9 1,4,7,10, Now integers in the same set are all congruent modulo 3. For example, 6 and-3 are both in the first set, and theyre congruent because their difference, 6 =9, is a multiple of 3 Similarly, 1l and 5 are both in the last set because 11-5=6 is a multiple of 3. On the other hand, numbers in different sets are not congruent. For example, 9 is in the first set and 11 in the last set, and theyre not congruent because 11-9=2 is not a multiple of 3. The upshot is that when arithmetic is done modulo n there are only n really different kinds of number to worry about. In this sense, modular arithmetic is a simplification of ordinary arithmetic and thus is a good reasoning tool There are many useful facts about congruences, some of which are listed in the lemma below. The overall theme is that congruences work a lot like equations, though ther re are a couple exceptions Lemma 1(Facts About Congruences). The following hold forn>1 1.a≡a(modn) 2.a≡b(modm) implies b≡a(modn) 3.a≡b(modm)andb≡c(modn) implies a≡c(modn) 4.a≡b(modn) implies a+c≡b+c(modn) 5.a≡b(modn) implies ac≡be(modn) 6.a≡b(modn)andc≡d(modn) imply a+c≡b+d(modm)4 Number Theory II 2 Modular Arithmetic On page 1 of his masterpiece on number theory, Disquisitiones Arithmeticae, Gauss intro￾duced the notion of “congruence”. Now, Gauss is another guy who managed to cough up a half­decent idea every now and then, so let’s take a look at this one. Gauss said that a is congruent to b modulo n if n | (a − b). This is denoted a ≡ b (mod n). For example: 29 ≡ 15 (mod 7) because 7 (29 | − 15). Intuitively, the ≡ symbol is sort of like an = sign, and the mod 7 describes the specific sense in which 29 is equal­ish to 15. Thus, even though (mod 7) appears over on the right side, it is in no sense more strongly associated with the 15 than the 29; in fact, it actually defines the meaning of the ≡ sign. Here’s another way to think about congruences: congruence modulo n defines a partition of the integers into n sets so that congruent numbers are all in the same set. For example, suppose that we’re working modulo 3. Then we can partition the integers into 3 sets as follows: { . . . , −6, −3, 0, 3, 6, 9, . . . } { . . . , −5, −2, 1, 4, 7, 10, . . . . . . , −4, −1, 2, 5, 8, 11, . . . } { } Now integers in the same set are all congruent modulo 3. For example, 6 and ­3 are both in the first set, and they’re congruent because their difference, 6 − (−3) = 9, is a multiple of 3. Similarly, 11 and 5 are both in the last set, because 11 − 5 = 6 is a multiple of 3. On the other hand, numbers in different sets are not congruent. For example, 9 is in the first set and 11 in the last set, and they’re not congruent because 11 − 9 = 2 is not a multiple of 3. The upshot is that when arithmetic is done modulo n there are only n really different kinds of number to worry about. In this sense, modular arithmetic is a simplification of ordinary arithmetic and thus is a good reasoning tool. There are many useful facts about congruences, some of which are listed in the lemma below. The overall theme is that congruences work a lot like equations, though there are a couple exceptions. Lemma 1 (Facts About Congruences). The following hold for n ≥ 1: 1. a ≡ a (mod n) 2. a ≡ b (mod n) implies b ≡ a (mod n) 3. a ≡ b (mod n) and b ≡ c (mod n) implies a ≡ c (mod n) 4. a ≡ b (mod n) implies a + c ≡ b + c (mod n) 5. a ≡ b (mod n) implies ac ≡ bc (mod n) 6. a ≡ b (mod n) and c ≡ d (mod n) imply a + c ≡ b + d (mod n)