Iwiseman: Created page with "=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..."

2026-04-18T04:10:24Z

Created page with "=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..."

New page

=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)

Modular Arithmetic - Revision history