Modular Arithmetic

Problems that involve large integers can be simplified by a technique called modular arithmetic. This technique uses the arithmetic of congruences in place of traditional equations. The basic idea involves choosing an integer n, which is called the modulus, and replace every integer with its remainder when divided by n. To illustrate this, let’s look at an example: What day of the week will it be 100 days from now? Most of us would solve this by getting out a diary and counting up 100 days until we found the answer. However, we can solve this using modular arithmetic. We know that the week repeats the same 7-day cycle and 100 = 14 x 7 + 2, so the day of the week in 100 days’ time will be the day of the week it is today plus 2. E.g. if today is Monday, the answer is Wednesday. Here, we chose n = 7, and replaced 100 with its remainder on division by 7 which is 2. Definition Let n be a positive integer, and let a and b be any integers. We say that a is congruent to b mod (n), or a is a residue of b mod (n), written

If a and b leave the same remainder when divided by n. To be more precise, we use the division algorithm to put a = qn +r with 0 ≤ r < n, and b = q'n + r' with 0 ≤ r' < n. We can then say a ≡ b mod (n) if and only if r = r'. Lemma For any fixed n ≥ 1, we have a ≡ b mod (n) if and only if n divides (a – b). Proof: From above, let a = qn +r and b = q'n + r' which gives a – b = (q - q')n + (r – r') with -n < r – r' < n. If a ≡ b mod (n) then r = r', so r – r’ = 0 and a – b = (q – q')n, which is divisible by n. Conversly, if n divides a – b then it divides (a – b) – (q – q')n = r – r'. The only integer strictly between -n and n which is divisible by n is 0, so r – r' = 0, giving r = r' and hence a ≡ b mod (n). ■ Example: As we can see, 52 and 24 are congruent (mod 7) because 52 (mod 7) = 3 and 24 (mod 7) = 3. Modular arithmetic has several important properties regarding addition, multiplication, exponentiation and division. We will walk through each of the properties and an example of each to help your understanding. Division is a little bit tricky so we will leave this out but please feel free to do your own research regarding modular division. Properties of addition in modular arithmetic: 1. If a + b = c, then a (mod n) + b (mod n) ≡ c (mod n). 2. If a ≡ b (mod n), then a + k ≡ b + k (nod n) for any integer k. 3. If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n). 4. If a ≡ b (mod n), then -a ≡ -b (mod n). Example: Find the sum of 31 and 148 in modulo 24. 31 in modulo 24 is equivalent to 7. If we use the first addition property, 155 in modulo 24 is 11. Properties of multiplication in modular arithmetic: 1. If a . b = c, then a (mod n) . b (mod n) ≡ c (mod n). 2. If a ≡ b (mod n), then ka ≡ (mod n) for any integer k. 3. If a ≡ b (mod n) and c ≡ d (mod n), then ac &equiv bd (mod n). Example: What is (8 x 16) (mod 7)? Since 8 ≡ 1 (mod 7) and 16 ≡ 2 (mod 7), we have Properties of exponentation in modular arithmetic: If a ≡ b (mod n), then a^k ≡ b^k (mod n) for any positive integer k. Example: What is 3¹⁶ (mod 4)? By observation, Using the property of exponentiation, These properties help us calculate values that are used in RSA. Written by JaneW