Modular Congruence
a and b have the same remainder when divided by m.
Formula
Variables
Example
17 ≡ 5 (mod 12)
How it works
The statement a ≡ b (mod m) means that the difference a − b is divisible by m, so a and b land in the same remainder class when divided by m. This works because adding or subtracting any multiple of m does not change the remainder. In other words, congruence is a compact way to say two integers behave the same “up to multiples of m.”
When to use it
Use modular congruence when working with remainders, clock arithmetic, divisibility tests, or problems where only the remainder after division matters. It is especially useful in simplifying large numbers and checking whether one number fits into another with no remainder.
Worked example, step by step
Check whether 29 ≡ 5 (mod 8) Step 1: Compute the difference: 29 - 5 = 24 Step 2: Check if 24 is divisible by 8: 24 ÷ 8 = 3 Step 3: Since 24 is a multiple of 8, 29 and 5 have the same remainder when divided by 8 Step 4: Therefore, 29 ≡ 5 (mod 8)
Common mistakes to avoid
- Thinking congruence means the numbers are equal, instead of equal up to a multiple of the modulus
- Forgetting to check the difference a − b is divisible by m
- Using a non-integer modulus in a basic modular congruence problem
Did You Know?
Modular "clock" arithmetic underpins all modern cryptography, from online banking to messaging apps.
Share this formula
More in Number Theory
View allEuclidean Algorithm
BasicRecursively finds the greatest common divisor.
Fermat's Little Theorem
AdvancedHolds when p is prime and gcd(a,p)=1.
Euler's Totient
AdvancedCounts integers up to n coprime to n.
Prime Number Theorem
AdvancedApproximates the number of primes below x.
LCM from GCD
BasicLeast common multiple via the greatest common divisor.
Sum of First n Integers
BasicClosed form for the sum of the first n natural numbers.