Free CAT library

Master Divisibility Rules & Digital Invariants

Master the mechanics behind divisibility rules, learn to construct rules for composite numbers, and leverage digital roots to rapidly verify arithmetic operations.

1. The Story & Mental Model

Think of divisibility rules not as arbitrary magic tricks, but as 'security checkpoints' at the border of Modulo Arithmetic. When a massive number like 45,89245,892 approaches the border of "Divisible by 9", the checkpoint doesn't inspect the whole number. It just asks the digits to weigh in: 4+5+8+9+2=284+5+8+9+2 = 28. Since 28 doesn't pass the border control for 9, the whole number is rejected.

Why does this work? Because our number system is base-10. Since 10≡1(mod9)10 \equiv 1 \pmod 9, any power of 10 behaves just like a 1 when dividing by 9. Therefore, 4×10004 \times 1000 leaves the same remainder as 4×14 \times 1, which is why we can just add the digits!

By understanding why the rules work, you can derive the rule for any number on the fly.

2. The CAT Question Blueprint

The examiner will rarely ask "Is 345 divisible by 3?" Instead, they will:

  • Leave one or two digits unknown (e.g., 4A5B74A5B7) and ask for the sum or maximum value of the unknowns for the number to be divisible by 72 (meaning it must pass both the 8 and 9 checkpoints).

  • Test rules for primes like 7, 11, and 13 simultaneously.

  • Ask for the remainder when a massive repetitive number (like 555... fifty times) is divided by 13 or 37.

3. Core Concepts, Formulae & Derivations

A. Power of 2 Checkpoints (2,4,8,162, 4, 8, 16)

Because 1010 is divisible by 22, 100100 is divisible by 44, and 10001000 by 88:

  • 2: Check the last 1 digit.

  • 4: Check the last 2 digits.

  • 8: Check the last 3 digits.

  • 16: Check the last 4 digits.

B. Power of 5 Checkpoints (5,25,1255, 25, 125)

Similar to powers of 2.

  • 5: Last digit must be 0 or 5.

  • 25: Last 2 digits must be 00, 25, 50, or 75.

  • 125: Last 3 digits must be divisible by 125.

C. The Summation Checkpoints (3,93, 9)

Because 10≡1(mod3)10 \equiv 1 \pmod 3 and 10≡1(mod9)10 \equiv 1 \pmod 9:

  • 3: Sum of digits must be divisible by 3.

  • 9: Sum of digits must be divisible by 9.

(The single-digit result of continuously summing digits is called the Digital Root. The digital root of a number is its remainder when divided by 9, with 9 replacing a remainder of 0).

D. The Alternating Checkpoint (1111)

Because 10≡−1(mod11)10 \equiv -1 \pmod{11}:

  • 11: The difference between the sum of digits at odd places and the sum of digits at even places must be 00 or a multiple of 1111.

E. The Block Checkpoints (7,11,137, 11, 13)

Because 1001=7×11×131001 = 7 \times 11 \times 13:

  • To test divisibility by 7, 11, or 13 for large numbers, break the number into blocks of 3 from right to left, and find the alternating sum/difference of the blocks. The result will have the same divisibility as the original number.

F. Composite Divisors (6,12,72,886, 12, 72, 88, etc.)

To test divisibility for a composite number NN, break NN into two or more co-prime factors.

  • 72: Must be divisible by 8 AND 9. (Notice we don't use 12 and 6, because they share a common factor of 6).

  • 88: Must be divisible by 8 AND 11.

4. Common Pitfalls & Speed Shortcuts

  • Pitfall: Breaking a composite divisor into non-coprime parts. E.g., testing for 24 by checking 4 and 6. A number like 12 passes for both 4 and 6, but is NOT divisible by 24! Always use co-primes: 24=8×324 = 8 \times 3.

  • Shortcut: The "Seed" method (Osculators) for primes like 7, 13, 17, 19. For 7: take the last digit, double it, and subtract from the rest of the number. Repeat until small. (For 13: multiply last digit by 4 and ADD).

Formulas

Divisibility by 8

N≡(Last 3 digits)(mod8)N \equiv (\text{Last 3 digits}) \pmod 8

If the hundreds digit is even, just check the last two digits for divisibility by 8. If odd, add 4 to the last two digits.
Divisibility by 11

∑Odd places−∑Even places=11k\sum \text{Odd places} - \sum \text{Even places} = 11k

Count places from right to left (or left to right, it yields the same absolute difference).
Composite Divisor N = a \times b

gcd⁡(a,b)=1\gcd(a, b) = 1

The factors used to check composite divisibility must be strictly co-prime.

Traps and tips

  • Always choose co-prime factors for composite divisibility rules. 36 is 4 and 9, not 6 and 6.
  • For divisibility by 8, if the hundreds digit is even, just check the last two digits!
  • Digital roots are invariant under multiplication: DigitalRoot(A x B) = DigitalRoot(DigitalRoot(A) x DigitalRoot(B)).

Solved examples

The Missing Digits of 72

A 7-digit number 8934A5B8934A5B is divisible by 72. Find the maximum possible value of A+BA + B.

Show solution

For a number to be divisible by 72, it must be divisible by its co-prime factors, 8 and 9.

Step 1: Divisibility by 8

The last three digits are A5BA5B. For this to be divisible by 8, A5BA5B must be a multiple of 8.

Since AA is in the hundreds place, let's use the shortcut: if AA is even, 5B5B must be divisible by 8. The only multiple of 8 in the 50s is 56. So B=6B=6 if AA is even.

If AA is odd, 5B+45B + 4 must be divisible by 8. 50+B+4=54+B50+B+4 = 54+B. Multiples of 8 in the 50s/60s are 56, 64. So 54+B=56  ⟹  B=254+B=56 \implies B=2. (Also 54+B=64  ⟹  B=1054+B=64 \implies B=10, impossible).

So we have two cases:

Case 1: B=6B=6, A∈{0,2,4,6,8}A \in \{0, 2, 4, 6, 8\}

Case 2: B=2B=2, A∈{1,3,5,7,9}A \in \{1, 3, 5, 7, 9\}

Step 2: Divisibility by 9

The sum of the digits must be a multiple of 9.

Sum =8+9+3+4+A+5+B=29+A+B= 8 + 9 + 3 + 4 + A + 5 + B = 29 + A + B.

Let's test Case 1 (B=6B=6): Sum =35+A= 35 + A. For this to be a multiple of 9, AA must be 1. But in Case 1, AA must be even. So this case fails.

Let's test Case 2 (B=2B=2): Sum =31+A= 31 + A. For this to be a multiple of 9, AA must be 5 (since 31+5=3631+5=36). Is 5 odd? Yes. This case works!

Therefore, A=5A = 5 and B=2B = 2.

The maximum (and only) value of A+B=5+2=7A + B = 5 + 2 = 7.

Takeaway: Always apply the localized rule (like 8, checking the end) before the global rule (like 9, checking the sum) to narrow down unknowns quickly.

The Alternating 11

If the 6-digit number x35624x35624 is divisible by 11, what is the value of the digit xx?

Show solution

The divisibility rule for 11 states that the difference between the sum of digits in odd positions and the sum of digits in even positions must be a multiple of 11.

Let's label the positions from right to left:

Position 1: 4

Position 2: 2

Position 3: 6

Position 4: 5

Position 5: 3

Position 6: xx

Sum of odd positions =4+6+3=13= 4 + 6 + 3 = 13.

Sum of even positions =2+5+x=7+x= 2 + 5 + x = 7 + x.

Difference =13−(7+x)=6−x= 13 - (7 + x) = 6 - x.

For the number to be divisible by 11, this difference must be 0,11,−110, 11, -11, etc.

Since xx is a single digit from 0 to 9, the only way 6−x6 - x can be a multiple of 11 is if it equals 0.

6−x=0  ⟹  x=66 - x = 0 \implies x = 6.

Takeaway: For the divisibility rule of 11, it doesn't matter if you go left-to-right or right-to-left, just ensure you alternate strictly.

The 1001 Block Check

Is the number 425,739 divisible by 7, 11, or 13?

Show solution

We use the block subtraction method because 7×11×13=10017 \times 11 \times 13 = 1001.

Split the number into blocks of 3 from right to left:

Block 1: 739

Block 2: 425

Take the alternating difference:

739−425=314739 - 425 = 314.

Now, test 314 for divisibility by 7, 11, and 13.

  • For 7: 314/7=44314 / 7 = 44 remainder 6. (Not divisible)

  • For 11: 3−1+4=63 - 1 + 4 = 6. (Not divisible)

  • For 13: 314/13=24314 / 13 = 24 remainder 2. (Not divisible)

The original number is not divisible by 7, 11, or 13.

Let's do a quick variant: what if the number was 425,432?

Difference = 432−425=7432 - 425 = 7.

7 is divisible by 7, but not 11 or 13. So 425,432 is a multiple of 7!

Takeaway: The 3-digit block difference method instantly checks divisibility for 7, 11, and 13 simultaneously.

The 99 Framework

A palindrome is a number that reads the same forwards and backwards. Prove that every 4-digit palindrome is divisible by 11.

Show solution

A 4-digit palindrome can be written in the form ABBAABBA, where AA and BB are digits.

Let's expand this using place value:

ABBA=1000A+100B+10B+AABBA = 1000A + 100B + 10B + A

=1001A+110B= 1001A + 110B

Notice that:

1001=11×911001 = 11 \times 91

110=11×10110 = 11 \times 10

So, ABBA=11(91A+10B)ABBA = 11(91A + 10B).

Since AA and BB are integers, the term (91A+10B)(91A + 10B) is an integer.

Therefore, ABBAABBA is always a multiple of 11.

Alternatively, using the rule of 11:

Odd positions sum: B+AB + A

Even positions sum: B+AB + A

Difference: (B+A)−(B+A)=0(B+A) - (B+A) = 0.

Since 0 is a multiple of 11, the number is divisible by 11.

Takeaway: Algebraic expansion of digits ( 1000A + 100B... ) often provides elegant proofs for divisibility rules and digit constraints.

Digital Root Verification

The product of 453453 and 789789 is claimed to be 357,419357,419. Use digital roots to quickly check if this multiplication could be correct.

Show solution

The digital root (sum of digits until a single digit) is invariant under multiplication.

Let's find the digital roots (DR) of the operands.

A=453A = 453.

Sum of digits =4+5+3=12= 4+5+3 = 12.

1+2=31+2 = 3.

So, DR(A)=3DR(A) = 3.

B=789B = 789.

Sum of digits =7+8+9=24= 7+8+9 = 24.

2+4=62+4 = 6.

So, DR(B)=6DR(B) = 6.

The digital root of the product should be the digital root of (3×6)(3 \times 6).

3×6=183 \times 6 = 18.

1+8=91+8 = 9 (which is equivalent to 0 in mod 9).

Now, let's check the claimed product C=357,419C = 357,419.

Sum of digits =3+5+7+4+1+9=29= 3+5+7+4+1+9 = 29.

2+9=112+9 = 11.

1+1=21+1 = 2.

So, DR(C)=2DR(C) = 2.

Since DR(A×B)=9DR(A \times B) = 9 but DR(C)=2DR(C) = 2, the claimed product is strictly INCORRECT.

Takeaway: The digital root of a product equals the digital root of the product of the digital roots of the operands. It is a blazing fast sanity check.

The Osculator (Seed) for Primes

Determine if 4,213 is divisible by 19 using the seed method.

Show solution

The seed (or osculator) for checking divisibility by 19 is +2+2.

Rule: Take the last digit, multiply by 2, and ADD it to the remaining truncated number.

Let's process 4,213:

  1. Last digit is 3. Truncated number is 421.

    New number =421+(3×2)=421+6=427= 421 + (3 \times 2) = 421 + 6 = 427.

  2. Next, process 427:

    Last digit is 7. Truncated number is 42.

    New number =42+(7×2)=42+14=56= 42 + (7 \times 2) = 42 + 14 = 56.

Is 56 divisible by 19?

19×3=5719 \times 3 = 57, not 56.

Since 56 is not a multiple of 19, the original number 4,213 is NOT divisible by 19.

(Note: How do we get the seed? We look for a multiple of 19 ending in 9. 19×1=1919 \times 1 = 19. Add 1 to get 20. Drop the zero to get 2. Since we added 1, the operation is ADD).

Takeaway: The seed method shrinks large numbers rapidly for prime divisibility checking, avoiding long division.

Practice questions

Question 1 · CAT Level

The eight-digit number N=6a54b3c2‾N = \overline{6a54b3c2} is divisible by 792792. What is the maximum possible value of the three-digit number 100a+10b+c100a + 10b + c?

  1. A

    889

  2. B

    925

  3. C

    961

  4. D

    982

Show answer and explanation

Answer: (C) 961

Since 792=8×9×11792 = 8 \times 9 \times 11 with factors pairwise co-prime, NN must satisfy all three divisibility tests.

For divisibility by 88, the last three digits 3c2‾\overline{3c2} must be a multiple of 88, yielding c∈{1,5,9}c \in \{1, 5, 9\}.

For divisibility by 99, the sum of digits 20+a+b+c≡0(mod9)  ⟹  a+b+c≡7(mod9)20 + a + b + c \equiv 0 \pmod 9 \implies a + b + c \equiv 7 \pmod 9.

For divisibility by 1111, alternating sum difference (a+9)−(b+c+11)=a−b−c−2≡0(mod11)(a + 9) - (b + c + 11) = a - b - c - 2 \equiv 0 \pmod{11}.

Testing c=9  ⟹  a=b=8c = 9 \implies a = b = 8, giving abc‾=889\overline{abc} = 889.

Testing c=5  ⟹  a=9,b=2c = 5 \implies a = 9, b = 2, giving abc‾=925\overline{abc} = 925.

Testing c=1  ⟹  a=9,b=6c = 1 \implies a = 9, b = 6, giving abc‾=961\overline{abc} = 961.

Hence, the maximum possible value of 100a+10b+c100a + 10b + c is 961961.

Question 2 · CAT Level

How many six-digit palindromes of the form abccba‾\overline{abccba} (where a≠0a \ne 0) are divisible by 77?

  1. A

    120

  2. B

    128

  3. C

    140

  4. D

    144

Show answer and explanation

Answer: (C) 140

By the 10011001-block rule, any integer N≡(sum of odd 3-digit blocks)−(sum of even 3-digit blocks)(mod1001)N \equiv (\text{sum of odd 3-digit blocks}) - (\text{sum of even 3-digit blocks}) \pmod{1001}.

Partitioning abccba‾\overline{abccba} gives blocks cba‾\overline{cba} and abc‾\overline{abc}, so abccba‾≡cba‾−abc‾=99(c−a)(mod1001)\overline{abccba} \equiv \overline{cba} - \overline{abc} = 99(c - a) \pmod{1001}.

Since 1001=7×11×131001 = 7 \times 11 \times 13 and 99≡1(mod7)99 \equiv 1 \pmod 7, we have abccba‾≡c−a(mod7)\overline{abccba} \equiv c - a \pmod 7.

Therefore, 7∣abccba‾  ⟺  c≡a(mod7)7 \mid \overline{abccba} \iff c \equiv a \pmod 7.

Since a∈{1,2,…,9}a \in \{1, 2, \dots, 9\} and c∈{0,1,…,9}c \in \{0, 1, \dots, 9\}:

Case 1: c=ac = a yields 99 pairs; Case 2: c−a=7c - a = 7 yields 22 pairs ((1,8),(2,9)(1, 8), (2, 9)); Case 3: a−c=7a - c = 7 yields 33 pairs ((7,0),(8,1),(9,2)(7, 0), (8, 1), (9, 2)).

This gives 9+2+3=149 + 2 + 3 = 14 valid pairs (a,c)(a, c). Since the middle digit b∈{0,1,…,9}b \in \{0, 1, \dots, 9\} is unconstrained (1010 choices), total count is 14×10=14014 \times 10 = 140.

Question 3 · CAT Level

For a positive integer nn, let S(n)S(n) denote the sum of the decimal digits of nn. How many positive integers AA satisfy the equation:

A+S(A)+S(S(A))=2025A + S(A) + S(S(A)) = 2025

  1. A

    2

  2. B

    3

  3. C

    4

  4. D

    5

Show answer and explanation

Answer: (C) 4

Since n≡S(n)(mod9)n \equiv S(n) \pmod 9, we have A+S(A)+S(S(A))≡3A(mod9)A + S(A) + S(S(A)) \equiv 3A \pmod 9.

Because 2025≡0(mod9)2025 \equiv 0 \pmod 9, we require 3A≡0(mod9)3A \equiv 0 \pmod 9, so A≡0,3,6(mod9)A \equiv 0, 3, 6 \pmod 9.

Since AA is a 4-digit number near 20002000, S(A)≤28S(A) \le 28 and S(S(A))≤10S(S(A)) \le 10, establishing 1987≤A≤20251987 \le A \le 2025.

Testing multiples of 33 in this interval yields solutions:

A=1989A = 1989 (1989+27+9=20251989+27+9=2025), A=1995A = 1995 (1995+24+6=20251995+24+6=2025),

A=2007A = 2007 (2007+9+9=20252007+9+9=2025), and A=2013A = 2013 (2013+6+6=20252013+6+6=2025).

No other values in the range satisfy the equation, giving exactly 44 solutions.

Question 4 · CAT Level

A large integer NN is formed by writing in order the positive integers from 11 to 4545:

N=123456789101112…4445N = 123456789101112\dots4445

What is the remainder when NN is divided by 9999?

  1. A

    18

  2. B

    27

  3. C

    36

  4. D

    45

Show answer and explanation

Answer: (B) 27

Because 100≡1(mod99)100 \equiv 1 \pmod{99}, the remainder modulo 9999 equals the sum of two-digit blocks grouped from right to left.

NN consists of the 3636 two-digit integers from 1010 to 4545 (7272 digits) preceded by the 99 single digits 123456789123456789.

Grouping from right: the first 3636 blocks are the integers 45,44,…,1045, 44, \dots, 10; the remaining left digits group into 89,67,45,2389, 67, 45, 23, and 11.

The sum of the two-digit numbers is ∑k=1045k=362(10+45)=18×55=990\sum_{k=10}^{45} k = \frac{36}{2}(10 + 45) = 18 \times 55 = 990, which is 0(mod99)0 \pmod{99}.

The sum of the remaining five blocks is 1+23+45+67+89=2251 + 23 + 45 + 67 + 89 = 225.

Thus N≡0+225≡225−2(99)=27(mod99)N \equiv 0 + 225 \equiv 225 - 2(99) = 27 \pmod{99}.

Question 5 · CAT Level

The five-digit number N=37ab4‾N = \overline{37ab4} is divisible by 1717. If the two-digit number ab‾\overline{ab} is also divisible by 77, what is the value of a+ba + b?

  1. A

    10

  2. B

    12

  3. C

    14

  4. D

    16

Show answer and explanation

Answer: (C) 14

Express NN as 37004+100a+10b=37004+10(ab‾)37004 + 100a + 10b = 37004 + 10(\overline{ab}).

Dividing 3700437004 by 1717: 37004=17×2176+1237004 = 17 \times 2176 + 12, so 37004≡12(mod17)37004 \equiv 12 \pmod{17}.

For 17∣N17 \mid N, we require 12+10(ab‾)≡0(mod17)  ⟹  10(ab‾)≡5(mod17)12 + 10(\overline{ab}) \equiv 0 \pmod{17} \implies 10(\overline{ab}) \equiv 5 \pmod{17}.

Multiplying by 1212 (since 10×12=120≡1(mod17)10 \times 12 = 120 \equiv 1 \pmod{17}) yields ab‾≡5×12=60≡9(mod17)\overline{ab} \equiv 5 \times 12 = 60 \equiv 9 \pmod{17}.

Two-digit multiples of 1717 plus 99 are ab‾∈{9,26,43,60,77,94}\overline{ab} \in \{9, 26, 43, 60, 77, 94\} (with leading zero disallowed if ab‾\overline{ab} is two-digit, though 0909 is also not div by 77).

Among these, testing divisibility by 77: only 7777 is divisible by 77 (77=7×1177 = 7 \times 11).

Thus ab‾=77\overline{ab} = 77, giving a=7a = 7 and b=7b = 7, so a+b=14a + b = 14.

Study this concept with interactive practice in PrepSoc.

Open the concept library