Divisibility for all divisors relative prime to 10

---

Description

A method for testing the divisibility of a number for all divisors that are relatively prime to $10$ is described and mathematically justified. The method has two advantages. First it works for a large infinite set of divisors. Secondly, it also provides instructions on how to determine the required multiplier $m_{d}$ by mental arithmetic. Divisors d are considered that have no proper common divisors with the natural number $10$. For such divisors, divisibility criteria are presented that primarily support divisibility questions using mental arithmetic and are adapted to the decimal representation of the number under test. The assertion that $n$ is divisible is by $d$ is expressed by $d\mid n$ and $m\perp n$ means $m$ is relative prime to $n$ also known as $m$ coprime $n$. The greatest common divisor of $a,b$ is denoted by $(a,b)$. The task of deciding whether $d$ divides the number $n$ is is abbreviated to $d\mid n{\text{ ?}}$.

Divisibility criteria of the following kind of transition are considered:

Multiply the right-hand digit of the number $n$ to be tested by a multiplier $m$ and add the result to the number formed by the remaining left-hand digits.

As an example $7\mid 476$ is the assertion: $7$ divides $476$. For the divisor $7$ the multiplier $m=-2$ is suitable. The result of transition is $35=47-2\cdot 6$ and therefore $7\mid 476$. Such a divisibility test contains a human component. The user decides at his own discretion when he considers the divisibility to be tested to be decided positively or negatively. A computer would probably not be entrusted with such a decision.

A general approach to this kind of transition is given in Tests for divisibility. The multipliers in it differ in part from those in Mapping ${\color {blue}d\mapsto m_{d}}$.

First of all, let the divisors be characterised that are relatively prime to $10$. Let it be $r(d)$ the value of the right-hand digit of $d$. Then $d$ is relatively prime to $10$ if and only if $r(d)\in \{1,3,7,9\}$. To justify this, let it be said that the other possible right-hand digits $r(d)\in \{0,2,4,5,6,8\}$ would entail the divisibility of $d$ by $2$ or $5$ . Such divisors can therefore not be relatively prime to $10$. Conversely, divisors with $r(d)\in \{1,3,7,9\}$ never leave the remainder $0$ when dividing by $2,5$. All primes except 2 and 5 are relatively prime to $10$ and therefore belong as divisors to the present topic. One can say that these are 40% of all positive numbers. In any case, that is an infinite number. The set ${\mathcal {D}}_{\perp 10}=\{d:d\in {\mathbb {N} },d\perp 10\}$ of such divisors is closed under multiplication and for $d\in {\mathcal {D}}_{\perp 10}$ a factorisation $d=f\cdot g$ is only possible if $f,g\in {\mathcal {D}}_{\perp 10}$ because each factor in turn can only have prime factors $p\notin \{2,5\}$. Such a factorisation does not have to be unique.

This article is a modified and translated version of a german version: de:Teilbarkeit für alle zu 10 teilerfremden Divisoren. The translation was done by the author of the german version.

Mathematical formalisation

Let be ${\mathbb {Z} },{\mathbb {R} }$ the set of integers respectively reals. Two functions are defined:

$\ell :\mathbb {Z} \to \mathbb {Z}$

$r:\mathbb {Z} \to \{0,1,\ldots ,9\}$

$\ell (n)=\left\lfloor {\frac {n}{10}}\right\rfloor$ Quotient of $n$ if divided with remainder by $10$

$r(n)=n-10\cdot \ell (n)$ Remainder of $n$ if divided by $10$

where $\lfloor x\rfloor$ is the largest integer $\leq x\in \mathbb {R}$. From definition of $r(n)$ follows immediately

$n=10\cdot \ell (n)+r(n)$.

(composition-dec)

Think of the pair $\langle \ell (n),r(n)\rangle$ as $\langle {\text{left part}},{\text{right part}}\rangle$ of $n$.

Both functions model the "remaining left-hand digits", "right-hand digit" in kind of transition.

A complete verbal description of the function $\ell$ is:

On the domain of definition $\mathbb {Z}$ the function $\ell$ is a monotonically increasing staircase function with $10$ consecutive identical values each. The jump points to a higher value are the multiples of $10$. The jump height is the value $1$ and it holds $\ell (0)=0$.

The monotonicity of $\ell$ follows almost directly from the monotonicity of the floor function $\lfloor \cdot \rfloor$ by the following chain of conclusions:

$n\leq m\Longrightarrow {\frac {n}{10}}\leq {\frac {m}{10}}\Longrightarrow \left\lfloor {\frac {n}{10}}\right\rfloor \leq \left\lfloor {\frac {m}{10}}\right\rfloor \Longrightarrow \ell (n)\leq \ell (m)$

(monotonicity-l())

Since by Division with remainder for any integer $n$ there is a representation $n=10\cdot \ell +r$ it results in

$\ell (10\cdot \ell +r)=\ell \quad \forall r\in \{0,1,\dots ,9\}$

and these are the $10$ consecutive identical values for fixed $\ell \in \mathbb {Z}$.

Example: l(−17) = −2 because $-2$ is the largest integer $\leq -{\frac {17}{10}}$ and $r(-17)=3$ because $-17=10\cdot (-2)+3$.

For nonnegative integers n the matter is more simple:

If $n=z_{k}z_{k-1}\cdots z_{1}z_{0}$ is the decimal representation of a nonnegative integer with digits $z_{i}\in \{0,1,\dots ,9\}$ then $\ell (n)=z_{k}z_{k-1}\cdots z_{1}$ where the right-hand digit $z_{0}$ is throwing away and $r(n)=z_{0}$,
$\ell (n)=0$ if $n=z_{0}$ is a single-digit nonnegative number.

Example: ℓ(27) = 2 because $2$ is the largest integer $\leq {\frac {27}{10}}$ and $r(27)=7$ because $27=10\cdot 2+7$.

For $n\in \mathbb {Z}$ there are the following conversions (based on the definitions):

$\ell (-n)={\begin{cases}-(\ell (n)+1)&{\text{if }}r(n)>0\\\ell (n)&{\text{if }}r(n)=0\end{cases}}$

(conversion-l())

$r(-n)={\begin{cases}10-r(n)&{\text{if }}r(n)>0\\0&{\text{if }}r(n)=0\end{cases}}$

(conversion-r())

The conversions work equally for nonnegative and negative $n$.

Partial sum of digits and divisibility

Test functions are now considered with a multiplier $m_{d}$ that has not yet been determined.

$\partial _{d}:\mathbb {Z} \to \mathbb {Z}$

$\partial _{d}(n)=\ell (n)+m_{d}\cdot r(n)$

This designation $m_{d}$ already indicates that for various divisors $d$ the multiplier $m_{d}$ is dependent on the divisor $d$, that means it is specialized on the divisor d.

Functions of this type are to be called partial sum of digits.

It is required of such a function that applies:

$n\in \mathbb {Z} \Rightarrow d\mid n\iff d\mid \partial _{d}(n)$

where $\iff$ means the logical "if and only if" relation. This is the meaning of divisibility criterion: The function $\partial _{d}$ transfers the truth value of the assertion $d\mid n$ unchanged to the truth value of the assertion $n\mid \partial _{d}(n)$, regardless of whether the assertion is true or false. The purpose of $\partial _{d}$ (apart from being a divisibility criterion) is to improve the recognisability of divisibility by d for a human user. An algorithm is now described which, given a divisor $d$, determines the multiplier $m_{d}$ and is even simple enough to be mental executable in one's head.

A comparable approach is used in Tests for divisibility by prime numbers, but in comparison to the to Mapping ${\color {blue}d\mapsto m_{d}}$ other multipliers are used.

Algorithm for determining the multiplier

To determine the multiplier $m_{d}$ from a given divisor $d\perp 10$ use following steps and prefer mental arithmetic in doing so:

1. Consider $e\in \{d,3\cdot d\}$ in this order and check if $r(e)\in \{1,9\}$.
2. Go to $e=3\cdot d$ only if this condition is not already fulfilled for $e=d$.
3. Set $m_{d}={\begin{cases}-(e-1)/10&{\text{if }}r(e)=1\\(e+1)/10&{\text{if }}r(e)=9\end{cases}}$

The division in step 3. is achievable without remainder. With this algorithm you end up with $r(e)\in \{1,9\}$ for $r(d)\in \{1,3,7,9\}$ at the latest for $e=3\cdot d$. This is based on the fact that for $r(d)\in \{3,7\}$ membership $r(3d)\in \{1,9\}$ is present because of $3\cdot 3=9,\;3\cdot 7=21$. The results of this algorithm are now presented as a table.

Table 1 Mapping $d\mapsto m_{d}$

$r(d)$	$1$	$3$	$7$	$9$
$m_{d}$	$-(d-1)/10$	$(3\cdot d+1)/10$	$-(3\cdot d-1)/10$	$(d+1)/10$
$m_{d}$	$-\ell (d)$	$3\cdot \ell (d)+1$	$-(3\cdot \ell (d)+2)$	$\ell (d)+1$

The values in the last row are alternative representation of the same values in the row above. This results from the following equations, where composition-dec $d=10\cdot \ell (d)+r(d)$ is throughout used for $n=d$:

${\begin{aligned}r(d)=1&\iff m_{d}=-(d-1)/10=-(10\cdot \ell (d)+1-1)/10=-\ell (d)\\r(d)=3&\iff m_{d}=(3\cdot d+1)/10=((3\cdot (10\cdot \ell (d)+3)+1)/10=3\cdot \ell (d)+10/10=3\cdot \ell (d)+1\\r(d)=7&\iff m_{d}=-(3\cdot d-1)/10=-(3\cdot (10\cdot \ell (d)+7)-1)/10=-(3\cdot \ell (d)+2)\\r(d)=9&\iff m_{d}=(d+1)/10=(10\cdot \ell (d)+9+1)/10=\ell (d)+1\end{aligned}}$

These alternative formulae use as means of expression throughout $\ell (d)$ and therefore offer advantages in mental arithmetic. In particular, the required multiplications with be applied to numbers with a smaller number of digits.

Now except $m_{d}$ another integer $k_{d}$ is brought into play with the aim of representing the so-called Bézout's identity for the greatest common divisor of $10,d$. For this purpose, the individual cases are analysed with reference to Mapping ${\color {blue}d\mapsto m_{d}}$.

${\begin{aligned}m_{d}&=-(d-1)/10&\iff 10\cdot m_{d}+1\cdot d=1\\m_{d}&=(3\cdot d+1)/10&\iff 10\cdot m_{d}-3\cdot d=1\\m_{d}&=-(3\cdot d-1)/10&\iff 10\cdot m_{d}+3\cdot d=1\\m_{d}&=(d+1)/10&\iff 10\cdot m_{d}-1\cdot d=1\end{aligned}}$

Let it be $k_{d}$ determined according to the following table, whose values are read off from the respective right identity as a factor before $d$.

Table 2 Mapping $d\mapsto k_{d}$

$r(d)$	$1$	$3$	$7$	$9$
$k_{d}$	$1$	$-3$	$3$	$-1$

One notes that the value of $k_{d}$ is an inevitable consequence of determining the value of $m_{d}$. Thus, the four right identities can be written uniformly in the following form:

$m_{d}\cdot 10+k_{d}\cdot d=1=(10,d){\text{ with }}k_{d}\in \{1,-3,3,-1\}$

(basic-equation)

This is the representation of the greatest common divisor (10, d) = 1 known from elementary number theory, also called Bézout's identity.

Theorem about divisibility and partial sum of digits

Theorem — Let $d>1$ be a divisor relative prime to $10$ and $m_{d}$ specified according to the Mapping ${\color {blue}d\mapsto m_{d}}$.

Then for the partial sum of digits $\partial _{d}(n)=\ell (n)+m_{d}\cdot r(n)$ applies:

$n\in \mathbb {Z} \Longrightarrow {\color {blue}d\mid n\iff d\mid \partial _{d}(n)}$

(divisibility-invariance)

Supplement:
Furthermore, if $d=f\cdot g$ is a product of two factors relatively prime to $10$, then for both divisors $e\in \{f,g\}$ applies divisibility-invariance: $n\in \mathbb {Z} \Longrightarrow {\color {blue}e\mid n\iff e\mid \partial _{d}(n)}$

With the statement divisibility-invariance , the test function $\partial _{d}$ specialized on the divisor d becomes a divisibility criterion that can also be used for testing divisibility mental in the head if, depending on the user, divisors d that are not too large come into play. It should also be noted that in some cases the test functions can also be identical for different ones divisors. This occurs systematically for $r(d)\in \{3,7\}$ because $\partial _{d}=\partial _{3\cdot d}$. Due to the relationship $\iff$ in divisibility-invariance, the test function $\partial _{d}$ can also be applied several times to results that have already been achieved without losing the property of divisibility/indivisibility. This may require increased memorisation by the user in mental arithmetic but it is part of the best practice for such divisibility tests. In any case, the user decides for himself when he considers the divisibility to be decided positively or negatively. The application of $\partial _{d}$ reduces the difficulty of recognising whether divisibility holds or not.
The supplement in the theorem means:

In case of $d=f\cdot g$ the partial sum of digits $\partial _{d}=\partial _{f\cdot g}$ is usable for three divisibility tasks: $d|n\;?,\;f|n\;?,\;g|n\;?$.

The divisibility-invariance represented by this theorem is also called Zbikowski’s Divisibility Criterion. and is dated there to the year 1861. See also Divisibility rule § Generalized divisibility rule.

Proof

The test value n can be expressed by $\partial _{d}(n),m_{d},k_{d},d,r(n)$ as follows, where composition-dec is used in the middle:

${\begin{aligned}\partial _{d}(n)&=\ell (n)+m_{d}\cdot r(n)\\\ell (n)&=(\partial _{d}(n)-m_{d}\cdot r(n))\\n&=10\cdot \ell (n)+r(n)\\n&=10\cdot {\bigl (}\partial (n)-m_{d}\cdot r(n){\bigr )}+r(n))\\n&=10\cdot \partial (n)-10\cdot m_{d}\cdot r(n)+r(n)\\n&=10\cdot \partial (n)-(m_{d}\cdot 10-1)\cdot r(n)\end{aligned}}$

$\;\,n=10\cdot \partial _{d}(n)+k_{d}\cdot d\cdot r(n)$

(1)

Here, the last equation 1 results from a suitable transformation of the basic-equation: $m_{d}\cdot 10+k_{d}\cdot d=1\iff -(m_{d}\cdot 10-1)=k_{d}\cdot d\cdot r(n)$.

With regard to equation 1, it can be argued as follows: The value n is a sum of two summands of which the second summand is a multiple of d. Therefore, divisibility is decided by the divisibility of the first summand:

$d\mid n\iff d\mid 10\cdot \partial _{d}(n)$

Finally because d is coprime to 10 it follows:

$d\mid n\iff d\mid \partial _{d}(n)$, which completes the proof(without the supplement).
To complete the proof in case of $d=f\cdot g$ equation 1 can be written in the form:

$n=10\cdot \partial _{d}(n)+k_{d}\cdot f\cdot g\cdot r(n)$

Here the second summand on the right-hand side is a multiple of $f$. It follows: $f\mid n\iff f\mid \partial _{d}(n)$ with the same argument as in the original case. Of course the same is valid for the second factor $g$ □.

Definition of iterations of partial sum of digits

For $i\in \mathbb {N} _{0}$ and fixed $n\in \mathbb {Z}$ following functions are introduced recursively :

$\partial _{d}^{i}\colon {\mathbb {Z} }\to {\mathbb {Z} }$

$\partial _{d}^{0}(n)=n$

$\partial _{d}^{i+1}(n)=\partial _{d}{\bigl (}\partial _{d}^{i}(n){\bigr )}$

These functions model the multiple nested application of $\partial _{d}$ to results of itself, for example is $\partial _{d}^{2}(n)=\partial _{d}{\bigl (}\partial _{d}(n){\bigr )}$. The value n is the initial value and $\partial _{d}^{i}(n)$ is the value of i-th iteration.

A concrete application is:

$\partial _{9}^{2}(123)=6$ because $\partial _{9}(123)=12+3=15$ and $\partial _{9}(15)=1+5=6$, where $m_{9}=1$ according to Mapping ${\color {blue}d\mapsto m_{d}}$. This is also a matter for mental calculation. The values $\partial _{d}^{0}(n),\partial _{d}^{1}(n),\dots ,\partial _{d}^{k}(n)$ , which are wandered through during mental divisibility arithmetic with several nested intermediate results, are called mental orbit for the divisibility task $d\mid n{\text{ ?}}$. Either one reaches a fixed point in such an orbit or one reach a permutation cycle. Ultimately, one must decide positively or negatively the divisibility task according to one's best judgement. As a rule, it turns out that the divisibility task is easier and easier to decide as the length of the orbit increases. Fortunately the divisibility property $d\mid n$ depends only from the last member $\partial _{d}^{k}(n)$ of the orbit. Therefore, a user does not have to remember the whole orbit.

See in Divisibility Tests Unified: Stacking the Trimmings for Sums the section Defining Divisibility Tests where the formalisation of iterations is also described together with some qualitative demands on the test function $f$ from which the iterations $f_{d}^{i}(n)$ are formed.

Application examples

Some examples for the mapping $d\mapsto m_{d}$

$d$	$3$	$7$	$9$	$11$	$13$	$17$	$19$	$23$	$29$	$31$	$33$	$39$	$41$	$43$	$49$	$59$	$71$	$77$	99	$251$	417
$m_{d}$	1	−2	1	−1	4	−5	2	7	3	−3	10	4	−4	13	5	6	−7	−23	10	−25	−125

Values in the second row are selected from Mapping ${\color {blue}d\mapsto m_{d}}$ respectively according to the algorithm for determining the multiplier $m_{d}$. This is also a matter for mental arithmetic. See also Divisibility Tests – Making Order out of Chaos for some of theses examples in section The Second Divisibility Test, Table 2.

Some examples for the application of partial sum of digits

$d$	$m_{d}$	$n$	$\partial _{d}(n)$	$\partial _{d}^{2}(n)$	$\partial _{d}^{3}(n)$
$19$	$2$	$233$	$23+2\cdot 3=29$
$19$	$2$	228	$22+2\cdot 8=38$	$3+2\cdot 8=19\checkmark$
$37$	$-11$	$851$	$85-11=74$	$7-11\cdot 4=-37\checkmark$
$23$	$7$	$851$	$85+7=92$	$9+7\cdot 2=23\checkmark$
$417$	$-125$	$10008$	$1000-125\cdot 8=0\;\checkmark$
$251$	$-25$	$-3432$	$344-25\cdot 8=-544$	$-55-25\cdot 6=-205$	$-21-25\cdot 6=-146$
$43$	$13$	$129$	$129$	$129$	$129\;\checkmark$

Values for $m_{d}$ are taken from Mapping ${\color {blue}d\mapsto m_{d}}$ and $\checkmark$ means divisibility $d|n$. Indivisibility in the row for $d=251$ follows from −251 < −205 < 0 and -251 < −146 < 0 . For negative test values $n$ conversion-r() and conversion-l() are to be applied. The last row reveals a difficulty. The test value $n=129$ does not change when $\partial _{43}$ is applied. Although $129$ is divisible by $43$, the application of $\partial _{43}$ does not result in any recognizable advantage. If the user does not realise by himself that $129=3\cdot 43$, he cannot gain any new knowledge on the divisibility question. The value $129$ is therefore called a fixed point of $\partial _{43}$. Without proof, it should be noted that the integers $n\in \{0,43,86,129\}$ are exactly the fix points of $\partial _{43}$.

The fix point brake

This constellation is to be described here in a metaphor as a fix point brake. The fix point hinders the user in recognising divisibility. Fortunately, there is a possibility to release the brake. Consider making the transition $n\curvearrowright -n$. Then it turns out that −n is not a fixed point and the test function recognises −n as divisible by $d$. For $n=129$ this leads to:

$\partial _{43}(-129)=-13+1\cdot 13=0$ where conversion-r() and conversion-l() are to be applied.

Therefore $43|0$ and by divisibility-invariance follows $43\mid -129$. Finally there is the general valid assertion $d\mid n\iff d|-n$, which leads to $43|129$. The same applies to $n=86$:

$\partial _{43}(-86)=-9+4\cdot 13=43\checkmark$ Therefore finally $43\mid -86$ and $43\mid 86$ , which is easily recognisable even without applying $\partial _{43}$. The same constellation occurs for all divisors $d\in \{3,13,23,\dots \}\cup \{7,17,27,\dots \}$ (with the same possibility to release the fix point brake) but this is not to be explained in detail here.

The diagram for releasing the fix point brake:

${\begin{array}{lcl}&d\mid n{\text{?}}&\longrightarrow &\partial _{d}(n)=n{\text{??}}&\\&\checkmark \uparrow &&\downarrow \\&d\mid \partial _{d}(-n)\checkmark &\longleftarrow &d\mid \partial _{d}(-n){\text{?}}&\\\end{array}}$

Examples for the supplement in Theorem about divisibility

Some examples for the application of the supplement

$d$	$m_{d}$	$n$	$\partial _{d}(n)$	$\partial _{d}^{2}(n)$	divisibility decision
$119=7\cdot 17$	$12$	$578={\color {red}17}\cdot 34$	$57+12\cdot 8=153$	$15+12\cdot 3=51\;\checkmark$	$17\mid 578\;\checkmark$
$119=7\cdot 17$	$12$	$238={\color {red}7}\cdot 34$	$23+12\cdot 8=119\;\checkmark$		$7\mid 238\;\checkmark$
$351=3\cdot 117$	$-35$	$381={\color {red}3}\cdot 127$	$38-35\cdot 1=3\;\checkmark$		$3\mid 381\;\checkmark$
$351=3\cdot 117$	$-35$	$234=2\cdot \color {red}{117}$	$23-35\cdot 4=-117\;\checkmark$		$117\mid 234\;\checkmark$
$351=13\cdot 27$	$-35$	$91=7\cdot \color {red}{13}$	$9-35\cdot 1=-26\;\checkmark$		$13\mid 91\;\checkmark$
$351=13\cdot 27$	$-35$	$189=7\cdot \color {red}{27}$	$18-35\cdot 9=-297$	$-30-35\cdot 3=-135\;\checkmark$	$27|189\;\checkmark$
$351=9\cdot 39$	$-35$	$273=7\cdot \color {red}{39}$	$27-35\cdot 3=-78\;\checkmark$		$39\mid 273\;\checkmark$
$351=9\cdot 39$	$-35$	$171={\color {red}9}\cdot 19$	$17-35\cdot 1=-18\;\checkmark$		$9\mid 171\;\checkmark$

Relations to sum of digits

The well known decimal cross sum , also called total sum of digits, sum of digits of a nonnegative number $n=z_{k}z_{k-1}\cdots z_{1}z_{0}$, written as decimal representation with digits $z_{i}\in \{0,\ldots ,9\}$ is the value

$C(n)=\sum _{i=0}^{k}z_{i}=z_{0}+z_{1}+\cdots +z_{k-1}+z_{k}$

In comparison, $\partial _{9}$ looks (according to $m_{9}=1$) like this:

$\partial _{9}(n)=\ell (n)+z_{0}=(z_{k}z_{k-1}\cdots z_{1})+z_{0}$

where the sum of the digits is only partially executed. This motivates the naming of partial sum of digits for all functions $\partial _{d}$.

The function $C$ is a divisibility criterion for $d\in \{3,9\}$ and both are relative prime to $10$. For the total sum of digits $C$ as well as for $\partial _{9}$ one can iteratively apply the operation to all intermediate results. This only leads to new results as long as the previously achieved result is not a decimal single-digit number. From then on, the total sum of digits and the value of $\partial _{9}$ remain constant. It can also be proved elementarily that the final single-digit results are identical, although intermediate results usually differ for cross sum and $\partial _{9}$. The final single-digit result is also called digital root.

For example $\partial _{9}(1237)=123+7=130$, and $C(1237)=1+2+3+7=13$. If one iteratively applies these intermediate results several more times, the final result in both cases is $4$. Therefore $1237$ is not divisible by $9$.

Note finally the congruences for all $n\in {\mathbb {Z} }$:

$n\equiv C(n){\pmod {9}}$ and $n\equiv \partial _{9}(n){\pmod {9}}$. These are well known for the cross sum $C$ and also valid for $\partial _{9}$ because $n-\partial _{9}(n)=10\cdot \ell (n)+r(n)-(\ell (n)+r(n))=9\cdot \ell (n)$.

The advantage of the cross sum over $\partial _{9}$ is that the cross sum reaches the single-digit results with fewer steps.

The role of m_d in residue class ring ℤ/dℤ

If basic-equation is written in the form $m_{d}\cdot 10-1=-k_{d}\cdot d$, one can see that $m_{d}\cdot 10-1$ is a multiple of $d$. As a congruence this means

$m_{d}\cdot 10\equiv 1{\pmod {d}}$

Therefore, in ℤ/dℤ the residue class $[m_{d}]$ of $m_{d}$ is the inverse of $[10]$ . It holds $[m_{d}]\times [10]=[1]$, thus $[m_{d}]=[10]^{-1}$. It is well known in elementary number theory, that the coefficients $m_{d},k_{d}$ in the basic-equation can be calculated by the Extended Euclidean algorithm. Surprisingly, it turns out that this algorithm gives the same results as the Algorithm for determining the multiplier. Because the coefficients are not unique determined by $10,d$ they can be modified as described in Bézout's_identity. For instance $m_{d}$ can be replaced by any other member ${\widehat {m}}$ from the same residue class $[m_{d}]$. However, this only guarantees the preservation of divisibility-invariance for the modified test function ${\widehat {\partial }}_{d}(n)=l(n)={\widehat {m}}\cdot r(n)$. An example for such a replacement is the transition $m_{d}\curvearrowright m_{d}+d$. For $d=7$ this results in the modified test function ${\widehat {\partial }}_{7}(n)=\ell (n)+5\cdot r(n)$ because $m_{7}=-2$ is mapped to $-2+7=5$. Obviously, the modified test function for positive values exclusively also yields positive values, which is invalid for the original function $\partial _{7}$. But although ${\widehat {\partial }}_{7}(476)=47+5\times 6=47+30=77$, which differs from $\partial _{7}(476)=35$; nevertheless both results are divisible by $7$: $\quad 7\mid 35\checkmark$ and $7\mid 77\checkmark$. But a replacement $m_{d}\curvearrowright {\widehat {m}}$ would change the permutation property. It is already evident from the example that this does not introduce any new divisibility criteria into the realm of partial sums of digits, because ${\widehat {\partial }}_{7}=\partial _{7\cdot 7}=\partial _{49}$. However, comprehensive conversion formulae of this kind are dispensed with here.

Simple Divisibility Rules for the 1st 1000 Prime Numbers lists divisibility tests for the first 1000 prime numbers, built on the pattern of partial digit sums. Only concrete prime divisors and multipliers are listed. The multipliers there can be described by the following relations: ${\widehat {m}}_{d}={\begin{cases}m_{d}&{\text{if }}m_{d}<0\\m_{d}-d&{\text{if }}m_{d}>0\end{cases}}$

It follows that all listed multipliers are negativ and belong to the residue class $[m_{d}]$.

Example(the last prime listed): $d=7919,\;{\widehat {m}}_{d}=-7127,\;m_{d}=792,\;m_{d}-d=792-7919=-7127$

Partial sum of digits as permutations

If for $d\in \{9,19,29,\dots \}$ the function $\partial _{d}$ is considered on the restricted domain of definition $\{0,1,\dots ,d\}$ the result is a permutation. This is justified by use of $m_{d}=\ell (d)+1$in last row in Mapping ${\color {blue}d\mapsto m_{d}}$ and by monotonicity-l() as follows.

Let be $n\in \{0,1,\dots ,d\}$. Then $0\leq \ell (n)\leq \ell (d)$ and $0\leq r(n)\leq 9$ leads to: ${\begin{aligned}0&\leq \partial _{d}(n)=\ell (n)+m_{d}\cdot r(n)\leq \ell (d)+m_{d}\cdot 9=\ell (d)+(\ell (d)+1)\cdot 9=10\cdot \ell (d)+9\\0&\leq \partial _{d}(n)\leq d\end{aligned}}$

because $10\cdot \ell (d)+9=d$ according to composition-dec.

Therefore, $\partial _{d}$ maps $\{0,1,\dots ,d\}$ into itself. To check whether $\partial _{d}$ is injective, consider two elements $n,m\in \{0,1,\dots ,d\}$ and assume $\partial _{d}(n)=\partial _{d}(m)$. Then it can be assumed without restriction of generality that $\ell (m)\geq \ell (n)$ and we can conclude:

${\begin{aligned}\ell (m)+m_{d}\cdot r(n)-(\ell (n)+m_{d}\cdot r(n))&=\ell (m)-\ell (n)+m_{d}\cdot (r(n)-r(m))\\\ell (m)-\ell (n)&=m_{d}\cdot (r(n)-r(m))\end{aligned}}$

From this it can be seen that $\ell (m)-\ell (n)$ is a nonnegative multiple of $m_{d}$. Since $\ell$ is monotonally increasing both values $\ell (m),\ell (n)$ are $\leq \ell (d)=m_{d}-1$. This yields $\ell (m)-\ell (n)\in \{0,1,\dots ,m_{d}-1\}$. Because the value $0$ is the only multiple of $m_{d}$ in this domain, it follows: $\ell (m)-\ell (n)=0$ and also $\ell (m)=\ell (n)$. Finally $m_{d}\cdot (r(n)-r(m))=0$ and $r(n)=r(m)$ because $m_{d}\neq 0$.Then composition-dec yields:

$n=10\cdot \ell (n)+r(n)=10\cdot \ell (m)+r(m)=m$ and hence $n=m$

Therefore is $\partial _{d}$ injective and in fact bijective because the domain $\{0,1,\dots ,d\}$ is a finite set. That means: $\partial _{d}$ is a permutation on the restricted domain $\{0,1,\dots ,d\}$. It can be seen that $0,d$ are fixed points of $\partial _{d}$: ${\begin{aligned}\partial _{d}(d)&=\ell (d)+m_{d}\cdot 9=\ell (d)+(\ell (d)+1)\cdot 9=10\cdot \ell (d)+9\\\partial _{d}(d)&=d\\\partial _{d}(0)&=0\end{aligned}}$

where for $\partial _{d}(d)$ the multiplier $m_{d}=\ell (d)+1$ is read from (last row,last column) of Mapping ${\color {blue}d\mapsto m_{d}}$. It follows that $\partial _{d}$ is also a permutation on $\{1,2,\dots ,d-1\}$. We consider $d=19$ with $m_{19}=2$ as an example: ${\tilde {\partial }}_{19}\!=\!{\begin{pmatrix}0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\0&2&4&6&8&10&12&14&16&18&1&3&5&7&9&11&13&15&17&19\end{pmatrix}}$

where ${\tilde {\partial }}_{19}$ is used to distinguish the permutation from the partial sum of digits $\partial _{19}$.

For $d=9,\;m_{9}=1$ the result is the identity on $\{0,1,\dots ,9\}$:

${\tilde {\partial }}_{9}={\begin{pmatrix}0&1&2&3&4&5&6&7&8&9\\0&1&2&3&4&5&6&7&8&9\end{pmatrix}}$

Without detailed elaboration, it may be mentioned that $\partial _{d}$ for $d\in \{11,21,31,\dots \}$ also determines a permutation on domain $\{-d,-(d-1),\dots ,-1,0\}$ equally denoted by ${\tilde {\partial }}_{d}$. Because $-d,0$ are fixpoints, this is also a permutation on domain of definition $\{-(d-1),\dots ,-1\}$. An example is given for $d=11,\;m_{11}=-1$:

${\tilde {\partial }}_{11}={\begin{pmatrix}-11&-10&-9&-8&-7&-6&-5&-4&-3&-2&-1&0\\-11&-1&-2&-3&-4&-5&-6&-7&-8&-9&-10&0\end{pmatrix}}$

For negative values conversion-r() and conversion-l() are to be applied. These background knowledge about permutations is meaningful for mental calculations with partial sums of digits, to interpret results appropriate with respect to divisibility. The permutation ${\tilde {\partial }}_{d}$ can also contain fixpoints $\notin \{0,d\}$ respectively $\notin \{-d,0\}$. With $d=99,m_{99}=10$ one can easily calculate that the set $\{0,11,22,33,44,55,66,77,88,99\}$ consists of fix points of $\partial _{99}$ but all elements $n\in \{1,2,\dots ,98\}$, including the fix points contained therein, are not divisible by $99$. This is for $d\in \{11,21,31,\dots \}\cup \{9,19,29,\dots \}$ a general insight: The inner elements of the domain of definition are to be classified as not divisible. A user can easily decide this according to the criterion $0<|n|<d$ where $|n|$ denotes the absolute value of $n$.

For $d\in \{3,13,23,\dots \}\cup \{7,17,27,\dots \}$ there is also a permutation but with respect to $\partial _{d}=\partial _{3\cdot d}$ where the domain of definition is determined by $3\cdot d$:

${\mathcal {D}}({\tilde {\partial }}_{d})={\begin{cases}\{-3\cdot d,-(3\cdot d-1),\dots ,-1,0\}&{\text{ if }}d\in \{7,17,27,\dots \}\\\{0,1,\dots ,3\cdot d\}&{\text{if }}d\in \{3,13,23,\dots \}\end{cases}}$

Consideration these domains of definition requires additional attention from the user.

If the mental arithmetic chain reaches the domain of such a permutation, it is possible to decide the divisibility task $d\mid n{\text{ ?}}$ (positively or negatively); not only for $d\in \{3,13,23,\dots \}\cup \{7,17,27,\dots \}$ but for all $d\perp 10$. Let be ${\tilde {n}}=\partial _{d}^{k}(n)$ the actual value in the (mental) calculation chain for a divisibility task $d\mid n{\text{ ?}}$. Typical final states that allow a decision of divisibility are:

Final states and divisibility decision

$Value$	Condition	Divisibility decision
${\tilde {n}}$	$\color {Green}{{\tilde {n}}\in \{-d,0,d\}}$	$d$ divides $n$
${\tilde {n}}$	$\color {Red}{0<|{\tilde {n}}|<d}$	$d$ does not divide $n$

At least for $d\in \{11,21,31,\dots \}\cup \{9,19,29\dots \}$ the condition in the last row describes the state where ${\tilde {n}}$ has reached the domain of the permutation ${\tilde {\partial }}_{d}$. For $d\in \{3,13,23,\dots \}\cup \{7,17,27\}$ the matter is not quite so simple because the Fix point brake has to be taken into account.

Relationships between sets of divisors

On the basis of following relations and in view of Mapping ${\color {blue}d\mapsto m_{d}}$ we have:

${\begin{aligned}d&\in \{3,13,23,\dots \}\Rightarrow 3\cdot d\in \{9,19,29,\dots \}\Rightarrow m_{d}=m_{3\cdot d}>0\\d&\in \{7,17,27,\dots \}\Rightarrow 3\cdot d\in \{11,21,31,\dots \}\Rightarrow m_{d}=m_{3\cdot d}<0\end{aligned}}$

This results in $m_{d}=m_{3\cdot d}$ for $d\in \{3,13,23,\dots \}\cup \{7,17,27,\dots \}$. Since $\partial _{d}$ depends with respect to $d$ only by $m_{d}$, the partial sum of digits $\partial _{d}$ and $\partial _{3\cdot d}$ coincide as functions. This means: Properties of $\partial _{d}$ that depend only on $m_{d}$ are equally valid for $d,3\cdot d$. The definition range of the permutation ${\tilde {\partial }}_{d}$ is such a property. This range is determined by $3\cdot d$.

All partial digit sum functions are enumerated in the sequence:

$\partial _{9},\partial _{11},\partial _{19},\partial _{21},\partial _{29},\partial _{31},\partial _{39},\partial _{41},\partial _{49},\partial _{51},\dots$

and despite different designations the following sequence is a subsequence of the first one.

$\partial _{3},\partial _{7},\partial _{13},\partial _{17},\partial _{23},\partial _{27}\dots$

For instance $\partial _{7}$ from the second sequence appears as $\partial _{21}$ in the first sequence in the sense of equality of functions and $\partial _{17}$ appears equally as $\partial _{51}$. But one should bear in mind that divisibility by $d$ is different from divisibility by $3\cdot d$. This is not a contradiction to the equation $\partial _{d}=\partial _{3\cdot d}$. For example, if $d<\partial _{d}(n)\leq 3\cdot d$ turns out to be true, it may be that $d$ divides $\partial _{d}(n)$ but $3\cdot d$ doesn't divide $\partial _{d}(n)$. See as an example $d=13,3\cdot d=39,n=26$ where $\partial _{13}(26)=26$ and $13$ divides $26$ but $39$ does not divide $26$. The divisibility property $d|n$ depends not only from $m_{d}$, because $d,n$ are both involved.

Furthermore, it follows from supplement in Theorem about divisibility that for fixed $d\in \{9,11,19,21,29,31,\dots \}$ all partial sum of digits in the family

$(\partial _{d\cdot g})_{g\in {\mathcal {D}}_{\perp 10}}$

are usable to solve the divisibility task $d\mid n{\text{?}}$

The divisibility task $7\mid n{\text{?}}$ together with a text description of the solution corresponding to $\partial _{7}$ is described in An Introduction to theTheory of Numbers..

References

This article "Divisibility for all divisors relative prime to 10" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Divisibility for all divisors relative prime to 10. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Term grouping criteria
• Dubner's conjecture
• List of positive integers and factors 8001 to 10,000
• List of positive integers and factors 2001 to 4000
• List of positive integers and factors/4
• Integer
• On the Residue Classes of Real Numbers and Its Topological Properties

---