Number System II: Remainders, Unit Digits and Bases formulas
At a glance
N = n × q + r, 0 ≤ r < n; r ⇔ r − n (a ± b), (a × b): work with the remainders, reduce again unit digits: cycles of 1, 2 or 4 → power mod 4 (0 → 4th) …a1^n ends in [a × n]1; 76, 25 stay; 24^even → 76 2^10 → 24, 2^20 → 76 (last two digits) Fermat a^(p−1) → 1; Euler a^φ(n) → 1 (no common factor) Wilson (p − 1)! → p − 1 (p prime) hunt for a^k → ±1; p(x) ÷ (x − a) leaves p(a) base b digits = remainders of ÷ b, read bottom up
Remainders on a clock
dividend = divisor × quotient + remainder 0 ≤ remainder < divisor
Remainders of sums and products
(a + b) mod n = (ra + rb) mod n (a × b) mod n = (ra × rb) mod n
Shortcut: Reduce as you go. 5 × 7 = 35 → 11 (mod 12), then 11 × 9 = 99 → 3. The numbers never get big.
Negative remainders
remainder r ⇔ negative remainder r − n a negative final answer: add n back
Unit digits run in cycles
| Last digit of a | a¹ | a² | a³ | a⁴ | Cycle length |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 8 | 6 | 4 |
| 3 | 3 | 9 | 7 | 1 | 4 |
| 4 | 4 | 6 | 4 | 6 | 2 |
| 5 | 5 | 5 | 5 | 5 | 1 |
| 6 | 6 | 6 | 6 | 6 | 1 |
| 7 | 7 | 9 | 3 | 1 | 4 |
| 8 | 8 | 4 | 2 | 6 | 4 |
| 9 | 9 | 1 | 9 | 1 | 2 |
Every cycle fits in 4, so aⁿ ends like a^r with r = n mod 4, using r = 4 when n is a multiple of 4.
Shortcut: Find the power mod 4. A remainder of 0 means the 4th spot of the cycle, not the first: 2^20 ends in 6, the same as 2^4.
Last two digits
(…a1)^n ends in [unit digit of a × n] then 1 e.g. 41^7: 4 × 7 = 28 → 81 …9: 9^(2k) = 81^k …3: 3^4 = 81 …7: 7^4 = 2401 → ends in 01 (…76)^n → 76 (…25)^n → 25 5^n → 25 for n ≥ 2 24^odd → 24 24^even → 76 2^10 = 1024: 2^(10k) ends in 24 for odd k, 76 for even k
Shortcut: 2^10 ends in 24, so 2^20 ends in 76, and 76 times anything ending in 76 stays 76. For 2^43: 2^40 ends in 76, and 76 × 2^3 = 608, so 2^43 ends in 08.
Fermat, Euler and Wilson: when a power becomes 1
| Theorem | Statement | Needs | Example |
|---|---|---|---|
| Fermat | a^(p − 1) mod p = 1 | p prime, a not a multiple of p | 2^12 mod 13 = 1, so 2^100 mod 13 = 2^4 mod 13 = 3 |
| Euler | a^φ(n) mod n = 1 | a and n share no factor | φ(21) = 12, so 5^48 mod 21 = 1 |
| Wilson | (p − 1)! mod p = p − 1 (that is, −1) | p prime | 6! = 720 = 7 × 102 + 6 |
φ(n) = n × (1 − 1/p₁)(1 − 1/p₂)… e.g. φ(21) = 21 × 2/3 × 6/7 = 12 φ(p) = p − 1 for a prime p
Shortcut: (p − 1)! leaves −1 by a prime p. Peel off the last factor, which is also −1, to get (p − 2)! → 1. So 28! by 29 leaves 28, and 27! by 29 leaves 1.
Remainders of large powers: hunt for ±1
(n + 1)^k mod n = 1 (n − 1)^k mod n = 1 if k is even, n − 1 if k is odd a^k − b^k is always divisible by a − b a^k + b^k is divisible by a + b when k is odd; a^k − b^k when k is even remainder theorem: p(x) ÷ (x − a) leaves p(a)
Shortcut: Dividing a polynomial p(x) by x − a leaves p(a). So x³ + 2x − 5 by x − 2 leaves 8 + 4 − 5 = 7, and by x + 1 it leaves −1 − 2 − 5 = −8. Numbers work the same way: 5 is −1 on the 6-clock, so 5^99 by 6 leaves (−1)^99 = −1, which is 5.
Shortcut: 7^84 mod 342: 342 = 7³ − 1, so 7³ leaves remainder 1, and 7^84 = (7³)^28 leaves 1. Always check whether the divisor is a power ± 1.
Number bases
(d₂d₁d₀)_b = d₂ × b² + d₁ × b + d₀ last digit in base b = N mod b
Formulas stick when you use them
The Number System II: Remainders, Unit Digits and Bases lesson has worked problems and quick checks for every formula here. Free to start.
Start free