7. Remainder-Based Divisibility Shortcuts
Free study material · concepts, shortcuts & solved questions
Core idea: When dividing a large expression (especially a power) by a small number, don’t compute the full value — track only the remainder at each multiplication step, since (a × b) mod m = [(a mod m)×(b mod m)] mod m.
Example 1: Find the remainder when 2^(96) is divided by 7. Powers of 2 mod 7 cycle: 2^1=2, 2^2=4, 2^3=1 (mod 7) (cycle length 3). 96 ÷ 3 = 32 exactly (no remainder in the exponent), so 2^(96) = (23)(32) ≡ 1^(32) = 1 (mod 7). Remainder = 1.
Example 2: Find the remainder when 7^(84) is divided by 5. 7 ≡ 2 5. Powers of 2 mod 5 cycle: 2,4,3,1 (cycle length 4). 84 ÷ 4 = 21 exactly → 2^(84) ≡ 2^4 ≡ 1 5 (since exponent is an exact multiple of the cycle length, remainder is same as the last term of one full cycle, which is 1). Remainder = 1.
Example 3: Find the remainder when 71,364 is divided by 9 using the digit-sum shortcut. Digit sum =7+1+3+6+4=21. 21 ÷ 9 leaves remainder 3. Remainder = 3 (this works because 10≡19, so the number and its digit sum always leave the same remainder mod 9 — extremely fast for divisibility-by-9 remainder questions, and similarly digit sum mod 3 for divisor 3).
Example 4 (harder cycle length): Find the remainder when 3^(100) is divided by 5. Powers of 3 mod 5 cycle: 3^1=3, 3^2=4, 3^3=2, 3^4=1 5 (cycle length 4). 100 ÷ 4 = 25 exactly → 3(100)=(34)(25)≡1(25)=15. Remainder = 1.
Example 5 (edge case — the base itself shares a factor with the modulus): Find the remainder when 6^(75) is divided by 8. Here (6,8)=2≠1, so the “cyclicity” method used above (which relies on modular inverses) needs care. Direct computation of small powers: 6^1=6, 6^2=36≡48, 6^3=216≡08 (since 216=8×27). Once a power of 6 hits remainder 0 mod 8, every higher power also gives remainder 0 (because 0×6≡0 forever). Since 75≥3, 6^(75)≡08, i.e., remainder = 0. This is an important caution: the neat “cycle mod m” shortcut works cleanly only when the base and modulus are co-prime; otherwise, check the first few powers directly — the remainder often collapses to 0 well before the target exponent.