Divisibility Rules Practice & Multi-Tester

In elementary and higher arithmetic, divisibility is a fundamental algebraic relationship between two integers. Formally, an integer $b$ is said to be divisible by a non-zero integer $a$ (written in number theory as $a \mid b$, pronounced "$a$ divides $b$") if and only if there exists some integer $k \in \mathbb{Z}$ such that:

When dividing $b$ by $a$ via the Division Algorithm, the remainder $r$ satisfies $b = q \cdot a + r$, with $0 \le r < |a|$. Divisibility holds when the remainder $r = 0$.

Divisibility shortcuts are derived from modular arithmetic, introduced by Carl Friedrich Gauss in his 1801 treatise Disquisitiones Arithmeticae. Two numbers are congruent modulo $m$ (written $x \equiv y \pmod m$) if their difference $(x - y)$ is an exact integer multiple of $m$. Every integer in base 10 can be expanded as a polynomial in powers of 10:

By evaluating the polynomial coefficients $10^k \pmod m$, mathematicians derive elegant tests that verify divisibility without computing full long division quotients.

Every standard divisibility rule is a direct theorem of modular congruence:

1. Proof of the Digit Sum Rule for 3 and 9

Notice that $10 = 9 + 1 \equiv 1 \pmod 9$ and $10 \equiv 1 \pmod 3$. By the properties of modular multiplication, any power of 10 satisfies $10^k \equiv 1^k \equiv 1 \pmod 9$ (and $\pmod 3$). Substituting this into the polynomial expansion of $N$:

Thus, $N$ leaves the exact same remainder when divided by 9 as the sum of its individual digits. If the digit sum is a multiple of 9 (or 3), $N$ is divisible by 9 (or 3).

2. Proof of the Last Digits Rule for Powers of 2 and 5 (2, 4, 8, 5, 10)

Because the base $10 = 2 \times 5$, higher powers of 10 contain factors of $2^k$ and $5^k$:

• $10 \equiv 0 \pmod 2$ and $10 \equiv 0 \pmod 5$: All terms above the units place are multiples of 2 and 5. Hence, divisibility depends strictly on the final single digit $d_0$.
• $100 = 10^2 = 4 \times 25 \equiv 0 \pmod 4$: All terms above the tens place are multiples of 4. Hence, divisibility by 4 depends strictly on the last two digits ($10 d_1 + d_0$).
• $1,000 = 10^3 = 8 \times 125 \equiv 0 \pmod 8$: All terms above hundreds are multiples of 8. Divisibility by 8 depends strictly on the last three digits.

3. Proof of the Alternating Sum Rule for 11

Observe that $10 = 11 - 1 \equiv -1 \pmod{11}$. Therefore, powers of 10 alternate in sign:

Substituting into the decimal expansion yields:

If the alternating sum $(d_0 + d_2 + d_4 + \dots) - (d_1 + d_3 + d_5 + \dots)$ is 0 or a multiple of 11, then $N$ is divisible by 11.

4. Proof of the Truncation Test for 7

Let a number be written as $N = 10a + b$, where $b$ is the units digit and $a$ is the truncated leading number. We seek to eliminate the factor of 10 modulo 7. Since $\gcd(10, 7) = 1$, the modular inverse of 10 mod 7 is $-2$ (because $10 \times (-2) = -20 \equiv 1 \pmod 7$). Multiplying $N$ by $-2$:

This proves that $10a + b$ is divisible by 7 if and only if $a - 2b$ (the remaining number minus twice the units digit) is divisible by 7.

Divisibility and modular arithmetic rules form the foundation of global data verification protocols:

• Credit Card Validation (The Luhn Algorithm): Standard payment card numbers (Visa, Mastercard, Amex) encode a check digit validated using a modified modulo-10 divisibility algorithm (ISO/IEC 7812-1). Doubling every second digit from right to left and summing the digits must produce a total divisible by 10, instantly blocking accidental typos before transmitting transactions.
• Book Publishing & ISBN-10 Checksums: International Standard Book Numbers (ISBN-10) employ a weighted modulo-11 divisibility rule: $\sum_{i=1}^{10} (11 - i) \cdot x_i \equiv 0 \pmod{11}$. Because 11 is prime, this rule provides mathematical protection against both single-digit typing errors and two-digit transposition slips. If the check digit equals 10, the letter "X" is inscribed.
• Computer Systems & Fast Bitwise Arithmetic: In low-level software engineering, checking divisibility by powers of 2 ($2, 4, 8, 16, 32$) avoids expensive CPU division cycles. Compilers replace $x \pmod{2^k} == 0$ with ultra-fast bitwise masks: (x & ((1 << k) - 1)) == 0.

Avoid these common fallacies when applying divisibility shortcuts:

• The Non-Coprime Factor Trap: You can only test a composite divisor by checking its factors if those factors are coprime ($\gcd(a, b) = 1$). For example, testing divisibility by 12 using 2 and 6 is a fallacy: the number 18 is divisible by 2 and divisible by 6, but $18 \div 12 = 1.5$ (not divisible!). For 12, one must test 3 and 4 ($\gcd(3, 4) = 1$). Similarly, for 24, test 3 and 8 (not 4 and 6).
• The Zero Divisibility Fallacy: Students frequently ask if 0 is divisible by 7. By definition, $0 = 0 \times 7$, so 0 is divisible by every non-zero integer. However, division by zero ($7 \div 0$) is mathematically undefined.
• Assuming the Digit Sum Rule Works for All Numbers: The digit sum rule works only for 3 and 9 in base 10 because $10 \equiv 1 \pmod 3$ and $10 \equiv 1 \pmod 9$. Summing digits does not test divisibility for 4, 6, 7, or 8.