Modular Arithmetic

Introduction

Modular arithmetic is a system of arithmetic for integers where the numbers wrap around when they reach a certain value. A good example is a clock. Once 12 is reached, the count resets. So given the set {0,1,2,3,4,5,6,7,8,9,10,11}, when 11 o'clock is reached we wrap back to 0.

Modulus

This is the *remainder* of a division. For example: 5 mod 3 means “what is left over when 5 is divided by 3?” 5 = 3 × 1 + 2 So 5 mod 3 = 2. The quotient (how many full times 3 fits into 5) is 1.

The set of all possible remainders modulo n is:

 ℤₙ = { 0, 1, 2, ..., n − 1 }

Arithmetic

All operations are done normally, then wrapped using mod n:

• Addition: (a + b) mod n
• Subtraction: (a − b) mod n
• Multiplication: (a × b) mod n

Congruence

Two integers a and b are congruent modulo n if they have the *same remainder* when divided by n.

 a ≡ b (mod n)

Example: 12 − 7 = 5 Now look at everything mod 5:

 2 mod 5 = 2  
 7 mod 5 = 2  
 12 mod 5 = 2  
 17 mod 5 = 2  

So:

 2 ≡ 7 ≡ 12 ≡ 17 (mod 5)