NEW ALGORITHMS FOR THE DIVISION’S QUOTIENT

S. Mazouzi

Abstract. We shall propose in this paper some practical divisibility tests as well as genuine expressions for the division’s quotient. The latter is only based on successive operations using either addition or substraction and multiplication by some appropriate integer weights.

1. Introduction. As everybody knows, of all traditional known operations, division is the most intricate and requires time, patience, and even material resources when implementing the algorithm in hardware. In order to quickly recognize whether a positive integer number is divisible by another some attempts have been made throughout the years to develop a basic skill relevant to the divisibility tests which may relieve human beings of performing long arithmetical operations.

Besides the inherited divisibility tests by numbers less than or equal to 11 (see [1, 2, 5]) the ancient Spanish provided their own divisibility criterion for the number 13 [4]. A few years ago, inspired by the latter criterion, T. Trotter gave in [4] easy tests for divisibility by the numbers 17 and 19. The reader can eventually find through the number theory literature a great deal of rough results dealing with divisibility tests by specific numbers which require a rigorous theoretical framework.

We shall introduce in the present work new methods of testing divisibility of a positive integer number by another, and whenever it is true, we propose genuine algorithms to find the corresponding division’s quotient. Meanwhile, we generalize (and simplify) the A. Khane results [3] by giving in an elementary way the exact multiplier for each division. The main technique we shall use is based on the natural properties of the “unit function” u: ℕ → \{0, 1, …, 9\} defined by u(n) = n−10⌊\frac{n}{10}⌋ (it is the function that associates to any nonnegative integer number its unit’s digit); for instance, u(5248) = 8 and u(219) = 9. As usual, the brackets ⌊·⌋ denote the floor function. Next, we define the function U: ℕ × ℕ → {0, 1, …, 9} by U(m, n) = u(u(m)u(n)), for any nonnegative integers m and n. The restriction of U to the set: {0, 1, …, 9} × {0, 1, …, 9} generates the following table of multiplication:

\begin{matrix}× & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 0 & 2 & 4 & 6 & 8 & 0 & 2 & 4 & 6 & 8 \\ 3 & 0 & 3 & 6 & 9 & 2 & 5 & 8 & 1 & 4 & 7 \\ 4 & 0 & 4 & 8 & 2 & 6 & 0 & 4 & 8 & 2 & 6 \\ 5 & 0 & 5 & 0 & 5 & 0 & 5 & 0 & 5 & 0 & 5 \\ 6 & 0 & 6 & 2 & 8 & 4 & 0 & 6 & 2 & 8 & 4 \\ 7 & 0 & 7 & 4 & 1 & 8 & 5 & 2 & 9 & 6 & 3 \\ 8 & 0 & 8 & 6 & 4 & 2 & 0 & 8 & 6 & 4 & 2 \\ 9 & 0 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{matrix}

It seems clear from the above table that if n ∈ ℕ is fixed in the set {1, 3, 7, 9}, that is n is coprime to the base A = 10, then the section function U(·, n) = u((·)n): {0, 1, …, 9} → {0, 1, …, 9}, denoted u_{n}, is a one–to–one and onto mapping. As a matter of fact one can easily check that

1) u_{1}(m) = u(m) = m, for all m ∈ {0, 1, …, 9},

2) u_{3}(m) = 10⌊\frac{5m+6}{7}⌋ − 7m, for all m ∈ \{0, 1, …, 9\},

3) u_{7}(m) = 10⌊\frac{m+2}{3}⌋ − 3m, for all m ∈ \{0, 1, …, 9\},

4) u_{9}(m) = 10 − m − 10⌊\frac{10−m}{10}⌋, for all m ∈ \{0, 1, …, 9\},

5) u_{a}(m) + u_{10−a}(m) = 10 − 10⌊\frac{10−m}{10}⌋, for all m ∈ \{0, 1, …, 9\}, for all a ∈ {1, 3, 7, 9},

6) u_{a}^{−1}(m) = 10⌊\frac{(a−2)m+a−1}{a}⌋ − am, for all m ∈ \{1, …, 9\}, a = 3, 7,

7) u_{9}^{−1} = u_{9}.

2. Results Relevant to the Decimal Base. We start with the following results which give simple algorithms to test the divisibility of a positive integer number by another and systematically find the corresponding quotient. The principle consists of finding the digits of the quotient proceeding from the unit’s digit to the left most digit.

\underline{Theorem 1 (division from right to left)}. Let N_{0}, K ∈ ℕ such that b = u(N_{0}) ≠ 0 and K = 10p + a, for some a ∈ {1, 3, 7, 9}. We define the sequence {N_{k}}_{k≥0} ⊂ ℕ by

N_{k+1} = \frac{N_{k} − Ku_{a}^{−1}(u(N_{k}))}{10}, k = 0, 1, ….  (1)

Then, N_{0} is divisible by K if and only if N_{k} is divisible by K for each k ∈ ℕ. Moreover, the quotient L = N_{0}/K is given by

L = ∑_{k=0}^{n̄} u_{a}^{−1}(u(N_{k})) · 10^{k},

where n̄ is the least positive integer number n such that N_{n+1} = 0.

\underline{Proof}. Write N_{0} = 10A + b. Then

\begin{aligned}N_{0} & = 10A + b − Ku_{a}^{−1}(b) + Ku_{a}^{−1}(b) \\ & = 10(A − \frac{Ku_{a}^{−1}(b) − b}{10}) + Ku_{a}^{−1}(b). \end{aligned}

Since 10 and Ku_{a}^{−1}(b) are coprime and K divides N_{0} then K must divide

A − \frac{Ku_{a}^{−1}(b) − b}{10} = \frac{N_{0} − Ku_{a}^{−1}(b)}{10} = N_{1}

and by induction K divides each term N_{k}.

It follows from relation (1) that

N_{k+1} ≤ \frac{N_{k}}{10} , k = 0, 1, …

so that,

N_{k+1} ≤ \frac{N_{0}}{10^{k+1}} , k = 0, 1, …

and thus, lim_{k→∞} N_{k} = 0. Therefore, there is a positive integer n such that N_{k} = 0 for all k ≥ n. Denote by n̄ the least positive integer n such that N_{n+1} = 0.

To find the quotient we observe that

10^{k+1}N_{k+1} = 10^{k}N_{k} − 10^{k}Ku_{a}^{−1}(u(N_{k})), k = 0, 1, ….

Then,

\begin{aligned}∑_{k=0}^{n̄} 10^{k+1}N_{k+1} & = ∑_{k=1}^{n̄} 10^{k}N_{k} = ∑_{k=0}^{n̄} 10^{k}N_{k} − ∑_{k=0}^{n̄} 10^{k}Ku_{a}^{−1}(u(N_{k})) \\ & = KL + ∑_{k=1}^{n̄} 10^{k}N_{k} − K ∑_{k=0}^{n̄} u_{a}^{−1}(u(N_{k}))10^{k}, \end{aligned}

from which we get

L = ∑_{k=0}^{n̄} u_{a}^{−1}(u(N_{k}))10^{k}.

\underline{Example 2}. Let N_{0} = 2111103, K = 389, then we have

N_{0} = 2 1 1 1 1 0 3
−  2 7 2 3 (= Ku_{9}^{−1}(3))
− − − − − − − −
N_{1} = 2 1 0 8 3 8 ∅
− 7 7 8 (= Ku_{9}^{−1}(8))
− − − − − − −
N_{2} = 2 1 0 0 6 ∅
− 1 5 5 6 (= Ku_{9}^{−1}(6))
− − − − − −
N_{3} = 1 9 4 5 ∅
− 1 9 4 5  (= Ku_{9}^{−1}(5))
− − − − −
N_{4} = 0

Hence, L = 10^{3}u_{9}^{−1}(5) + 10^{2}u_{9}^{−1}(6) + 10u_{9}^{−1}(8) + u_{9}^{−1}(3) = 5427.

\underline{Theorem 3 (division from right to left)}. Let N_{0}, K ∈ ℕ such that b = u(N_{0}) ≠ 0 and K = 10p+a, for some a ∈ {1, 3, 7, 9}. Let {N_{k}}_{k≥0} ⊂ ℕ be a sequence defined by

N_{k+1} = \frac{N_{k} + Ku_{10−a}^{−1}(u(N_{k}))}{10} k = 0, 1, ….  (2)

Then, N_{0} is divisible by K if and only if N_{k} is divisible by K for each k ∈ ℕ. Besides, the quotient L = N_{0}/K is given by

L = {10 − u_{10−a}^{−1}(b)} + ∑_{k=1}^{n̄′}{9 − u_{10−a}^{−1}(u(N_{k}))} · 10^{k},

where n̄′ is the least positive integer n such that N_{n+1} = K.

\underline{Proof}. We have

\begin{aligned}N_{0} & = 10A + b = 10A + b + Ku_{10−a}^{−1}(b) − Ku_{10−a}^{−1}(b) \\ & = 10(A + \frac{Ku_{10−a}^{−1}(b) + b}{10}) − Ku_{10−a}^{−1}(b). \end{aligned}

Now since the numbers 10 and Ku_{10−a}^{−1}(b) are coprime and K divides N_{0}, then K must divide the integer number

A + \frac{Ku_{10−a}^{−1}(b) + b}{10} = \frac{N_{0} + Ku_{10−a}^{−1}(b)}{10} = N_{1}

and by induction K divides each N_{k}.

We observe on the other hand that

N_{k+1} − K = \frac{N_{k} − K}{10} − \frac{K(9 − u_{10−a}^{−1}(u(N_{k})))}{10}, k = 0, 1, …

so that,

0 ≤ N_{k+1} − K ≤ \frac{N_{k} − K}{10} ≤ ⋯ ≤ \frac{N_{0} − K}{10^{k+1}} , k = 0, 1, ….

Thus, there is a positive integer n such that N_{k+1} = K, for all k ≥ n. We denote by n̄′ the least positive integer n such that N_{n+1} = K.

We have from relation (2)

10^{k+1}N_{k+1} = 10^{k}N_{k} + 10^{k}Ku_{10−a}^{−1}(u(N_{k})), k = 0, 1, …

then,

∑_{k=0}^{n̄′} 10^{k+1}N_{k+1} = 10^{n̄′ +1}K + ∑_{k=1}^{n̄′} 10^{k}N_{k}

= ∑_{k=0}^{n̄′} 10^{k}N_{k} + K ∑_{k=0}^{n̄′} u_{10−a}^{−1}(u(N_{k})) · 10^{k}

= KL + ∑_{k=1}^{n̄′} 10^{k}N_{k} + K ∑_{k=0}^{n̄′} u_{a}^{−1}(u(N_{k})) · 10^{k},

from which we get

\begin{aligned}L & = 10^{n̄′ +1} − ∑_{k=0}^{n̄′} u_{10−a}^{−1}(u(N_{k})) · 10^{k} \\ & = \{10 − u_{10−a}^{−1}(b)\} + ∑_{k=1}^{n̄′}\{9 − u_{10−a}^{−1}(u(N_{k}))\} · 10^{k}. \end{aligned}

\underline{Example 4}. Let N_{0} = 2111103, K = 389, then we have

N_{0} = 2 1 1 1 1 0 3
+  1 1 6 7 (= Ku_{1}^{−1}(3))
− − − − − − − −
N_{1} = 2 1 1 2 2 7 ∅
+ 2 7 2 3 (= Ku_{1}^{−1}(7))
− − − − − − −
N_{2} = 2 1 3 9 5 ∅
+ 1 9 4 5 (= Ku_{1}^{−1}(5))
− − − − − −
N_{3} = 2 3 3 4 ∅
+ 1 5 5 6  (= Ku_{1}^{−1}(4))
− − − − −
N_{4} = 3 8 9 ∅  (= K)

so that,

\begin{aligned}L & = 10^{3}(9 − u_{1}^{−1}(4)) + 10^{2}(9 − u_{1}^{−1}(5)) + 10(9 − u_{1}^{−1}(7)) + (10 − u_{1}^{−1}(3)) \\ & = 5427. \end{aligned}

\underline{Theorem 5 (Division via a positive multiplier)}. Let N_{0}, K ∈ ℕ such that b = u(N_{0}) and K = 10p+a, for some a ∈ {1, 3, 7, 9}. We define the sequence {Ñ_{k}}_{k≥0} ⊂ ℕ by

\{ \begin{matrix}Ñ_{0} = N_{0}u_{a}^{−1}(9), \\ Ñ_{k+1} = \frac{Ñ_{k} + Ku_{a}^{−1}(9)u(Ñ_{k})}{10}, & k = 0, 1, …. \end{matrix}  (3)

Then, N_{0} is divisible by K if and only if Ñ_{k} is divisible by K for each k ∈ ℕ. Furthermore, the quotient L = N_{0}/K is given by

L = {10 − u(bu_{a}^{−1}(9))} + ∑_{k=1}^{n̄}{9 − (u(Ñ_{k}))} · 10^{k},

where n̄ is the least positive integer n such that Ñ_{n+1} = Ku_{a}^{−1}(9).

\underline{Proof}. It is easy to show that the sequence \{Ñ_{k}\}_{k≥0} is nonincreasing and there is a positive integer n such that Ñ_{k+1} = Ku_{a}^{−1}(9), for all k ≥ n. Let n̄ be the least positive integer such that Ñ_{n̄+1} = Ku_{a}^{−1}(9).

The first assertion of the theorem is similar to that of the preceding theorems and so it is omitted. It is worthwhile to observe that

\begin{aligned}Ñ_{k+1} & = \frac{Ñ_{k} + (Ku_{a}^{−1}(9))u(Ñ_{k})}{10} \\ & = \frac{Ñ_{k} − u(Ñ_{k})}{10} + \frac{(Ku_{a}^{−1}(9) + 1)}{10}u(Ñ_{k}), k = 0, 1, …. \end{aligned}

We shall denote by μ^{+}(K) the positive integer \frac{Ku_{a}^{−1}(9) + 1}{10} called a positive multiplier. We have for different expressions of K the following values of the corresponding multipliers:

μ^{+}(K) = \{ \begin{matrix}9p + 1, & if u(K) = 1 \\ 3p + 1, & if u(K) = 3 \\ 7p + 5, & if u(K) = 7 \\ p + 1, & if u(K) = 9. \end{matrix}

To obtain explicitly the quotient L = N_{0}/K we have from relation (3)

10^{k+1}Ñ_{k+1} = 10^{k}Ñ_{k} + 10^{k}Ku_{a}^{−1}(9)u(Ñ_{k}), k = 0, 1, …

so that,

∑_{k=0}^{n̄} 10^{k+1}Ñ_{k+1} = 10^{n̄+1}Ku_{a}^{−1}(9) + ∑_{k=1}^{n̄} 10^{k}Ñ_{k}

= ∑_{k=0}^{n̄} 10^{k}Ñ_{k} + Ku_{a}^{−1}(9) ∑_{k=0}^{n̄} u(Ñ_{k}) · 10^{k}

= KLu_{a}^{−1}(9) + ∑_{k=1}^{n̄} 10^{k}Ñ_{k} + Ku_{a}^{−1}(9) ∑_{k=0}^{n̄} u(Ñ_{k}) · 10^{k},

which implies that

\begin{aligned}L & = 10^{n̄+1} − ∑_{k=0}^{n̄} u(Ñ_{k}) · 10^{k} \\ & = \{10 − u(bu_{a}^{−1}(9))\} + ∑_{k=1}^{n̄}\{9 − u(Ñ_{k})\} · 10^{k}, \end{aligned}

as expected.

\underline{Example 6}. Let N_{0} = 4779411 and K = 7503, then Ñ_{0} = N_{0}u_{3}^{−1}(9) = 14338233 and Ku_{3}^{−1}(9) = 22509. Hence, μ^{+}(K) = (Ku_{3}^{−1}(9) + 1)/10 = 2251, then

Ñ_{0} = 1 4 3 3 8 2 3 3
+  6 7 5 3 (= μ^{+}(K)u(Ñ_{0}))
− − − − − − − −
Ñ_{1} = 1 4 4 0 5 7 6
+ 1 3 5 0 6 (= μ^{+}(K)u(Ñ_{1}))
− − − − − − −
Ñ_{2} = 1 5 7 5 6 3
+ 6 7 5 3 (= μ^{+}(K)u(Ñ_{2}))
− − − − − −
Ñ_{3} = 2 2 5 0 9  (= Ku_{3}^{−1}(9)

Since Ñ_{3} = Ku_{3}^{−1}(9), then

L = 10^{2}(9 − u(Ñ_{2})) + 10^{1}(9 − u(Ñ_{1})) + (10 − u(Ñ_{0})) = 637.

\underline{Theorem 7 (Division via a negative multiplier)}. Let N_{0}, K ∈ ℕ such that b = u(N_{0}) and K = 10p+a, for a ∈ {1, 3, 7, 9}. Let {Ñ_{k}}_{k≥0} ⊂ ℕ be a sequence defined by

\{ \begin{matrix}Ñ_{0} = N_{0}u_{10−a}^{−1}(9), \\ Ñ_{k+1} = \frac{Ñ_{k} − Ku_{10−a}^{−1}(9)u(Ñ_{k})}{10}, & k = 0, 1, . . .. \end{matrix}  (4)

Then, N_{0} is divisible by K if and only if Ñ_{k} is divisible by K for each k ∈ ℕ. Besides, the quotient L = N_{0}/K is given by

L = ∑_{k=0}^{n̄′} u(Ñ_{k}) · 10^{k},

where n̄′ is the least positive integer n such that Ñ_{n+1} = 0.

\underline{Proof}. It can easily be proved that the sequence \{Ñ_{k}\}_{k≥0} is nonincreasing and there is a positive integer n such that Ñ_{k+1} = 0, for all k ≥ n. Let n̄ be the least positive integer such that Ñ_{n̄+1} = 0.

As above the first assertion of the theorem is similar to that of the foregoing theorems. Next, we note that

\begin{aligned}Ñ_{k+1} & = \frac{Ñ_{k} − Ku_{10−a}^{−1}(9)u(Ñ_{k})}{10} \\ & = \frac{Ñ_{k} − u(Ñ_{k})}{10} − \frac{(Ku_{10−a}^{−1}(9) − 1)}{10}u(Ñ_{k}), k = 0, 1, …. \end{aligned}

We shall designate by μ^{−}(K) the negative integer number −\frac{Ku_{10−a}^{−1}(9) − 1}{10} called a negative multiplier. Here are the values of the negative multipliers for different expressions of K:

−μ^{−}(K) = \{ \begin{matrix}p, & if u(K) = 1 \\ 7p + 2, & if u(K) = 3 \\ 3p + 2, & if u(K) = 7 \\ 9p + 8, & if u(K) = 9. \end{matrix}

Let us now find the expression of the corresponding quotient L. Relation (4) gives

10^{k+1}Ñ_{k+1} = 10^{k}Ñ_{k} − 10^{k}Ku_{10−a}^{−1}(9)u(Ñ_{k}), k = 0, 1, …

∑_{k=0}^{n̄′} 10^{k+1}Ñ_{k+1} = ∑_{k=1}^{n̄′} 10^{k}Ñ_{k}

= ∑_{k=0}^{n̄′} 10^{k}Ñ_{k} − Ku_{10−a}^{−1}(9) ∑_{k=0}^{n̄′} u(Ñ_{k}) · 10^{k}

= KLu_{10−a}^{−1}(9) + ∑_{k=1}^{n̄′} 10^{k}Ñ_{k} − Ku_{10−a}^{−1}(9) ∑_{k=0}^{n̄′} u(Ñ_{k}) · 10^{k},

from which we deduce that

L = ∑_{k=0}^{n̄′} u(Ñ_{k}) · 10^{k}.

\underline{Example 8}. Let N_{0} = 4779411 and K = 7503, then Ñ_{0} = N_{0}u_{10−3}^{−1}(9) = 33455877 and Ku_{10−3}^{−1}(9) = 52521. Hence, μ^{−}(K) = −(Ku_{7}^{−1}(9) − 1)/10 = −5252, then

Ñ_{0} = 3 3 4 5 5 8 7 7
−  3 6 7 6 4 (= μ^{−}(K)u(Ñ_{0}))
− − − − − − − −
Ñ_{1} = 3 3 0 8 8 2 3
− 1 5 7 5 6 (= μ^{−}(K)u(Ñ_{1}))
− − − − − − −
Ñ_{2} = 3 1 5 1 2 6
− 3 1 5 1 2 (= μ^{−}(K)u(Ñ_{2}))
− − − − − −
Ñ_{3} = 0

Hence, L = 10^{2}u(Ñ_{2}) + 10^{1}u(Ñ_{1}) + u(Ñ_{0}) = 637.

\underline{Remark 1}. Since

μ^{−}(K) = −\frac{Ku_{10−a}^{−1}(9) − 1}{10} = −\frac{K(10 − u_{a}^{−1}(9)) − 1}{10} = −K + \frac{Ku_{a}^{−1}(9) + 1}{10},

then,

μ^{+}(K) − μ^{−}(K) = K.

\underline{Proposition 9}. A positive integer N = ∑_{k=0}^{m} b_{k}10^{k} is divisible by K = 10p + a, for some a ∈ {1, 3, 7, 9} if and only if the positive integer N^{∗} = | ∑_{k=0}^{m} b_{k}μ^{m−k}| is divisible by K, where μ is either μ^{+}(K) or μ^{−}(K).

\underline{Proof}. We have for the first case μ = μ^{+}(K) = \frac{Ku_{a}^{−1}(9) + 1}{10} from which we

get 10 = \frac{Ku_{a}^{−1}(9) + 1}{μ}, therefore,

N = ∑_{k=0}^{m} b_{k}10^{k} = ∑_{k=0}^{m} b_{k}(\frac{Ku_{a}^{−1}(9) + 1}{μ})^{k}

= b_{0} + ∑_{k=1}^{m} b_{k}{1 + K ∑_{l=1}^{k} C_{k}^{l}K^{l−1}(u_{a}^{−1}(9))^{l}}μ^{−k}

= ∑_{k=0}^{m} b_{k}μ^{−k} + K ∑_{k=0}^{m} { ∑_{l=1}^{k} C_{k}^{l}K^{l−1}(u_{a}^{−1}(9))^{l}}μ^{−k}.

Multiplying both sides by μ^{m} we get

∑_{k=0}^{m} b_{k}μ^{m−k} = Nμ^{m} − K ∑_{k=0}^{m} { ∑_{l=1}^{k} C_{k}^{l}K^{l−1}(u_{a}^{−1}(9))^{l}}μ^{m−k}.

Since the right hand side is divisible by K, then ∑_{k=0}^{m} b_{k}μ^{m−k} is also divisible by K and conversely.

The second case can be dealt with in the same manner by merely observing

that 10 = \frac{1 − Ku_{a}^{−1}(9)}{μ}.

\underline{Theorem 10 (Division by complementation)}. Let N_{0} and K be two positive integer numbers such that u(N_{0}) ≠ 0 and K = 10p + a, with a ∈ {1, 3, 7, 9}.

We define the sequence {N̄_{k}}_{k≥0} ⊂ ℕ by

\{ \begin{matrix}N̄_{0} = 10^{m} − N_{0}u_{a}^{−1}(9), \\ N̄_{k+1} = \frac{N̄_{k} + Ku_{a}^{−1}(9)u(N̄_{k})}{10}, & k ≥ 0, \\ m being the number of digits of N_{0}u_{a}^{−1}(9). \end{matrix}  (5)

If N_{0} is divisible by K then the quotient L is given by

L = ∑_{k=0}^{n−1} u(N̄_{k})10^{k},

where n is the least positive integer such that 10^{n}N̄_{n} = 10^{m}.

\underline{Proof}. It can be proved that

N̄_{k} = 10^{m−k} − Ñ_{k} + Ku_{a}^{−1}(9), k = 1, 2, …

where {Ñ_{k}}_{k≥0} is defined by (3).

Let n be the least positive integer satisfying Ñ_{n} − Ku_{a}^{−1}(9) = 0, then N̄_{n} = 10^{m−n}, or equivalently, 10^{n}N̄_{n} = 10^{m}.

Relation (5) yields

∑_{k=0}^{n−1} N̄_{k+1}10^{k+1} = ∑_{k=0}^{n−1} N̄_{k}10^{k} + Ku_{a}^{−1}(9) ∑_{k=0}^{n−1} u(N̄_{k})10^{k},

so that,

N̄_{n}10^{n} ≡ 10^{m} = N̄_{0} + Ku_{a}^{−1}(9) ∑_{k=0}^{n−1} u(N̄_{k})10^{k},

hence,

N_{0}u_{a}^{−1}(9) = 10^{m} − N̄_{0} = Ku_{a}^{−1}(9) ∑_{k=0}^{n−1} u(N̄_{k})10^{k}.

Therefore,

L = ∑_{k=0}^{n−1} u(N̄_{k})10^{k}.

\underline{Example 11}. Let N_{0} = 520429, K = 637, then N_{0}u_{7}^{−1}(9) = 3643003 and K̂ = Ku_{7}^{−1}(9) = 4459, so that m = 7 and thus, N̄_{0} = 6356997.

N̄_{0} =  6 3 5 6 9 9 7
+  3 1 2 1 3 (= K̂u(N̄_{0}))
− − − − − − − − −
N̄_{1} =  6 3 8 8 2 1 ∅
+ 4 4 5 9 (= K̂u(N̄_{1}))
− − − − − − − −
N̄_{2} =  6 4 3 2 8 ∅
+ 3 5 6 7 2 (= K̂u(N̄_{2}))
− − − − − − −
N̄_{3} = 1 0 0 0 0 ∅

Since 10^{3}N̄_{3} = 10^{m}, (m = 7), then the quotient N_{0} over K is L = 817.

3. Generalization to Other Bases. It is sometimes practical to handle some special forms of the integer if we want to test its divisibility by another integer, rather than using its decimal representation. For this reason we shall obtain similar divisibility criteria to those we have already obtained in the decimal base. We have the following results:

\underline{Theorem 12}. Let A and K be two coprime positive integers nonequal to 0 and 1. A positive integer N_{0} = Am + b, with 0 ≤ b < A, is divisible by K if and only if

N_{1} = m + \frac{δK + 1}{A}b

is divisible by K. (δ being the least positive integer such that \frac{δK + 1}{A} is a positive integer).

\underline{Proof}. The fact that A and K are coprime implies the existence of two (nonunique) positive integers δ and μ such that μA − δK = 1. Then,

\begin{aligned}N_{0} & = Am + b = Am + b + δbK − δbK \\ & = A(m + \frac{δK + 1}{A}b) − δbK. \end{aligned}

As K is coprime to A and divides N_{0} then it must divide N_{1} = m + \frac{δK + 1}{A}b.

\underline{Theorem 13}. Let A and K be two coprime positive integers nonequal to 0 and 1. A positive integer N_{0} = Am + b, with 0 ≤ b < A, is divisible by K if and only if

N_{1} = m − \frac{δ′K − 1}{A}b

is divisible by K. (δ′ being the least positive integer such that \frac{δ′K − 1}{A} is a positive integer).

\underline{Proof}. Since A and K are coprime then there are two (nonunique) positive integers δ′ and μ′ such that δ′K − μ′A = 1. It follows that

\begin{aligned}N_{0} & = Am + b = Am + b + δ′bK − δ′bK \\ & = A(m − \frac{δ′K − 1}{A}b) + δ′bK. \end{aligned}

As K is coprime to A and divides N_{0} then it must divide N_{1} = m − \frac{δ′K − 1}{A}b.

\underline{Remark 2}. If we define r_{A}(S) to be the remainder of the euclidean division of S by A, then K divides N_{0} if and only if K divides each term of the sequence {N_{k}}_{k≥0} ⊂ ℕ defined by

N_{k+1} = \frac{N_{k} + δKr_{A}(N_{k})}{A}, k = 0, 1, ….

\underline{Theorem 14}. Let A and K be two coprime positive integers nonequal to 0 and 1. A positive integer N = ∑_{k=0}^{n} b_{k}A^{k} is divisible by K if and only if the positive integer N^{∗} = | ∑_{k=0}^{n} b_{k}μ^{n−k}| is divisible by K (μ is either defined by μ = (δK + 1)/A or μ = −(δ′K − 1)/A).

\underline{Proof}. Let us only consider the first case, that is μ = (δK + 1)/A, then A = (δK + 1)/μ. It follows that

\begin{aligned}N & = ∑_{k=0}^{n} b_{k}(\frac{δK + 1}{μ})^{k} = ∑_{k=0}^{n} b_{k}\{∑_{l=0}^{k} C_{k}^{l}(δK)^{l}\}μ^{−k} \\ & = ∑_{k=0}^{n} b_{k}\{1 + K ∑_{l=1}^{k} C_{k}^{l}δ^{l}K^{l−1}\}μ^{−k}, \end{aligned}

hence,

∑_{k=0}^{n} b_{k}μ^{n−k} = Nμ^{n} − K ∑_{k=0}^{n} b_{k}{ ∑_{l=1}^{k} C_{k}^{l}δ^{l}K^{l−1}}μ^{n−k}.

Therefore, N is divisible by K if and only if ∑_{k=0}^{n} b_{k}μ^{n−k} is divisible by K.

\underline{References}

1. D. M. Burton, Elementary Number Theory, 4th ed., Allyn and Bacon, Boston, MA, 1989.

2. M. Humphreys and N. Macharia, “Tests of Divisibility by 19,” The Mathematical Gazette, 82 (1999).

3. A. Khane, “Divisibility Tests,” Furman Univ. Elect. J. of Undergrad. Math., 3 (1997), 1–5.

4. T. Trotter, “Divisibility Tests,” www.trottermath.com/divtests.html.

5. N. N. Vorob’ev, Criteria for Divisibility, Univ. of Chicago Press, 1980.

Mathematics Subject Classification (2000): 11Y05, 11Y55.

S. Mazouzi Department of Mathematics Faculty of Sciences University of Annaba P. O. Box 12 Annaba 23000 Algeria email: mazouzi sa@yahoo.fr