Modular arithmetic collapses huge numbers into small, manageable remainders. The fundamental distributive property is \((a \cdot b) \bmod n = ((a \bmod n)(b \bmod n)) \bmod n\), which lets you square, multiply, and raise without expanding the original expression. If \(x\) leaves remainder 3 when divided by 7, then \(x^2\) leaves the same remainder as \(3^2 = 9\), which is 2 modulo 7. A useful fact about squares is that they are always congruent to 0 or 1 modulo 4, which is why 1234567 (whose value mod 4 is 3) cannot possibly be a perfect square.
A particularly powerful congruence is that any positive integer is congruent to the sum of its digits modulo 9. This single rule explains why the digit-sum test detects divisibility by 3 and 9. It also unlocks otherwise impossible digit-sum calculations: to find \(7^{50}\) modulo 9, note that \(7^3 = 343 \equiv 1 \pmod{9}\). Since 50 mod 3 = 2, \(7^{50} \equiv 7^2 = 49 \equiv 4 \pmod{9}\). The same logic gives 2¹⁰⁰ mod 9: since \(2^3 \equiv 8 \equiv -1\) and \(2^{99} \equiv (-1)^{33} = -1\), we get \(2^{100} \equiv -2 \equiv 7 \pmod{9}\), so the remainder is 7.
Last-digit problems are a special case of arithmetic modulo 10. Powers of 5 always end in 5 for any positive exponent, since 5¹ = 5, 5² = 25, 5³ = 125, and so on. Powers of 7 cycle through 7, 9, 3, 1 with period 4, so 7²⁵ ends in 7 because 25 mod 4 = 1. Powers of 2 cycle 2, 4, 8, 6 with period 4, so 2⁵⁰ ends in 4 since 50 mod 4 = 2. Powers of 3 (and 13, since 13 ends in 3) cycle 3, 9, 7, 1 with period 4, so 3¹⁰⁰ ends in 1 because 100 mod 4 = 0, and 13⁷⁹ ends in 7 because 79 mod 4 = 3. The pattern extends to two-digit residues for harder problems: since 37² ≡ 69 (mod 100) and 37⁴ ≡ 61 (mod 100), and 61⁵ ≡ 1 (mod 100), we get 37⁴⁰ = (37⁴)¹⁰ ≡ 1¹⁰ = 1 (mod 100), so the last two digits of 37⁴⁰ are 01. Other quick remainders: \(5^{23} \bmod 13\) equals 5 because \(5^2 \equiv -1\) and \(5^{22} \equiv 1\); \(7^{600} \bmod 5\) equals 1 because 7 ≡ 2, 2⁴ ≡ 1, and 600 mod 4 = 0; and \(3^{50} \bmod 7\) equals 2 because \(3^6 \equiv 1\) and 50 mod 6 = 2 gives \(3^2 = 9 \equiv 2\).