Tests for Divisibility
Tests for Divisibility
We will now prove some very nice tests for divisibility.
Theorem 1: Let $n \in \mathbb{Z}$. Then $n$ is divisible by $9$ if the sum of the digits of $n$ is divisible by $9$. |
- Proof: Let $n \in \mathbb{Z}$ and assume that $n$ is divisible by $9$. We can represent $n$ in terms of it digits $d_0, d_1, ..., d_k \in \{ 0, 1, ..., 9 \}$ where:
\begin{align} \quad n = d_0 \cdot 10^0 + d_1 \cdot 10^1 + ... + d_k \cdot 10^k \end{align}
- Notice that $10^0 \equiv 1 \pmod 9$, $10^1 \equiv 1 \pmod 9$, $10^2 \equiv 1 \pmod 9$, …, $10^k \equiv 1 \pmod 9$. Therefore:
\begin{align} \quad n & \equiv (d_0 \cdot 10^0 + d_1 \cdot 10^1 + ... + d_k \cdot 10^k) \pmod 9 \\ \quad 0 & \equiv (d_0 + d_1 + ... + d_k) \pmod 9 \end{align}
- So $9 \mid (d_0 + d_1 + ... + d_k)$, i.e., the sum of the digits of $n$ is divisible by $9$. $\blacksquare$
Theorem 2: Let $n \in \mathbb{Z}$. Then $n$ is divisible by $3$ if the sum of the digits of $n$ is divisible by $3$. |
- Proof: Analogous to Theorem 1. $\blacksquare$
Theorem 3: The product of any three consecutive natural numbers is divisible by $6$. |
- Proof: Let $n \in \mathbb{N}$. Then $p = n(n+1)(n+2)$ is either the product of two even numbers and one odd number OR two odd numbers and one even number. In either case we see that this product is even, so $2 \mid p$.
- Furthermore, every third natural number is divisible by $3$ and selecting three consecutive natural numbers guarantees us that $3 \mid p$.
- Since $2 \mid p$ and $3 \mid p$ we have that $6 \mid p$. $\blacksquare$