Modular Arithmetic | Research & Encyclopedia Articles

Modular Arithmetic

Modular arithmetic is a generalization of odd and even. We say that two integers, x and y, are congruent modulo a third integer n if and only if x - y is divisible by n. For example, 5 and 8 are congruent modulo 3 because 5 - 8 = -3 is divisible by 3. However, 4 and 5 are not congruent modulo 3. A number is even if it is congruent to zero modulo two. It is odd if it is congruent to one modulo two. The notation "x y mod(n)" means "x is congruent to y modulo n." The notation gcd(m, n) means the greatest common divisor (or factor) of m and n.Here are the basic facts about modular arithmetic:

• if x y mod(n) and z w mod(n), then x + z y + w mod(n) and xz yw mod(n).
• if xm ym mod (n) and gcd(m, n) = 1 then x y mod(n).

Here is the proof of the first fact. Since x y mod(n) and z w mod(n) there are integers j and k such that x - y = nj and z - w = nk. Then x + z - (y + w) = (x - y) + (z - w) = nj + nk = n(j + k). Thus x + z y + w mod(n). Also xz = (y + nj)(w + nk) = yw + n(jw + ky + jkn). Thus xz yw mod(n).

Here is the proof of the second fact. Since xm ym mod(n) there is an integer k such that xm - ym = kn. Since gcd(m, n) = 1, and m divides kn, m must divide k. So k/m is an integer and x - y = (k/m)n. So x y mod(n). On the other hand, if gcd(m, n) is not one then x does not have to be congruent to y. For example, suppose m = 2, n = 4, x = 1, and y = 3. Then, 2 is congruent to 6 modulo 4 but 1 is not congruent to 3 modulo 4.

Modular arithmetic is a fundamental tool used by mathematicians in practically every field but most commonly, it used by number theorists. Modern cryptography uses modular arithmetic extensively. Here is how public key cryptosystems work. First there is a method, known to everyone, for encoding messages into numbers or sequences of numbers. If, say, Jane wants to receive secret messages, then she publishes two numbers, e and N, say. If Bob wants to send Jane a message, then he first writes his message and his computer translates it into a number M. Then his computer raises M to the power of e and sends the remainder after dividing by N to Jane's computer. In other words, Bob's computer sends M^e modulo N. Jane has a number, that she keeps secret, called d. Her computer raises the number it received from Bob to the power of d and takes the remainder modulo N. The trick is that e, d, and N are specially chosen so that if M is any number, then M^ed M mod(N). So, now Jane's computer can translate M back to Bob's message. This system works for two main reasons. First, a computer can quickly calculate M^e and M^ed modulo N. Second, it is currently very hard (even for a computer) to figure out what d is if you only know what e and N are and if they are large (100 digits or more). Most cryptosystems today use some variation of this method.

Here is an example illustrating how easy it is to calculate M^e modulo N. Suppose M is 7, e is 1000 and N is 10. 7¹⁰⁰⁰ = (7²)⁵⁰⁰ = (49)⁵⁰⁰ 9⁵⁰⁰ mod(10). 9⁵⁰⁰ = (9²)²⁵⁰ = (81)²⁵⁰ 1²⁵⁰ mod (10). 1²⁵⁰ = 1. So the answer is, 7¹⁰⁰⁰ 1 mod(10).

Gauss' favorite number theory theorem, the law of quadratic reciprocity, uses modular arithmetic. We say that x is a quadratic residue modulo N if x y² mod(N) for some integer y. The Legendre symbol (p/q) is defined to equal 1 if p is a quadratic residue modulo q, and it is equal to -1 otherwise. Gauss' "aureum theorema" is the following: If p and q are distinct odd primes, then (p/q)(q/p) = (-1)^(p1)(q-1)/4. Although Euler stated this theorem in 1783, Gauss was the first to prove it in 1796. Since Gauss, more than fifty different proofs have been found.

Another theorem from number theory states that if p is an odd prime then there are integers x and y such that p = x² + y² if and only if p is congruent to 1 modulo 4. This is called the genus theorem.