Modular arithmetic is arithmetic based on remainders. Instead of treating integers as distinct solely by their ordinary values, modular arithmetic groups integers together when they leave the same remainder after division by a chosen positive integer called the modulus.
For example:
17 ÷ 5 = 3 remainder 2
so:
17 mod 5 = 2
Also:
17 ≡ 2 (mod 5)
because 17 and 2 differ by:
15
which is divisible by 5.
Another example is clock arithmetic. On a 12-hour clock:
10 + 5 = 15
but after wrapping around 12:
15 ≡ 3 (mod 12)
So five hours after 10 o’clock is 3 o’clock.
Modular arithmetic is fundamental to number theory, cyclic patterns, divisibility, computing, cryptography, checksums, calendars, and repeated processes.
What Is Modular Arithmetic?
Choose a positive integer:
n
called the modulus.
Every integer can be classified by its remainder after division by n.
For modulus 5, the possible canonical remainders are:
0, 1, 2, 3, 4
For example:
12 mod 5 = 2
17 mod 5 = 2
22 mod 5 = 2
These numbers all belong to the same residue class modulo 5.
That relationship can be written:
12 ≡ 17 ≡ 22 ≡ 2 (mod 5)
Modulo Formula
For an integer a and positive modulus n, write:
a = nq + r
where:
q = integer quotient
r = remainder
with:
0 ≤ r < n
Then:
a mod n = r
This is the same quotient-and-remainder structure used in ordinary long division.
Example
For:
a = 38
n = 7
we have:
38 = 7 × 5 + 3
Therefore:
38 mod 7 = 3
What Does a ≡ b (mod n) Mean?
The notation:
a ≡ b (mod n)
is read:
“a is congruent to b modulo n.”
It means that a and b leave the same remainder when divided by n.
An equivalent condition is:
n divides (a – b)
or:
a – b is a multiple of n
For example:
23 ≡ 3 (mod 10)
because:
23 – 3 = 20
and:
10 divides 20
Congruence vs. Equality
The statement:
17 = 2
is false in ordinary arithmetic.
But:
17 ≡ 2 (mod 5)
is true.
Congruence does not say the integers are equal. It says they occupy the same remainder class under the chosen modulus.
The modulus therefore changes which differences are treated as equivalent.
Finding a Modulo Remainder
Calculate:
47 mod 6
Divide:
47 = 6 × 7 + 5
Therefore:
47 mod 6 = 5
Check the required range:
0 ≤ 5 < 6
The result is a valid canonical remainder.
Example: 100 mod 9
Divide:
100 = 9 × 11 + 1
Therefore:
100 mod 9 = 1
This is also consistent with the divisibility-by-9 digit relationship:
1 + 0 + 0 = 1
so 100 leaves the same remainder as 1 modulo 9.
Exact Divisibility
If n divides a exactly:
a mod n = 0
For example:
48 mod 6 = 0
because:
48 = 6 × 8
This links modular arithmetic directly with divisibility rules.
A number is divisible by n exactly when:
a ≡ 0 (mod n)
Modular Arithmetic and Remainders
The dedicated remainders topic focuses on quotient-and-remainder calculations themselves.
Modular arithmetic uses those remainders as a complete arithmetic system.
For example, knowing:
53 mod 7 = 4
does more than report a remainder. It allows 53 to be replaced by 4 in many calculations performed modulo 7.
That replacement is the key efficiency of modular arithmetic.
Addition Modulo n
If:
a ≡ r (mod n)
and:
b ≡ s (mod n)
then:
a + b ≡ r + s (mod n)
You can reduce the result again if necessary.
Example
Calculate:
(17 + 29) mod 5
Reduce each number:
17 mod 5 = 2
29 mod 5 = 4
Add:
2 + 4 = 6
Reduce:
6 mod 5 = 1
Therefore:
(17 + 29) mod 5 = 1
Directly:
46 mod 5 = 1
The methods agree.
Subtraction Modulo n
Subtraction also preserves congruence:
a – b ≡ r – s (mod n)
Example:
(23 – 17) mod 5
Reduce:
23 mod 5 = 3
17 mod 5 = 2
Subtract:
3 – 2 = 1
Therefore:
(23 – 17) mod 5 = 1
Direct calculation:
23 – 17 = 6
6 mod 5 = 1
Multiplication Modulo n
Multiplication can also be reduced before the complete product is calculated:
ab ≡ rs (mod n)
if:
a ≡ r (mod n)
and:
b ≡ s (mod n)
Example
Calculate:
37 × 48 mod 5
Reduce:
37 mod 5 = 2
48 mod 5 = 3
Multiply:
2 × 3 = 6
Reduce:
6 mod 5 = 1
Therefore:
37 × 48 ≡ 1 (mod 5)
There is no need to calculate the full product first.
Modular Powers
Repeated multiplication can be reduced at every stage.
Calculate:
3⁴ mod 5
Start:
3² = 9
Reduce:
9 ≡ 4 (mod 5)
Then:
3⁴ = (3²)²
So:
3⁴ ≡ 4² (mod 5)
≡ 16 (mod 5)
≡ 1 (mod 5)
Therefore:
3⁴ mod 5 = 1
The ordinary power rules come from exponents; modular reduction keeps the intermediate values small.
Example: 2¹⁰ mod 7
Compute progressively.
2³ = 8 ≡ 1 (mod 7)
Then:
2⁹ = (2³)³
So:
2⁹ ≡ 1³
≡ 1 (mod 7)
Therefore:
2¹⁰ ≡ 2 (mod 7)
So:
2¹⁰ mod 7 = 2
Without modular reduction:
2¹⁰ = 1,024
and:
1,024 mod 7 = 2
The answer is the same.
Why Modular Reduction Works
If:
a ≡ r (mod n)
then:
a = r + kn
for some integer k.
When adding or multiplying such expressions, the terms containing n remain multiples of n.
For example:
a = r + kn
b = s + mn
Then:
ab = rs + rmn + skn + kmn²
Everything after rs contains a factor of n.
Therefore:
ab ≡ rs (mod n)
This explains why large values may be replaced by small equivalent residues.
Negative Numbers Modulo n
With the standard positive-modulus convention, choose the remainder:
0 ≤ r < n
For example:
-3 mod 5
We want:
-3 = 5q + r
Choose:
q = -1
Then:
-3 = 5(-1) + 2
Therefore:
-3 mod 5 = 2
Equivalently:
-3 ≡ 2 (mod 5)
because:
-3 – 2 = -5
which is divisible by 5.
Another Negative Example
Find:
-17 mod 6
We can add multiples of 6 until reaching the canonical remainder range.
-17 + 18 = 1
Since:
18 = 3 × 6
we have:
-17 ≡ 1 (mod 6)
Therefore:
-17 mod 6 = 1
Different programming languages may use different sign conventions for remainder operators, so mathematical modulo and software remainder behavior should not always be assumed identical.
Clock Arithmetic
A 12-hour clock is a familiar modular system.
Suppose it is:
9 o’clock
What time is it after 8 hours?
Calculate:
9 + 8 = 17
Reduce modulo 12:
17 mod 12 = 5
Therefore:
5 o’clock
The clock “wraps around” after each complete cycle of 12.
Why Clocks Are Slightly Different in Display
Mathematical residues modulo 12 are normally:
0 through 11
But ordinary clocks display:
12 instead of 0
So:
24 mod 12 = 0
corresponds to:
12 o’clock
The underlying modular cycle is still the same.
Day-of-Week Arithmetic
Days repeat every:
7 days
so weekday calculations naturally use modulus 7.
Suppose today is represented by residue:
2
and you want the weekday:
10 days later
Calculate:
2 + 10 = 12
Then:
12 mod 7 = 5
Therefore the future day has residue:
5
Only the chosen mapping between residue numbers and weekday names is needed to interpret the final result.
Even and Odd Numbers as Modulo 2
Parity is modular arithmetic with:
modulus 2
An even integer satisfies:
n ≡ 0 (mod 2)
An odd integer satisfies:
n ≡ 1 (mod 2)
For example:
18 mod 2 = 0
so 18 is even.
27 mod 2 = 1
so 27 is odd.
This makes many even/odd proofs compact.
Adding Parities
Using modulo 2:
Odd plus odd:
1 + 1 = 2
and:
2 ≡ 0 (mod 2)
Therefore:
odd + odd = even
Odd plus even:
1 + 0 ≡ 1 (mod 2)
Therefore:
odd + even = odd
Even plus even:
0 + 0 ≡ 0 (mod 2)
Therefore:
even + even = even
Last Digit Using Modulo 10
The last decimal digit of a nonnegative integer is its remainder modulo 10.
For example:
12,347 mod 10 = 7
Therefore the last digit is:
7
Likewise:
890 mod 10 = 0
This property makes modulus 10 useful in decimal digit problems.
Last Two Digits Using Modulo 100
The final two decimal digits correspond to modulo 100.
For example:
12,347 mod 100 = 47
Therefore the final two digits are:
47
Similarly:
8,006 mod 100 = 6
which may be displayed as:
06
when two digit positions must be preserved.
Modular Arithmetic and Multiples
Two congruent integers differ by a multiple of the modulus.
For example:
38 ≡ 3 (mod 5)
because:
38 – 3 = 35
and:
35 = 5 × 7
In general:
a ≡ b (mod n) ⇔ a – b = kn
for some integer k.
This connection between congruence and multiples is foundational.
Modular Arithmetic and Factors
Suppose:
a ≡ 0 (mod n)
Then n divides a.
Therefore:
n
is a factor of a.
For example:
84 ≡ 0 (mod 7)
so:
7 is a factor of 84
Modular notation can therefore express exact divisibility compactly.
Modular Arithmetic and the Euclidean Algorithm
The Euclidean algorithm repeatedly computes remainders.
For example:
252 mod 105 = 42
Then:
105 mod 42 = 21
Then:
42 mod 21 = 0
The last nonzero remainder is:
21
Therefore:
GCD(252,105) = 21
Modulo notation gives a concise way to express the repeated remainder calculations.
Modular Arithmetic and GCF
The GCF determines when certain modular operations, particularly division through inverses, are possible.
An integer a has a multiplicative inverse modulo n exactly when:
GCF(a,n) = 1
For example:
GCF(3,7) = 1
so 3 has an inverse modulo 7.
But:
GCF(3,6) = 3
so 3 has no multiplicative inverse modulo 6.
Modular Inverse
A modular inverse of a modulo n is an integer x satisfying:
ax ≡ 1 (mod n)
For example, find the inverse of 3 modulo 7.
Try:
3 × 5 = 15
and:
15 ≡ 1 (mod 7)
Therefore:
3⁻¹ ≡ 5 (mod 7)
This inverse makes a controlled form of modular division possible.
Why Ordinary Division Is Different Modulo n
Addition, subtraction, and multiplication work naturally under congruence.
Division requires more care.
For example:
2x ≡ 4 (mod 6)
It might seem natural to divide both sides by 2 and write:
x ≡ 2 (mod 6)
But the original congruence has multiple solution classes:
x ≡ 2 (mod 3)
which corresponds modulo 6 to:
x ≡ 2 or 5 (mod 6)
Ordinary cancellation can therefore lose solutions when the cancelled value is not invertible modulo the modulus.
Safe Modular Division
To divide by a modulo n, a should have a modular inverse.
This occurs when:
GCF(a,n) = 1
For example:
3x ≡ 2 (mod 7)
Since:
3⁻¹ ≡ 5 (mod 7)
multiply both sides by 5:
x ≡ 10 (mod 7)
Reduce:
x ≡ 3 (mod 7)
Check:
3 × 3 = 9
9 ≡ 2 (mod 7)
Solving a Simple Modular Equation
Solve:
x + 4 ≡ 2 (mod 7)
Subtract 4:
x ≡ -2 (mod 7)
Convert to canonical residue:
-2 + 7 = 5
Therefore:
x ≡ 5 (mod 7)
Check:
5 + 4 = 9
and:
9 mod 7 = 2
Solve 2x ≡ 3 (mod 5)
The inverse of 2 modulo 5 is 3 because:
2 × 3 = 6
and:
6 ≡ 1 (mod 5)
Multiply both sides by 3:
x ≡ 9 (mod 5)
Reduce:
x ≡ 4 (mod 5)
Check:
2 × 4 = 8
8 mod 5 = 3
Modular Arithmetic With Large Sums
Calculate:
(12,345 + 67,890) mod 9
Reduce each number.
For 12,345, digit sum:
1 + 2 + 3 + 4 + 5 = 15
and:
15 mod 9 = 6
So:
12,345 ≡ 6 (mod 9)
For 67,890:
6 + 7 + 8 + 9 + 0 = 30
30 mod 9 = 3
Therefore:
12,345 + 67,890 ≡ 6 + 3
≡ 9
≡ 0 (mod 9)
So:
(12,345 + 67,890) mod 9 = 0
Modular Arithmetic With Large Products
Find:
1,234 × 5,678 mod 7
Reduce:
1,234 mod 7 = 2
because:
1,234 = 7 × 176 + 2
Also:
5,678 mod 7 = 1
because:
5,678 = 7 × 811 + 1
Therefore:
1,234 × 5,678 ≡ 2 × 1
≡ 2 (mod 7)
So:
1,234 × 5,678 mod 7 = 2
The full product never needs to be calculated.
Cycles of Powers
Powers often repeat in modular arithmetic.
Consider powers of 2 modulo 5:
2¹ ≡ 2
2² ≡ 4
2³ ≡ 8 ≡ 3
2⁴ ≡ 6 ≡ 1
2⁵ ≡ 2
The cycle repeats every four powers:
2, 4, 3, 1, …
This periodicity allows extremely large exponents to be reduced to small cycle positions.
Example With a Large Exponent
Find:
2¹⁰⁰ mod 5
The powers repeat every 4.
Calculate:
100 mod 4 = 0
So the exponent corresponds to the fourth position in the cycle:
2⁴ ≡ 1 (mod 5)
Therefore:
2¹⁰⁰ mod 5 = 1
Modular Arithmetic and Least Common Multiple
If several periodic processes have different cycle lengths, their combined pattern may repeat after a least common multiple of the cycle lengths.
Suppose one process repeats modulo 4 and another every 6 steps.
The combined alignment repeats after:
LCM(4,6) = 12
This combines modular-cycle thinking with common-multiple structure.
Modular Arithmetic and Prime Numbers
Prime numbers are especially important in modular arithmetic because every nonzero residue modulo a prime has a multiplicative inverse.
For modulus 7, the nonzero residues are:
1,2,3,4,5,6
Each has an inverse modulo 7.
For example:
2 × 4 ≡ 1 (mod 7)
3 × 5 ≡ 1 (mod 7)
6 × 6 ≡ 1 (mod 7)
This property is one reason prime moduli are central in number theory.
Modular Arithmetic and Integer Operations
All congruence calculations ultimately depend on integer operations.
Addition, subtraction, multiplication, powers, and exact divisibility are carried out on integers before or during reduction modulo n.
For example:
-8 + 13 = 5
therefore:
-8 + 13 ≡ 5 (mod 7)
and:
5 mod 7 = 5
The sign rules remain ordinary integer rules.
Modular Arithmetic and Binary Numbers
Binary numbers often interact naturally with powers of 2 and modular calculations.
For example, checking whether an integer is even is equivalent to:
n mod 2 = 0
The final binary digit gives the same information:
ending in 0 → even
ending in 1 → odd
The numeral representation and modular remainder encode the same parity property in different ways.
Modular Arithmetic and Check Digits
Many identification systems use weighted sums followed by a modulus.
A simplified example might compute:
S = sum of selected digits
and then evaluate:
S mod 10
The remainder can be used to produce or verify a check digit.
The exact rule depends on the identification system, but the mathematical mechanism is modular arithmetic: different large totals are reduced to a small set of residue classes.
Modular Arithmetic and Hash-Like Bucketing
Suppose 100 numbered items must be assigned to 8 repeating buckets.
A simple rule could be:
Bucket = item number mod 8
Then:
21 mod 8 = 5
so item 21 goes to residue bucket 5.
Likewise:
29 mod 8 = 5
Both values fall into the same modular class.
This illustrates why modulo operations are useful whenever a large integer range must wrap into a fixed number of positions.
Modulo 1
For every integer a:
a mod 1 = 0
because every integer is divisible by 1.
There is only one residue class modulo 1.
Although mathematically valid, modulus 1 has little distinction among integers because all of them are congruent:
a ≡ b (mod 1)
for every pair of integers a and b.
Modulus Zero Is Not Used
Ordinary modular arithmetic requires a positive modulus.
An expression such as:
a mod 0
is undefined because division by zero is undefined.
Therefore:
n > 0
is the standard assumption for the modulus in elementary modular arithmetic.
Common Mistake: Confusing mod With Ordinary Division
For:
17 mod 5
the answer is not:
3.4
The modulo operation asks for the remainder:
17 = 5 × 3 + 2
Therefore:
17 mod 5 = 2
Ordinary division asks for the quotient; modulo asks for the remainder.
Common Mistake: Returning a Remainder Outside the Canonical Range
For positive modulus 7, the canonical remainder should satisfy:
0 ≤ r < 7
So:
-2
may be congruent to 5 modulo 7, but the standard nonnegative remainder is:
5
because:
-2 ≡ 5 (mod 7)
Common Mistake: Treating Congruence as Equality
From:
14 ≡ 2 (mod 12)
you cannot conclude:
14 = 2
The numbers differ by:
12
which is a multiple of the modulus.
Congruence is an equivalence relationship under modular arithmetic, not ordinary numerical equality.
Common Mistake: Canceling Without Checking Invertibility
Suppose:
2x ≡ 2 (mod 6)
Blindly dividing by 2 gives:
x ≡ 1 (mod 6)
But test:
x = 4
Then:
2 × 4 = 8
and:
8 ≡ 2 (mod 6)
So x = 4 is also a solution.
The reason is:
GCF(2,6) ≠ 1
so 2 is not invertible modulo 6.
Modular division requires additional conditions.
Common Mistake: Reducing an Exponent Instead of the Base Without Justification
For:
3^k mod 7
you may always reduce the base:
10^k ≡ 3^k (mod 7)
because:
10 ≡ 3 (mod 7)
But reducing the exponent modulo 7 itself is not automatically valid.
Exponent reduction depends on periodicity or specific number-theory results.
The modulus of the base and the cycle length of the powers are different concepts.
How to Check a Congruence
Suppose:
47 ≡ 5 (mod 7)
Subtract:
47 – 5 = 42
Check:
42 ÷ 7 = 6
Since the difference is divisible by the modulus:
47 ≡ 5 (mod 7)
This difference test is one of the simplest ways to verify a congruence.
How to Check a Modular Remainder
Suppose:
83 mod 9 = 2
Verify:
83 = 9 × 9 + 2
and:
0 ≤ 2 < 9
Both conditions hold.
Therefore the remainder is correct.
Frequently Asked Questions
What is modular arithmetic?
Modular arithmetic is arithmetic based on remainder classes after division by a fixed positive integer called the modulus.
What does mod mean?
a mod n is the canonical remainder when integer a is divided by positive integer n.
What is 17 mod 5?
2
because:
17 = 5 × 3 + 2
What does a ≡ b (mod n) mean?
It means a and b leave the same remainder modulo n, or equivalently:
n divides a – b
What is 23 mod 7?
23 = 7 × 3 + 2
Therefore:
23 mod 7 = 2
What is -3 mod 5?
Using the standard nonnegative remainder convention:
-3 mod 5 = 2
because:
-3 = 5(-1) + 2
Can you add numbers modulo n?
Yes.
(a+b) mod n
can be calculated after reducing a and b modulo n.
Can you multiply modulo n?
Yes. Products may be reduced before or after multiplication.
Can you divide in modular arithmetic?
Not through ordinary division in general. Division by a is possible through a modular inverse when a is invertible modulo n.
When does a modular inverse exist?
For integer a modulo n, an inverse exists exactly when:
GCF(a,n) = 1
Why is clock arithmetic modular?
Clock positions repeat after a fixed number of hours, so values wrap around after reaching the modulus.
What modulus determines even and odd numbers?
Modulus 2
Even numbers are congruent to 0 modulo 2, while odd numbers are congruent to 1 modulo 2.
Final Example
Calculate:
7⁵ + 12 × 19 mod 11
Reduce the bases first.
For 7⁵, compute modular powers:
7² = 49
49 mod 11 = 5
Then:
7⁴ ≡ 5²
≡ 25
≡ 3 (mod 11)
Therefore:
7⁵ ≡ 3 × 7
≡ 21
≡ 10 (mod 11)
Now reduce the product:
12 ≡ 1 (mod 11)
19 ≡ 8 (mod 11)
So:
12 × 19 ≡ 1 × 8
≡ 8 (mod 11)
Add:
10 + 8 = 18
Reduce:
18 mod 11 = 7
Therefore:
(7⁵ + 12 × 19) mod 11 = 7
Modular arithmetic works by replacing integers with simpler congruent representatives while preserving addition, subtraction, and multiplication:
a ≡ b (mod n) ⇔ n divides (a – b)
and:
a mod n = r
where:
a = nq + r, 0 ≤ r < n
These two relationships form the foundation for remainder arithmetic, cyclic calculations, modular equations, and more advanced number theory.
