Divisibility for all of 10 prime divisors

Divisibility for all 10 prime divisors is a method for checking the divisibility of a number for all 10 prime divisors.

description

A method for checking the divisibility of a number for all 10 prime divisors is described and mathematically justified. The method has two advantages. Once it works for all of the named factors. Second, it also provides guidance on how to determine the required multiplier in your head. Divisors are considered that have no common divisors with the natural number . 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 to be tested . The claim that is divisible by is expressed by. An example is given . The sub-prime of is expressed by. The greatest common factor of is denoted by. Divisibility criteria of the following kind are considered: ${\displaystyle m_{d}}$ ${\displaystyle d\in {\mathbb {N} }}$ ${\displaystyle 10}$ ${\displaystyle n\in {\mathbb {N} }_{0}}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle d|n}$ ${\displaystyle 7|476}$ ${\displaystyle m\;,n}$ ${\displaystyle m\perp n}$ ${\displaystyle n,m}$ ${\displaystyle (n,m)}$

Multiply the right digit of the number to be tested by a multiplier and add the result to the number formed from the remaining left digits. ${\displaystyle n}$ ${\displaystyle m}$

The divisor is suitable. In the example it results and therefore applies . ${\displaystyle 7}$ ${\displaystyle m=-2}$ ${\displaystyle 47-2*6=47-12=35}$ ${\displaystyle 7|476}$

Such a divisibility test contains a human component. The user decides at his own discretion when to consider the divisibility to be examined as positive or negative. Such a decision would probably not be entrusted to a computer.

First let us characterize the divisors that are coprime too . Let it be the value of the right digit of . Then is coprime to if and only if is. As a justification, it should be mentioned that the other possible right-hand digits would result in the divisibility by or . Such factors cannot therefore be relatively prime . Conversely, divisors with never pass the remainder through the division . The divisibility tests described here are not suitable for or multiples thereof. All other prime numbers are also prime and therefore belong to the present topic. ${\displaystyle 10}$ ${\displaystyle r(d)}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle 10}$ ${\displaystyle r(d)\in \{1,3,7,9\}}$ ${\displaystyle r(d)\in \{0,2,4,5,6,8\}}$ ${\displaystyle d}$ ${\displaystyle 2}$ ${\displaystyle 5}$ ${\displaystyle 10}$ ${\displaystyle d}$ ${\displaystyle r(d)\in \{1,3,7,9\}}$ ${\displaystyle 0}$ ${\displaystyle 2\;,5}$ ${\displaystyle d\in \{2,5\}}$ ${\displaystyle \in \{3,7,11,13,17,19,\dots \}}$ ${\displaystyle 10}$

Mathematical formalization

The following two functions are defined: ${\displaystyle l,r:{\mathbb {N} }_{0}\to {\mathbb {N} }_{0}}$

${\displaystyle r(n)=mod(n,10)}$Remainder from when dividing through ${\displaystyle n}$ ${\displaystyle 10}$

${\displaystyle l(n)=(n-r(n))/10}$ The left part of ${\displaystyle n}$

It applies and the division can be carried out without a remainder. It always applies . If decimal is one-digit, then applies . The following applies in the example . There are now test functions ${\displaystyle r(n)\in \{0,1,2,3,4,5,6,7,8,9\}}$ ${\displaystyle (n-r(n))/10}$ ${\displaystyle n=10*l(n)+r(n)}$ ${\displaystyle n}$ ${\displaystyle l(n)=0}$ ${\displaystyle n=476}$ ${\displaystyle r(476)=6\;,l(476)=47\;,476=10*47+6}$

${\displaystyle \partial _{d}:{\mathbb {N} }_{0}\to {\mathbb {Z} }}$

${\displaystyle \partial _{d}(n)=l(n)+m_{d}*r(n)}$ considered with a multiplier that has not yet been determined . To be hinted at by this notation that for different divisors of the multiplier from the divisor is dependent, is thus dedicated to the divisor. For reasons that will be mentioned later, functions of the type partial digit sums should be named. Such a function requires that: ${\displaystyle m_{d}\in {\mathbb {Z} }\;,m_{d}\neq 0}$ ${\displaystyle d}$ ${\displaystyle m_{d}}$ ${\displaystyle d}$ ${\displaystyle \partial _{d}}$

${\displaystyle d|n\iff d|\partial _{d}(n)\;\forall n\in {\mathbb {N} }_{0}}$

where the logical -exactly if- relationship means. An algorithm will now be described which, for a given divisor, determines the multiplier and is even so simple that it can be executed in the head. ${\displaystyle \iff }$ ${\displaystyle d}$ ${\displaystyle m_{d}}$

1. Look in this order and see if it is. ${\displaystyle e\in \{d\;,3*d\}}$ ${\displaystyle r(e)\in \{1,9\}}$
2. Only go to if this condition is not already met at . ${\displaystyle e=3*d}$ ${\displaystyle e=d}$
3. Sit if it's here ${\displaystyle m_{d}=-(e-1)/10}$ ${\displaystyle r(e)=1}$ ${\displaystyle m_{d}<0}$
4. Sit if it's here ${\displaystyle m_{d}=(e+1)/10}$ ${\displaystyle r(e)=9}$ ${\displaystyle m_{d}>0}$

One can realize that one of the latest when in lands. This is because in true due . The results of this algorithm are now shown as a table. ${\displaystyle r(d)\in \{1,3,7,9\}}$ ${\displaystyle e=3*d}$ ${\displaystyle r(e)\in \{1,9\}}$ ${\displaystyle r(d)\in \{3,7\}}$ ${\displaystyle r(3*d)\in \{9,1\}}$ ${\displaystyle 3*3=9\;,3*7=21}$

Table 1 Results for the above algorithm ${\displaystyle d\mapsto m_{d}}$

${\displaystyle r(d)}$	${\displaystyle 1}$	${\displaystyle 3}$	${\displaystyle 7}$	${\displaystyle 9}$
${\displaystyle m_{d}}$	${\displaystyle -(d-1)/10}$	${\displaystyle (3*d+1)/10}$	${\displaystyle -(3*d-1)/10}$	${\displaystyle (d+1)/10}$

It is out of yet another integer into play, with the aim of the so-called Bézout identity for the greatest common divisor display. For this purpose, the individual cases are analyzed with reference to the table above. ${\displaystyle m_{d}}$ ${\displaystyle k_{d}}$ ${\displaystyle (10,d)=1}$ ${\displaystyle r(d)\in \{1,3,7,9\}}$

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

It is determined according to the following table, the values ​​of which are read from the respective right identity as a factor . ${\displaystyle k_{d}}$ ${\displaystyle d}$

Table 2 results for ${\displaystyle d\mapsto k_{d}}$

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

This means that the four right identities can be written uniformly in the following form:

${\displaystyle m_{d}*10+k_{d}*d=1}$ With ${\displaystyle k_{d}\in \{1,-3,3,-1\}}$

This is the representation of the greatest common divisor known from elementary number theory in , which is also called the Bézout identity . ${\displaystyle {\mathbb {Z} }}$ ${\displaystyle (10,d)=1}$

Theorem about partial sums of digits

It should and by Table-1 set. Then for the function of the statement . ${\displaystyle d\in {\mathbb {N} }\;,d>1\;,d\perp 10}$ ${\displaystyle m_{d}}$ ${\displaystyle \partial _{d}:{\mathbb {N} }_{0}\to {\mathbb {Z} },\quad \partial _{d}(n)=l(n)+m_{d}*r(n)}$ ${\displaystyle d|n\iff d|\partial _{d}(n)\;\forall n\in {\mathbb {N} }_{0}}$

With this statement, the test function specialized in the divisor becomes a divisibility criterion that can also be used to test divisibility in the head, if, depending on the user, divisors that are not too large are involved. It should also be noted that the test functions can in some cases also be identical for different ones. This occurs z. B. for on. Because of the relationship, the test function can also be applied several times to intermediate results that have already been achieved. This may require increased memory on the part of the user when doing mental arithmetic. In these cases the result can be negative. Then the test function cannot be used again on the intermediate result achieved. Nevertheless, the user can try to decide whether it is divisible by . In any case, the user himself decides when to consider divisibility as positive or negative. The use of reduces the difficulty of recognizing whether or not it is divisible. A proof sketch for the theorem about partial digit sums looks like this: ${\displaystyle d}$ ${\displaystyle \partial _{d}}$ ${\displaystyle d}$ ${\displaystyle r(d)=3}$ ${\displaystyle \iff }$ ${\displaystyle r(d)\in \{1,7\}}$ ${\displaystyle d}$ ${\displaystyle \partial _{d}}$

The value to be tested can be reconstructed from the values in the following way: ${\displaystyle n}$ ${\displaystyle d\!,\partial _{d}(n)\;,m_{d}\;,r(n)}$

${\displaystyle {\begin{aligned}\partial _{d}(n)&=l(n)+m_{d}*r(n)\\l(n)&=(\partial _{d}(n)-m_{d}*r(n))\\n&=10*l(n)+r(n)\\n&=10*{\bigl (}\partial (n)-m_{d}*r(n){\bigr )}+r(n))\\n&=10*\partial (n)-10*m_{d}*r(n)+r(n)\\n&=10*\partial (n)-(m_{d}*10-1)*r(n)\\n&=10*\partial _{d}(n)+k_{d}*d*r(n)\\n&=k_{d}*d*r(n)+10*\partial _{d}(n)\end{aligned}}}$

The penultimate equation results from a suitable equivalent transformation of the Bézout identity in the form . Looking at the last equation, the following can be argued: The value is a sum of two summands, of which the first summand is a multiple of . Therefore, the divisibility is determined by the divisibility of the second summand. It results: ${\displaystyle m_{d}*10+k_{d}*d=1\iff -(m_{d}*10-1)=k_{d}*d}$ ${\displaystyle n}$ ${\displaystyle d}$

${\displaystyle d|n\iff d|10*\partial _{d}(n)}$

Since are coprime, we get: ${\displaystyle d,10}$

${\displaystyle d|n\iff d|\partial _{d}(n)}$

It should also be noted that in the Bézout identity the coefficients vor are by no means uniquely determined. The factor can be replaced by any other factor from the same remaining class if the factor is still suitably adjusted. Since only the factor is included in the construction of , this can be done easily. In this case one reads from Table-1 . If one forms now , then is also suitable as a test criterion for the divisibility by . With regard to mental arithmetic, it is advisable not to choose the factor too far from . This is automatically guaranteed if the algorithm is used as described above. If one forms , the result is negative and is not defined. It is therefore impossible to improve the intermediate result again. The mental arithmetic user recognizes immediately that and decides the divisibility positively. Finally, it should be mentioned that is. This can be seen directly from Table-1 . Usually does not have the same remainder when dividing by as . This only applies if it is really divisible. In the special case , however, the remainder are retained even if they are not divisible. With respect to the radicals can be derived only in the last equation in the above equation chain that residues of and match: . ${\displaystyle 10\;,d}$ ${\displaystyle m_{d}}$ ${\displaystyle m}$ ${\displaystyle {\pmod {d}}}$ ${\displaystyle k_{d}}$ ${\displaystyle \partial _{d}}$ ${\displaystyle m_{d}}$ ${\displaystyle d=7}$ ${\displaystyle m_{d}=-2}$ ${\displaystyle m=-2+7=5}$ ${\displaystyle t(n)=l(n)+5*r(n)}$ ${\displaystyle 7}$ ${\displaystyle m}$ ${\displaystyle 0\in {\mathbb {Z} }}$ ${\displaystyle m_{d}}$ ${\displaystyle \partial _{7}(7)=l(7)-2*r(7)=0-2*7=-7}$ ${\displaystyle \partial _{7}(-7)}$ ${\displaystyle 7|-7}$ ${\displaystyle \partial _{3}=\partial _{9}}$ ${\displaystyle \partial _{d}(n)}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle d=9}$ ${\displaystyle n}$ ${\displaystyle 10*\partial _{d}(n)}$ ${\displaystyle 10*\partial _{d}(n)\equiv n{\pmod {d}}}$

The role of in the residual class ring ${\displaystyle m_{d}}$ ${\displaystyle {\mathbb {Z} }/d{\mathbb {Z} }}$

If the Bézout identity is written in the form , one recognizes that is a multiple of . As congruence, that means ${\displaystyle m_{d}*10-1=-k_{d}*d}$ ${\displaystyle m_{d}*10-1}$ ${\displaystyle d}$

${\displaystyle m_{d}*10\equiv 1{\pmod {d}}}$

Therefore, in the remaining classes of the inverse of . It is so . ${\displaystyle {\mathbb {Z} }/d{\mathbb {Z} }}$ ${\displaystyle [m_{d}]}$ ${\displaystyle m_{d}}$ ${\displaystyle [10]}$ ${\displaystyle [m_{d}]*[10]=[1]}$ ${\displaystyle [m_{d}]=[10]^{-1}}$

Relationship to the checksum

In this case one reads from Table-1 . Therefore: ${\displaystyle d=9}$ ${\displaystyle m_{d}=1}$

${\displaystyle \partial _{9}(n)=l(n)+r(n)}$

and only the last digit of is added to the left part . If you compare this with the checksum of , in which all decimal digits are added, you can see that the checksum is, so to speak, only partially formed. Therefore, here for all dividers mentioned the term partial sum of digits for use. The operation can be iteratively applied to all intermediate results both with the checksum and with . This only leads to new results as long as the previously achieved result is not a single-digit decimal. From then on, the checksum and remain constant. It can also be proven in elementary terms that the final single-digit results are identical, although intermediate results usually differ for checksums and . For example is and the checksum is . If one applies iteratively several times to these intermediate results, the end result is obtained in both cases . Therefore is not divisible by . ${\displaystyle n}$ ${\displaystyle l(n)}$ ${\displaystyle n}$ ${\displaystyle \partial _{9}(n)}$ ${\displaystyle \partial _{d}}$ ${\displaystyle \partial _{9}}$ ${\displaystyle \partial _{9}}$ ${\displaystyle \partial _{9}}$ ${\displaystyle \partial _{9}(1237)=123+7=130}$ ${\displaystyle q(1237)=1+2+3+7=13}$ ${\displaystyle \partial _{9}\;,q}$ ${\displaystyle 4}$ ${\displaystyle 1237}$ ${\displaystyle 9}$ ${\displaystyle 9\nmid 1237}$

Further application examples

For is according to Table-1 and . So is not divisible by. Against it . Therefore applies . ${\displaystyle d=19}$ ${\displaystyle m_{d}=2}$ ${\displaystyle \partial _{19}(233)=23+2*3=29}$ ${\displaystyle 233}$ ${\displaystyle 19}$ ${\displaystyle \partial _{19}(228)=22+2*8=22+16=38,\quad \partial _{19}(38)=3+2*8=19}$ ${\displaystyle 19|228}$

It should also be noted that there are problematic use cases. Such occur z. B. systematically for on. Be . For this one reads from Table-1 . For results . Although it is divisible by , there is no discernible benefit from using . If the user does not recognize for himself that is, he cannot gain any new knowledge on the question of divisibility . The value is therefore a fixed point of . ${\displaystyle r(d)=3}$ ${\displaystyle d=43}$ ${\displaystyle m_{d}=13}$ ${\displaystyle n=129}$ ${\displaystyle \partial _{43}(129)=12+13*9=12+117=129}$ ${\displaystyle 129=3*43}$ ${\displaystyle 43}$ ${\displaystyle \partial _{43}(129)}$ ${\displaystyle 129=3*43}$ ${\displaystyle 43|129?}$ ${\displaystyle 129}$ ${\displaystyle \partial _{43}}$

Without proof it is noted that the whole numbers are exactly the fixed points of . An analogous statement applies to all divisors . ${\displaystyle n\in \{0,43,86,129\}}$ ${\displaystyle \partial _{43}}$ ${\displaystyle d\;,3\nmid d\;,r(d)=3\;,d\perp 10}$

Table 3 Examples for the assignment ${\displaystyle d\mapsto m_{d}}$

${\displaystyle d}$	${\displaystyle 3}$	${\displaystyle 7}$	${\displaystyle 9}$	${\displaystyle 11}$	${\displaystyle 13}$	${\displaystyle 17}$	${\displaystyle 19}$	${\displaystyle 23}$	${\displaystyle 29}$	${\displaystyle 31}$	${\displaystyle 33}$	${\displaystyle 39}$	${\displaystyle 41}$	${\displaystyle 43}$	${\displaystyle 47}$	${\displaystyle 49}$	${\displaystyle 59}$	${\displaystyle 69}$	${\displaystyle 71}$	${\displaystyle 73}$	${\displaystyle 79}$	${\displaystyle 89}$	${\displaystyle 99}$
${\displaystyle m_{d}}$	${\displaystyle 1}$	${\displaystyle -2}$	${\displaystyle 1}$	${\displaystyle -1}$	${\displaystyle 4}$	${\displaystyle -5}$	${\displaystyle 2}$	${\displaystyle 7}$	${\displaystyle 3}$	${\displaystyle -3}$	${\displaystyle 10}$	${\displaystyle 4}$	${\displaystyle -4}$	${\displaystyle 13}$	${\displaystyle -14}$	${\displaystyle 5}$	${\displaystyle 6}$	${\displaystyle 7}$	${\displaystyle -7}$	${\displaystyle 22}$	${\displaystyle 8}$	${\displaystyle 9}$	${\displaystyle 10}$

You can practice your mental arithmetic skills on this table if you apply the algorithm described to calculate the assigned value in the line below for a given value in the top line . ${\displaystyle d}$ ${\displaystyle m_{d}}$

Individual evidence

1. ↑ Reinhold Remmert, Peter Ullrich: Elementary number theory . Third edition. Birkhäuser, Basel-Boston-Berlin, ISBN 978-3-7643-7730-4 , pp. 267 , Corollary on page 64 on coprime numbers .