Modular congruence
State that two integers have the same remainder modulo $n$.
Modular congruence is one of 2 number theory formulas in the discrete math section of this library, and it is used at university level.
Why modular congruence works
Two numbers land on the same spot of a clock face with n hours exactly when the distance between them is a whole number of full trips around. That distance is a − b, and a whole number of trips means n divides it evenly. The congruence sign is a way of saying same position, not same number.
What each symbol means
$n$ is the modulus.
Modular congruence: when it holds
$n$ is a positive integer in the standard convention.
When it stops applying
Division is the operation that does not carry over. Addition, subtraction, and multiplication all respect congruence, but you can only divide by a number that has an inverse mod n, which requires its gcd with n to be 1.
Modular congruence: a worked example
$17\equiv5\pmod{12}$ because $12\mid(17-5)$.
The mistake to avoid
What people do: Students treat the congruence like an ordinary equation and cancel a common factor from both sides.
Why it goes wrong: Cancelling is only safe when the factor shares no divisor with the modulus. It is true that 2 times 3 is congruent to 2 times 0 mod 6, but cancelling the 2 would claim 3 is congruent to 0 mod 6, which is false.
Do this instead: Check that the factor you want to remove is coprime with n before cancelling. With modulus 7 you may cancel any nonzero factor freely, since 7 is prime.
Modular congruence: step by step
- Name the unknown, and the unit the answer has to come out in.
- Match the symbols to your values. $n$ is the modulus.
- Check the conditions before substituting. $n$ is a positive integer in the standard convention.
- Substitute, keep exact values to the last line, then test the sign, size, and unit against a rough estimate — the check that catches most discrete math slips.
Where this formula fits
- Subject
- Discrete Math formulas — 11 entries in this library
- Topic
- Number theory
- Level
- University
Formulas are easiest to keep when they sit inside a method rather than on a list. Use the links below to see where modular congruence comes from, to check a calculation against a tool, and to practise it until you can recall it without looking.
- Discrete Math Calculator — check your substitution and the value it produces.
- Study discrete math — the subject guide that explains the ideas these formulas compress.
- Discrete Math Practice — questions that make you retrieve the formula instead of recognising it.
- All 11 discrete math formulas — the full grouped reference, or the complete formula library.
Questions about modular congruence
Is a ≡ b (mod n) the same as saying a mod n equals b mod n?
Yes, they say the same thing. The first phrasing is about the difference being divisible by n, and the second is about the two remainders matching, and either one implies the other.
What is −7 mod 12?
It is 5, because −7 and 5 differ by 12. Remainders are usually reported in the range 0 through n − 1, so you add copies of the modulus until you land inside it.
Can I add and multiply congruences?
Yes, and freely. If a ≡ b and c ≡ d with the same modulus, then a + c ≡ b + d and ac ≡ bd, which is what makes it possible to reduce huge numbers before calculating.
Why is 17 ≡ 5 (mod 12)?
Because 17 − 5 = 12, which 12 divides exactly once. On a clock, 17:00 and 5:00 point at the same place, which is exactly the situation the notation describes.