\(\newcommand{\lcm}{\mbox{lcm}}\) \(\newcommand{\N}{\mathbb{N}}\) \(\newcommand{\Z}{\mathbb{Z}}\) \(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\C}{\mathbb{C}}\) \(\newcommand{\Q}{\mathbb{Q}}\)
View on GitHub

Simplemath

A mathematical exploration
Download this project as a .zip file Download this project as a tar.gz file

Divisibility rules

A natural number $m$ is divisible by $2$ iff it ends in $0$, $2$, $4$, $6$ or $8$ when written in decimal. A number $m$ that ends in the decimal digit $k$ is of the form $m \equiv k \pmod{10}$. By a previous theorem $m \equiv k \pmod{2}$. Thus $m$ is even iff $k \equiv 0 \pmod{2}$. The possibilities for $k$ are therefore precisely the ones given. A natural number $m$ is divisible by $5$ iff it ends in $0$ or $5$ when written in decimal. If $k$ is the last digit, $m \equiv k \pmod{10}$. By a previous theorem $m \equiv k \pmod{5}$. Thus the possibilities for $k$ are $0$ or $5$. A natural number $m$ is divisible by $10$ iff it ends in $0$ when written in decimal. A natural number $m$ is divisible by $3$ iff the sum of its decimal digits is divisible by $3$. A digit $k$ represents the value $k\times 10^n$ for some $n \geq 0$, depending on what place it is in. As $10 \equiv 1 \pmod{3}$, we have that $k\times 10^n \equiv k \pmod{3}$. Thus a number is congruent to the sum of its digits modulo $3$. A natural number $m$ is divisible by $9$ iff the sum of its decimal digits is divisible by $9$. A natural number $m$ is divisible by $4$ iff its final two decimal digits give a number divisible by $4$. As $100$ is divisible by $4$, only the last two digits are relevant. A natural number $m = 10n + k$ is divisible by $7$ iff $n - 2k$ is divisible by $7$. To test division of a number by $7$, let $k$ be the final digit and $n$ the number formed by the remaining digits. Repeatedly apply the rule until a value between $-18$ and $0$ (inclusive) is obtained. If the remaining number is $-14$, $-7$ or $0$, the original number was divisible by $7$. If $10n + k$ is divisible by $7$ then so is $-2(10n + k) = -20n - 2k$. But $-20n - 2k \equiv n - 2k \pmod{7}$.

If $m$ is positive, $n - 2k < 10n + k$. Thus, repeated application of the rule reduces the number whilst it remains positive. On the first occasion that that the number becomes nonpositive, as $k$ can be at most $9$, $n - 2k \geq -18$. Thus the final value must lie between $-18$ and $0$ inclusive. The only values in this range that are divisible by $7$ are those given. To test whether a number is divisible by $8$, if the hundreds digit is even examine the number formed by the final two digits for divisibility by $8$. Otherwise, add $4$ to the number formed by the last two digits and examine for divisibility by $8$. As $1000$ is divisible by $8$, only the final three digits count. As $200$ is divisible by $8$ an even hundreds digit does not contribute. Otherwise, an odd hundreds digit contributes $100 \equiv 4 \pmod{8}$. A number of the form $m = 100n + 10k_1 + k_2$ is divisible by $11$ iff $n - k_1 + k_2$ is. To test whether a number is divisible by $11$ test the alternating sum of its digits by divisibility by $11$. We have that $100n + 10k_1 + k_2 \equiv n - k_1 + k_2 \pmod{11}$. If $k_1, k_2$ are the final two digits of a number, repeated application of the rule computes the alternating sum of the digits of a number (the leading digit may be zero). Suppose that $d \equiv 1, 3, 7, 9 \pmod{10}$. Let $k = 9, 3, 7, 1$ respectively. Let $m = (kd + 1)/10$. A number $n = 10a + b$ is divisible by $d$ iff $a + mb$ is. In each case we have that $kd \equiv 9 \pmod{10}$. Thus $kd + 1$ is divisible by $10$ and $m$ is an integer.

If $n$ is divisible by $d$ then so is $nm = akd + a + mb$. This implies that $a + mb$ is.

The converse holds by reversing the argument if we can show that $m$ and $d$ are coprime. But if $m$ and $d$ share a factor bigger than $1$, so do $10m$ and $d$, i.e. $\gcd(kd + 1, d) \neq 1$. As this is not possible, we must have that $m$ and $d$ are coprime. (Loir) Let $p < 100$ be prime and coprime to $10$. Suppose that $mp = 100k + 1$ for some $m$. Then $A = 100a + r$ is divisible by $p$ if $a - rk$ is. We see that $rmp = 100rk + r$. This is a multiple of $p$. Thus if $A$ is a multiple of $p$ so is $A - rmp = 100(a - rk)$. As $\gcd(10, p) = 1$ we have that $A$ is divisible by $p$ iff $a - rk$ is. (Plakhowo) Let $m$ be coprime to $10$. Let $A = a_0 + 10a_1 + 100a_2 + \cdots + 10^na_n$. Let $10d = mx + 1$ for some $x$. Then $A$ is divisible by $m$ if $A' = a_0d + (a_1 + 10a_2 + \cdots 10^{n-1}a_n)$ is. Multiplying $10d = mx + 1$ through by $a_0$ we have that $10a_0d \equiv a_0 \pmod{m}$. Thus if $A$ is divisible by $m$ so is $10a_0d + 10a_1 + 100a_2 + \cdots + 10^na_n = 10A'$. As $\gcd(m, 10) = 1$, $A$ is divisible by $m$ if $A'$ is. (Pascal) If $1 \equiv m_0 \pmod{d}$, $10 \equiv m_1 \pmod{d}$, $100 \equiv m_2 \pmod{d}$, $\ldots$, then $A = a_0 + 10a_1 + 100a_2 + \cdots + 10^ka_k$ is divisible by $d$ if $m_0a_0 + m_1a_1 + \cdots + m_ka_k$ is. We have that $A \equiv a_0m_0 + a_1m_1 + \cdots a_km_k \pmod{d}$. Then $A$ is divisible by $d$ iff $A \equiv 0 \pmod{d}$, which gives the required result. (D'Alombert) If $A = 10^na_n + 10^{n - 1}a_{n - 1} + \cdots + a_0$ is divisible by $10 - b$ then so is $B = b^na_n + b^{n - 1}a_{n - 1} + \cdots + a_0$. Consider $f(x) = a_nx^n + a_{n - 1}x^{n - 1} + \cdots + a_0$. We have that $A = f(10)$ and $B = f(b)$. But $f(10) - f(b)$ is divisible by $10 - b$ as $a_i(10^i - b^i) = a_i(10 - b)(10^{i - 1} + 10^{i - 2}b + \cdots + b^{i - 1})$ is divisible by $10 - b$ for all $i$.

Therefore, if $f(10)$ is divisible by $10 - b$, so is $f(b)$. (D'Alombert) If $A = 10^na_n + 10^{n - 1}a_{n - 1} + \cdots + a_0$ is divisible by $10 + b$ then so is $B = (-b)^na_n + (-b)^{n - 1}a_{n - 1} + \cdots + a_0$. With $f(x)$ defined as in the previous theorem, we have that $A = f(10)$ and $B = f(-b)$. By the same argument as the previous theorem we have that $A - B$ is divisible by $10 - (-b) = 10 + b$. Thus is $A$ is divisible by $10 + b$, so is $B$. (Gergonne) Let $A = a_0 + a_110^m + \cdots + a_n10^{mn}$ with $0 \leq a_i < 10^m$. If $d$ is any divisor of $10^m - 1$ then $A \equiv a_0 + a_1 + \cdots + a_n \pmod{d}$. We have that $10^m \equiv 1 \pmod{d}$. Thus $a_i10^{mi} \equiv a_i \pmod{d}$. Thus $A \equiv a_0 + a_1 + \cdots + a_n \pmod{d}$. (Gergonne) Let $A = a_0 + a_110^m + \cdots + a_n10^{mn}$ with $0 \leq a_i < 10^m$. If $d$ is any divisor of $10^m + 1$ then $A \equiv a_0 - a_1 + \cdots + (-1)^na_n \pmod{d}$. We have that $10^m \equiv -1 \pmod{d}$. Thus $a_i10^{mi} \equiv (-1)^ma_i \pmod{d}$. Thus $A \equiv a_0 - a_1 + \cdots + (-1)^na_n \pmod{d}$. Let $A = a_0 + 10^ma_1$ with $0 \leq a_i < 10^m$. To find the quotient $Q$ and remainder $R$ of $A$ by $d = 10^m - 1$ set $Q = a_1$ and set $R = a_0 + a_1$. If $R \geq d$ increase $Q$ by $1$ and decrease $R$ by $d$ and repeat if necessary. Upon setting $Q = a_1$ and $R = a_0 + a_1$ we have $dQ + R = 10^ma_1 - a_1 + a_0 + a_1 = A$. At this point $0 \leq R \leq 2\times(10^m - 1) = 2d$.

If $R \geq d$, let $Q' = Q + 1$ and $R' = R - d$. Then $dQ' + R' = dQ + d + R - d = A$. However, now $0 \leq R' \leq d$. Replace $Q$ by $Q'$ and $R$ by $R'$.

Repeating the last step if necessary finally yields $0 \leq R < d$. Let $A = a_0 + 10^ma_1 + \cdots + 10^{mn}a_n$. Suppose $A$ is an exact multiple of a divisor $d$ of $10^m - 1$. We can compute the quotient $Q$ of $A$ by $d$ with only a single division of an $m$ digit number by $d$ (assuming we know $(10^m - 1)/d$ in advance). Use the previous theorem repeatedly to compute the quotient $Q$ and remainder $R$ of $A$ by $10^m - 1$. Let $c = (10^m - 1)/d$. We have that $A = Q(10^m - 1) + R$. Dividing through by $d$ we have $A/d = Q(10^m - 1)/d + R/d = Qc + R/d$.

As we computed $Q$ without divisions, only the division $R/d$ remains to compute the quotient $A/d$. Let $A = a_0 + 10^ma_1$ with $0 \leq a_i < 10^m$. To find the quotient $Q$ and remainder $R$ of $A$ by $d = 10^m + 1$ set $Q = a_1$ and set $R = a_0 - a_1$. If $R < 0$ decrease $Q$ by $1$ and increase $R$ by $d$. Upon setting $Q = a_1$ and $R = a_0 - a_1$ we have $dQ + R = 10^ma_1 + a_1 + a_0 - a_1 = A$. At this point $-d < R < d$.

If $R < 0$, let $Q' = Q - 1$ and $R' = R + d$. Then $dQ' + R' = dQ - d + R + d = A$. However, now $0 \leq R' < d$. Replace $Q$ by $Q'$ and $R$ by $R'$. Let $A = a_0 + 10^ma_1 + \cdots + 10^{mn}a_n$. Suppose $A$ is an exact multiple of a divisor $d$ of $10^m + 1$. We can compute the quotient $Q$ of $A$ by $d$ with only a single division of an $m + 1$ digit number by $d$ (assuming we know $(10^m + 1)/d$ in advance). Use the previous theorem repeatedly to compute the quotient $Q$ and remainder $R$ of $A$ by $10^m + 1$. Let $c = (10^m + 1)/d$. We have that $A = Q(10^m + 1) + R$. Dividing through by $d$ we have $A/d = Q(10^m + 1)/d + R/d = Qc + R/d$.

As we computed $Q$ without divisions, only the division $R/d$ remains to compute the quotient $A/d$. (Malengreau) Let $d$ be coprime with $10$. Suppose $c = (10^r - 1)/9$ is divisible by $d$. Let $A = a_0 + a_110^r + a_210^{2r} + \cdots + a_n10^{nr}$. Let $a_i'$ be the remainder on division of $a_i$ by $c$. Then $A$ is divisible by $d$ if $a_0' + a_1' + \cdots + a_n'$ is. We see that $10^r - 1$ is divisible by $9$, thus $c$ is an integer. Furthermore, $10^r \equiv 1 \pmod{d}$. Thus $A \equiv a_0 + a_1 + \cdots + a_n \pmod{d}$. But $a_i' \equiv a_i \pmod{d}$. Thus $A \equiv a_0' + a_1' + \cdots + a_n' \pmod{d}$. (Crelle) Let $A = a_0 + 10a_1 + 100a_2 + \cdots 10^na_n$. To test $A$ for divisibility by $d$, choose any $n$ coprime with $d$ and let $r = 10n \pmod{d}$. Now test $a_0 + ra_1 + \cdots r^na_n$ for divisibility by $d$. If $A \equiv 0 \pmod{d}$ then $nA \equiv 0 \pmod{d}$. But $nA \equiv a_0 + ra_1 + \cdots r^na_n \pmod{d}$. (Wilbraham) Let $m$ and $10$ be coprime. Suppose that $10^p \equiv 1 \pmod{m}$. If $A = a_0 + a_110^p + \cdots + a_n10^{pn}$ then $A$ is divisible by $m$ iff $a_0 + a_1 + \cdots + a_n$ is. We have $A \equiv a_0 + a_1 + \cdots + a_n \pmod{m}$. Let $m$ and $10$ be coprime. Suppose that $10^p \equiv 1 \pmod{m}$. If $A = a_0 + 10a_1 + 100a_2 + \cdots + 10^na_n$ then if $S_0 = a_0 + a_p + \cdots$, $S_1 = a_1 + a_{p+1} + \cdots$, etc., then $A \equiv S_0 + 10S_1 + 100S_2 + \cdots \pmod{m}$. We have that $S_0 \equiv a_0 + 10^pa_p + 10^{2p}a_{2p} + \cdots \pmod{m}$, $S_1 \equiv a_1 + 10^pa_{p+1} + 10^{2p}a_{2p + 1} + \cdots \pmod{m}$, etc. Thus $A \equiv S_0 + 10S_1 + 100S_2 + \cdots \pmod{m}$. (Schlegel) Suppose $d \equiv 1, 3, 7, 9 \pmod{10}$. Let $m = 1, 7, 3, 9$ respectively. Suppose $A = 10k + r$, then $A$ is divisible by $d$ iff $(A - rdm)/10$ is. We note that $dm = 10s + 1$ for some $s$. Thus $rdm \equiv r \equiv A \pmod{10}$ so that $A - rdm$ is divisible by $10$. As $\gcd(d, 10) = 1$, $A - rdm$ is divisible by $d$ iff $(A - rdm)/10$ is. But the former is divisible by $d$ iff $A$ is. (Ripert) If $d\alpha - \delta a$ is divisible by $m = 10\delta + \alpha$ with $\gcd(\alpha, m) = 1$ then $10d + a$ is divisible by $m$. We have $d\alpha \equiv \delta a \pmod{m}$. Thus $\alpha(10d + a) \equiv 10\delta a + \alpha a \equiv 0 \pmod{m}$.

As $\gcd(\alpha, m) = 1$, we must have $10d + a \equiv 0 \pmod{m}$. (Liljevalch) Suppose $\alpha 10^k - \beta$ is divisible by $m$ for some $m$ coprime to $10$. Then $a - b 10^k$ divisible by $m$ implies $\alpha a - \beta b$ is too. The converse is true if $\gcd(\beta, m) = 1$. Suppose $\alpha 10^k - \beta = mx$ for some $x$ and $a - b 10^k = mx'$ for some $x'$. Then $a\alpha 10^k \equiv b\beta 10^k \mod{m}$.

As $\gcd(m, 10) = 1$ we have $a\alpha \equiv b\beta \mod{m}$.

Conversely if $a\alpha \equiv b\beta \mod{m}$ then $a\alpha 10^k \equiv b\beta 10^k \mod{m}$. As $\alpha 10^k \equiv \beta \pmod{m}$ and $\gcd(\beta, m) = 1$ we have $a \equiv b 10^k \pmod{m}$. (Catalan) Suppose that $\gcd(a, a') = 1$ and $\gcd(b, b') = 1$. Let $N = aa' + bb'$. Suppose that $Aa + Bb = Nx$ for some $x$ and $A'a' + B'b' = Nx'$ for some $x'$. Then $AA' + BB'$ is divisible by $N$. We have $$AA'aa' + BB'aa' = (Nx - Bb)(Nx' - B'b') + BB'aa' \equiv BB'bb' + BB'aa' \equiv 0 \pmod{N}.$$ Now suppose that the largest power of $p$ dividing both $N$ and $a$ is $p^k$. As $\gcd(a, b) = 1$ and $N = aa' + bb'$, we must have $p^k$ divides $b'$. But as $\gcd(a', b') = 1$ and $A'a' + B'b' = Nx'$ we must then have $p^k$ divides $A'$. Similarly, as $\gcd(a, b) = 1$ and $Aa + Bb = Nx$ we must have $p^k$ divides $B$.

We can divide all of $a, b', A', B$ through by $p^k$. Repeating for each prime $p$ dividing $a$ and $N$, we can reduce to the case where $\gcd(a, N) = 1$. A similar argument works for $a'$, so that we can suppose without loss of generality that $\gcd(a', N) = 1$.

Now because $AA'aa' + BB'aa' \equiv 0 \pmod{N}$, we must have that $N$ divides $AA' + BB'$. (Folie) Let $p = 10a + c$ be prime and $ak' \pm ck = px$ for some $x$ and $Ak' \pm Ck = px'$ for some $x'$. If $a, c, k, k'$ are not divisible by $p$ then $10A + C$ is divisible by $p$. We have that $10aAk' = (p - c)(px' \mp Ck) \equiv \pm cCk \pmod{p}$. Also $Cak' = C(px \mp ck) \equiv \mp cCk \pmod{p}$. Thus $ak'(10A + C) \equiv 0 \pmod{p}$. As $\gcd(a, p) = 1$ and $\gcd(k', p) = 1$ we must have $10A + C \equiv 0 \pmod{p}$.