Special Divisibility Tests

Appendix A Special Divisibility Tests

Example A.0.14.

In the decimal system, we have

\begin{equation*} 209 = 2\cdot 10^2 + 0\cdot 10 + 9\cdot 10^0. \end{equation*}

In binary notation we represent the same quantity as \(11010001;\) that is,

\begin{equation*} 1 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0. \end{equation*}

Here we have written an integer in base \(10\) notation and then in base \(2\) notation. We can indeed do this in any base.

Theorem A.0.15.

Let \(k\gt 1\) be an integer. Then, for each \(n \in\mathbb{N},\) there exists a representation

\begin{equation*} n = a_sk^s + a_{s-1}k^{s-1} + \cdots + a_1k + a_0, \end{equation*}

where \(a_s\neq 0,\) and where each \(a_i\) is nonnegative and less than \(k.\) Furthermore, this representation is unique; it is called the representation of \(n\) to the base \(k.\)

Proof.

By the Division Algorithm there exist \(q_1, a_0 \in\mathbb{Z}\) such that

\begin{equation*} n = q_1k + a_0 \hspace{10mm} 0 \leq a_0 \lt k. \end{equation*}

If \(q_1\lt k\) we are done. If \(q_1 \geq k,\) we can divide again and get for some \(q_2, a_1 \in\mathbb{Z}\)

\begin{equation*} q_1 = q_2k + a_1 \hspace{10mm} 0 \leq a_1 \lt k. \end{equation*}

Substituting this into the previous equality gives

\begin{equation*} n = (q_2k + a_1)k + a_0 = q_2k^2 + a_1k + a_0. \end{equation*}

As long as \(q_i \geq k\) we can continue this process. As a consequence of the Division Algorithm, we have

\begin{equation*} n \gt q_1 \gt q_2 \gt \cdots \geq 0 \end{equation*}

so that in at most \(n-1\) steps the process will stop, say at the \((s-1)\)st stage. We then set \(a_s = q_s\) and we get

\begin{equation*} n = a_sk^s + a_{s-1}k^{s-1} + \cdots + a_1k + a_0, \end{equation*}

where \(a_s \neq 0,\) and where each \(a_i\) is nonnegative and less than \(k.\)

To see the uniqueness we just assume that there are two different representations of \(n\) say

\begin{equation*} n = a_sk^s + a_{s-1}k^{s-1} + \cdots + a_1k + a_0= b_sk^s + b_{s-1}k^{s-1} + \cdots + b_1k + b_0. \end{equation*}

Subtracting the one representation from the other we get

\begin{equation*} 0 = c_sk^s + c_{s-1}k^{s-1} + \cdots + c_1k + c_0, \end{equation*}

where \(c_i = a_i-b_i\) for each \(i.\) Since the two representations are different there is a minimum \(i\) so that \(c_i \neq 0,\) say \(c_j.\) Then

\begin{equation*} 0 = c_sk^s + c_{s-1}k^{s-1} + \cdots + c_jk^j, \end{equation*}

so that dividing out \(k^j\) gives

\begin{equation*} c_j = -k(c_sk^s + c_{s-1}k^{s-1} + \cdots + c_{j+1}). \end{equation*}

This tells us that \(k\vert d_j,\) and so \(k \leq \vert d_j \vert,\) which is a contradiction. Thus the representation is unique.

Definition A.0.16.

For \(n = a_sk^s + a_{s-1}k^{s-1} + \cdots + a_1k + a_0\) a representation of \(n\) to the base \(k,\) we abbreviate as

\begin{equation*} n = (a_sa_{s-1} \cdots a_2a_1a_0)_k. \end{equation*}

This is called the base \(k\) place-value notation for \(n.\)

Example A.0.17.

The first example can be rewritten as

\begin{equation*} 209 = (209)_{10} \end{equation*}

and

\begin{equation*} 209 = (11010001)_2. \end{equation*}

We wish to give some quick divisibility test to see whether an integer \(n\) is divisible by \(9\) or \(11.\) But for this we first go back to polynomials.

Theorem A.0.18.

Let \(p(x) = \sum_{k=0}^{m}c_kx^k\) be a polynomial function of \(x\) with integer coefficients. If \(a \equiv b\pmod{n},\) then \(p(a) \equiv p(b)\pmod{n}.\)

Proof.

This is a direct application of the properties of modular arithmetic.

Corollary A.0.19.

If \(a \equiv b\pmod{n}\) and \(a\) is a solution to \(p(a) \equiv 0\pmod{n},\) then \(b\) is also a solution.

Proof.

From the theorem above \(p(a) \equiv p(b)\pmod{n}\) and so by transitivity \(p(b) \equiv 0\pmod{n}.\)

Theorem A.0.20.

Let \(n = (a_ma_{m-1} \cdots a_1a_0)_{10}\) and \(S = n = a_m + a_{m-1} +\cdots + a_1 + a_0.\) Then \(9\vert n\) if and only if \(9\vert S.\)

Consider \(p(x) = \sum_{k=0}^{m}a_kx^k.\) Since \(10 \equiv 1\pmod{9},\) we have \(p(10) \equiv p(1)\pmod{9}.\) Now \(p(10) = n\) and \(p(1) = S.\) So \(n \equiv S\pmod{9}.\) So \(n \equiv 0\pmod{9}\) if and only if \(S \equiv 0\pmod{9}.\)

Theorem A.0.21.

Let \(n = (a_ma_{m-1} \cdots a_1a_0)_{10}\) and \(T = n = a_0 -a_{1} +a_2-\cdots + (-1)^ma_m.\) Then \(11\vert n\) if and only if \(11\vert T.\)

Proof.

Consider \(p(x) = \sum_{k=0}^{m}a_kx^k.\) Since \(10 \equiv -1\pmod{11},\) we have \(p(10) \equiv p(-1)\pmod{11}.\) Now \(p(10) = n\) and \(p(-1) = T.\) So \(n \equiv T\pmod{11}.\) So \(n \equiv 0\pmod{11}\) if and only if \(T \equiv 0\pmod{11}.\)

Example A.0.22.

Consider the integer \(n = 1, 571, 724.\) Since

\begin{equation*} 1 + 5 + 7 + 1 + 7 + 2 + 4 = 27 \end{equation*}

and \(9\vert 27,\) we have that \(9\vert 1, 571, 724.\) Also

\begin{equation*} 4 -2 + 7 - 1 + 7 - 5 + 1 = 11 \end{equation*}

and \(11\vert 11,\) we have that \(11\vert 1, 571, 724.\)