Divisibility Tests (3 and 9)

Before we go onto the divisibility proofs, let first acknowledge what is known as a *digital* form of an integer. Let n be an integer and let's represent it by a sum of powers of ten. That is for an integer in some base b, it follows that for n = (d_{k}d_{k-1}…d_{1}d_{0})_{b}, then:

\begin{align} \quad n_b = \sum_{i=0}^{k} d_i b^i = d_0 b^0 + d_1 b^1 + ... + d_{k-1} b^{k-1} + d_k b^k \end{align}

For example, we will only use base 10, so it follow that:

(2)\begin{align} \quad n_{10} = \sum_{i=0}^{k} d_i 10^i = d_0 10^0 + d_1 10^1 + ... + d_{k-1} 10^{k-1} + d_k 10^k \end{align}

# Lemma 1: A number n is divisible by 9 if the sum of it's digits is divisible by 9.

**Proof:**Suppose we have an integer n. We can represent n in terms of powers of 10, where d_{k}, d_{k-1}… d_{1}, d_{0}represents the digits of number.

\begin{equation} n = d_k 10^k + d_{k-1} 10^{k-1} + ... + d_1 10^1 + d_0 10^0 \end{equation}

- For example, 4235 = 4 * 10
^{3}+ 2 * 10^{2}+ 3 * 10^{1}+ 5 * 10^{0}. Thus it follows that:

\begin{align} \quad n \equiv d_k 10^k + d_{k-1} 10^{k-1} + ... + d_1 10^1 + d_0 10^0 \pmod 9 \end{align}

- We know that any power of 10 (mod 9) is 1, thus it follows that:

\begin{align} \quad n \equiv d_k 1^k + d_{k-1} 1^{k-1} + ... + d_1 1^1+ d_0 0^1 \pmod 9 \\ n \equiv d_k + d_{k-1} + ... + d_1 + d_0 \pmod 9 \end{align}

- Thus the proof is complete as d
_{k}+ d_{k-1}+ … + d_{1}+ d_{0}is the sum of the digits of n which leaves the same remainder when divided by 9.

# Lemma 2: A number n is divisible by 3 if the sum of it's digits is divisible by 3.

**Proof:**The proof operates in a similar manner. Suppose we have an integer n such that:

\begin{equation} n = d_k 10^k + d_{k-1} 10^{k-1} + ... + d_1 10^1 + d_0 10^0 \end{equation}

- Then:

\begin{align} \quad n \equiv d_k 10^k + d_{k-1} 10^{k-1} + ... + d_1 10^1 + d_0 10^0 \pmod 3 \\ n \equiv d_k 1^k + d_{k-1} 1^{k-1} + ... + d_1 1^1+ d_0 0^1 \pmod 3 \\ n \equiv d_k + d_{k-1} + ... + d_1 + d_0 \pmod 3 \end{align}

- Notice that 10 mod 3 is 1, so we have the same result as we did with divisibility by 9. Thus the proof is complete.

# Lemma 3: The product of three consecutive natural numbers is divisible by 6.

**Proof:**Suppose that n is our number. We know that n is composed of three integers that are all naturals numbers (integers greater than 0). Hence, n will be composed of two even numbers and one odd number OR two odd numbers and one even number. In both cases, the product of these three numbers will be even, and hence, n is divisible by 2. Now we know that n is also divisible by 3 since n is composed of 3 consecutive numbers, one of which is always divisible by 3. Since n is divisible by both 2 and 3, then n is also divisible by 6, that is $n \equiv 0 \pmod {6}$, and the proof is complete.