Recurrences and arithmetic · Definition
Modular congruence
Before you start you need to know
It lets you work with remainders as if they were numbers, which is why it appears in clocks, calendars, cryptography and divisibility rules.
Definition
Two integers \(a\) and \(b\) are congruent modulo a positive integer \(m\) if \(m\) divides their difference; equivalently, they leave the same remainder when divided by \(m\).
The idea is that of a clock: at 15:00 and at 3:00 the hand is in the same place, because \(15\equiv3\pmod{12}\). Every integer is congruent modulo \(m\) to exactly one remainder between 0 and \(m-1\), written \(a\bmod m\). That is why \(17\equiv5\pmod6\) and \(-7\equiv3\pmod5\): the remainder is never negative. Congruence is reflexive, symmetric and transitive, so it splits the integers into \(m\) equivalence classes.
What makes it useful is that congruence respects operations: if \(a\equiv b\) and \(c\equiv d\pmod m\), then \(a+c\equiv b+d\), \(a-c\equiv b-d\) and \(ac\equiv bd\). Numbers can therefore be reduced before operating: \(2^{10}\bmod7\) follows from \(2^3\equiv1\), without computing 1024. This finds last digits, proves that a square leaves remainder 0 or 1 modulo 4, and justifies the divisibility rules for 3 and 9.
Division is the exception: from \(ac\equiv bc\) one cannot conclude \(a\equiv b\) (modulo 6, \(4\cdot1\equiv4\cdot4\)). You may cancel \(c\) only when \(\gcd(c,m)=1\), and then \(c\) has an inverse modulo \(m\), found with the extended Euclidean algorithm. A common mistake is to treat \(\equiv\) as equality: \(a\equiv b\pmod m\) states a property of the difference, not that the numbers are equal.
Think about it
Is it true that \(38\equiv2\pmod9\)?
Yes: \(38-2=36\) is a multiple of 9. Equivalently, 38 and 2 both leave remainder 2 when divided by 9, since \(38=4\cdot9+2\).
Find the remainder of \(10^{100}\) when divided by 9.
Since \(10\equiv1\pmod9\), \(10^{100}\equiv1^{100}=1\pmod9\). The remainder is 1.
Exercises 10
- Which of the following congruences is true?
- Compute \(53\bmod8\).
- What is \(-7\bmod5\)?
- Compute \((17+25)\bmod6\).
- Compute \(3^4\bmod5\).
- Compute \(2^{10}\bmod7\).
- Solve \(3x\equiv4\pmod7\) with \(0\le x\le6\).
- What is the last digit of \(7^{2026}\)?
- If \(a\equiv b\) and \(c\equiv d\pmod m\), which statement does NOT always hold?
- Which remainders can a perfect square leave when divided by 4?
References
- Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §4.1
- Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §8.4