Teilbarkeit für alle zu 10 teilerfremden Divisoren

Teilbarkeit für alle zu 10 teilerfremden Divisoren^[1] ist eine Methode zur Prüfung der Teilbarkeit einer Zahl für alle zu 10 teilerfremden Divisoren.

Es wird eine Methode zur Prüfung der Teilbarkeit einer Zahl für alle zu 10 teilerfremden Divisoren beschrieben und mathematisch begründet. Die Methode hat zwei Vorteile. Einmal funktioniert sie für alle genannten Teiler. Zweitens stellt sie auch eine Anleitung zur Verfügung, wie der erforderliche Multiplikator ${\displaystyle m_{d}}$ im Kopf ermittelt werden kann. Es werden Divisoren ${\displaystyle d\in {\mathbb {N} }}$ betrachtet, die keine echten gemeinsamen Teiler mit der natürlichen Zahl ${\displaystyle 10}$ haben. Für solche Divisoren werden Teilbarkeitskriterien vorgestellt, die vorrangig Teilbarkeitfragen mittels Kopfrechnen unterstützen und auf die Dezimaldarstellung der zu testenden Zahl ${\displaystyle n\in {\mathbb {N} }_{0}}$ angepasst sind. Die Behauptung, dass ${\displaystyle n}$ durch ${\displaystyle d}$ teilbar ist, wird durch ${\displaystyle d|n}$ ausgedrückt. Als Beispiel sei ${\displaystyle 7|476}$ genannt.Teilerfremdheit von ${\displaystyle m\;,n}$ wird durch ${\displaystyle m\perp n}$ ausgedrückt. Der größte gemeinsame Teiler von ${\displaystyle n,m}$ wird mit ${\displaystyle (n,m)}$ bezeichnet. Es werden Teilbarkeitskriterien der folgenden Art betrachtet:

Multipliziere die rechte Ziffer der zu testenden Zahl ${\displaystyle n}$ mit einem Multiplikator ${\displaystyle m}$ und addiere das Ergebnis zu der Zahl, die aus den restlichen linken Ziffern gebildet wird.

Beim Divisor ${\displaystyle 7}$ ist ${\displaystyle m=-2}$ geeignet. Im Beispiel ergibt sich ${\displaystyle 47-2\cdot 6=47-12=35}$ und daher gilt ${\displaystyle 7|476}$.

Ein solcher Teilbarkeitstest enthält eine menschliche Komponente. Der Anwender entscheidet nach eigenem Ermessen, wann er die zu untersuchende Teilbarkeit als positiv oder negativ entschieden betrachtet. Einem Computer würde man eine solche Entscheidung wahrscheinlich nicht übertragen.

Zunächst seien die Divisoren charakterisiert, die teilerfremd zu ${\displaystyle 10}$ sind. Es sei ${\displaystyle r(d)}$ der Wert der rechten Ziffer von ${\displaystyle d}$. Dann ist ${\displaystyle d}$ genau dann teilerfremd zu ${\displaystyle 10}$, wenn ${\displaystyle r(d)\in \{1,3,7,9\}}$ ist. Zur Begründung sei genannt, dass die anderen möglichen rechten Ziffern ${\displaystyle r(d)\in \{0,2,4,5,6,8\}}$ die Teilbarkeit von ${\displaystyle d}$ durch ${\displaystyle 2}$ oder ${\displaystyle 5}$ nach sich ziehen würde. Solche Teiler können daher nicht teilerfremd zu ${\displaystyle 10}$ sein. Umgekehrt lassen Divisoren ${\displaystyle d}$ mit ${\displaystyle r(d)\in \{1,3,7,9\}}$ niemals den Rest ${\displaystyle 0}$ bei der Division durch ${\displaystyle 2\;,5}$. Für ${\displaystyle d\in \{2,5\}}$ oder Vielfache davon sind die hier beschriebenen Teilbarkeitstests nicht geeignet. Alle anderen Primzahlen ${\displaystyle \in \{3,7,11,13,17,19,\dots \}}$ sind teilerfremd mit ${\displaystyle 10}$ und gehören daher zum vorliegenden Thema.

Es werden die folgenden beiden Funktionen ${\displaystyle l,r:{\mathbb {N} }_{0}\to {\mathbb {N} }_{0}}$ definiert:

${\displaystyle r(n)=mod(n,10)}$ Rest von ${\displaystyle n}$ bei der Division durch ${\displaystyle 10}$

${\displaystyle l(n)=(n-r(n))/10}$ Der linke Teil von ${\displaystyle n}$

Es gilt ${\displaystyle r(n)\in \{0,1,2,3,4,5,6,7,8,9\}}$ und die Division ${\displaystyle (n-r(n))/10}$ ist ohne Rest ausführbar. Es gilt immer ${\displaystyle n=10\cdot l(n)+r(n)}$. Falls ${\displaystyle n}$ dezimal einstellig ist, gilt ${\displaystyle l(n)=0}$. Im Beispiel ${\displaystyle n=476}$ gilt ${\displaystyle r(476)=6\;,l(476)=47\;,476=10\cdot 47+6}$. Es werden jetzt Testfunktionen

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

${\displaystyle \partial _{d}(n)=l(n)+m_{d}\cdot r(n)}$ mit vorläufig noch nicht festgelegtem Multiplikator ${\displaystyle m_{d}\in {\mathbb {Z} }\;,m_{d}\neq 0}$ betrachtet. Schon durch diese Bezeichnungsweise soll angedeutet werden, dass für verschiedene Divisoren ${\displaystyle d}$ der Multiplikator ${\displaystyle m_{d}}$ vom Divisor ${\displaystyle d}$ abhängig ist, also auf den Divisor spezialisiert ist. Aus Gründen, die noch genannt werden, sollen Funktionen vom Typ ${\displaystyle \partial _{d}}$ partielle Ziffernsummen genannt werden. Von einer solchen Funktion wird verlangt, dass gilt:

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

wobei ${\displaystyle \iff }$ die logische – genau dann wenn – Beziehung bedeutet.

Es wird jetzt ein Algorithmus beschrieben, der bei gegebenem Divisor ${\displaystyle d}$ den Multiplikator ${\displaystyle m_{d}}$ festlegt und sogar so einfach beschaffen ist, dass er im Kopf ausführbar ist.

1. Betrachte ${\displaystyle e\in \{d\;,3\cdot d\}}$ in dieser Reihenfolge und prüfe ob ${\displaystyle r(e)\in \{1,9\}}$ ist.
2. Gehe nur dann zu ${\displaystyle e=3\cdot d}$ über, wenn diese Bedingung nicht schon bei ${\displaystyle e=d}$ erfüllt ist.
3. Setze ${\displaystyle m_{d}=-(e-1)/10}$, falls ${\displaystyle r(e)=1}$, hier ist ${\displaystyle m_{d}<0}$
4. Setze ${\displaystyle m_{d}=(e+1)/10}$, falls ${\displaystyle r(e)=9}$, hier ist ${\displaystyle m_{d}>0}$

Man kann sich klarmachen, dass man für ${\displaystyle r(d)\in \{1,3,7,9\}}$ spätestens bei ${\displaystyle e=3\cdot d}$ bei ${\displaystyle r(e)\in \{1,9\}}$ landet. Das beruht darauf, dass bei ${\displaystyle r(d)\in \{3,7\}}$ gilt ${\displaystyle r(3\cdot d)\in \{9,1\}}$, wegen ${\displaystyle 3\cdot 3=9\;,3\cdot 7=21}$. Die Resultate dieses Algorithmus werden jetzt noch als Tabelle dargestellt.

Tabelle 1 Ergebnisse ${\displaystyle d\mapsto m_{d}}$ für den obigen Algorithmus

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

Es wird außer ${\displaystyle m_{d}}$ noch eine weitere ganze Zahl ${\displaystyle k_{d}}$ ins Spiel gebracht, mit dem Ziel die sogenannte Bézout-Identität für den größten gemeinsamen Teiler ${\displaystyle (10,d)=1}$ darzustellen. Dazu werden die einzelnen Fälle ${\displaystyle r(d)\in \{1,3,7,9\}}$ unter Bezugnahme auf die obige Tabelle analysiert.

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

Es sei ${\displaystyle k_{d}}$ nach folgender Tabelle bestimmt, deren Werte aus der jeweiligen rechten Identität als Faktor vor ${\displaystyle d}$ abgelesen werden.

Tabelle 2 Ergebnisse für ${\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}$

Damit können die vier rechten Identitäten einheitlich in folgender Form geschrieben werden:

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

Das ist die aus der elementaren Zahlentheorie in ${\displaystyle {\mathbb {Z} }}$ bekannte Darstellung des größten gemeinsamen Teilers ${\displaystyle (10,d)=1}$, die auch Bézout-Identität genannt wird.

Mit dieser Aussage wird die auf den Divisor ${\displaystyle d}$ spezialisierte Testfunktion ${\displaystyle \partial _{d}}$ zu einem Teilbarkeitskriterium, das auch für das Testen der Teilbarkeit im Kopf benutzt werden kann, wenn je nach Anwender nicht zu große Divisoren ins Spiel kommen. Es sei noch angemerkt, dass die Testfunktionen in einigen Fällen für verschiedene ${\displaystyle d}$ auch identisch sein können. Das tritt z. B. für ${\displaystyle r(d)=3}$ auf. Wegen der ${\displaystyle \iff }$-Beziehung kann die Testfunktion auch mehrfach auf bereits erreichte Ergebnisse angewendet werden. Das erfordert beim Kopfrechnen eventuell erhöhte Merkfähigkeit des Anwenders. In den Fällen ${\displaystyle r(d)\in \{1,7\}}$ kann das Ergebnis negative Werte annehmen. Dann kann auf das erreichte Zwischenergebnis nicht nochmal die Testfunktion angewendet werden. Trotzdem kann der Anwender versuchen, die Teilbarkeit durch ${\displaystyle d}$ zu entscheiden. In jedem Fall entscheidet der Anwender selbst, wann er die Teilbarkeit als positiv oder negativ entschieden betrachtet. Mit der Anwendung von ${\displaystyle \partial _{d}}$ verringert sich die Schwierigkeit zu erkennen, ob Teilbarkeit vorliegt oder nicht. Eine Beweisskizze für den Satz über partielle Ziffernsummen sieht so aus:

Der zu testende Wert ${\displaystyle n}$ kann aus den Werten ${\displaystyle d\!,\partial _{d}(n)\;,m_{d}\;,r(n)}$ auf folgende Weise rekonstruiert werden:

${\displaystyle {\begin{aligned}\partial _{d}(n)&=l(n)+m_{d}\cdot r(n)\\l(n)&=(\partial _{d}(n)-m_{d}\cdot r(n))\\n&=10\cdot l(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)\\n&=10\cdot \partial _{d}(n)+k_{d}\cdot d\cdot r(n)\\n&=k_{d}\cdot d\cdot r(n)+10\cdot \partial _{d}(n)\end{aligned}}}$

Dabei ergibt sich die vorletzte Gleichung durch geeignete äquivalente Umformung der Bézout-Identität in der Form ${\displaystyle m_{d}\cdot 10+k_{d}\cdot d=1\iff -(m_{d}\cdot 10-1)=k_{d}\cdot d}$. Mit Blick auf die letzte Gleichung kann wie folgt argumentiert werden: Der Wert ${\displaystyle n}$ ist eine Summe von zwei Summanden, von denen der erste Summand ein Vielfaches von ${\displaystyle d}$ ist. Daher entscheidet sich die Teilbarkeit an der Teilbarkeit des zweiten Summanden. Es ergibt sich:

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

Da ${\displaystyle d,10}$ teilerfremd sind, ergibt sich:

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

Es sei noch angemerkt, dass in der Bézout-Identität die Koeffizienten vor ${\displaystyle 10\;,d}$ keineswegs eindeutig bestimmt sind. Der Faktor ${\displaystyle m_{d}}$ kann durch einen beliebigen anderen Faktor ${\displaystyle m}$ aus der gleichen Restklasse ${\displaystyle {\pmod {d}}}$ ersetzt werden, wenn der Faktor ${\displaystyle k_{d}}$ noch geeignet angepasst wird. Da in die Konstruktion von ${\displaystyle \partial _{d}}$ nur der Faktor ${\displaystyle m_{d}}$ eingeht, kann das einfach vollzogen werden. Für den Fall ${\displaystyle d=7}$ liest man aus Tabelle-1 ${\displaystyle m_{d}=-2}$ ab. Bildet man nun ${\displaystyle m=-2+7=5}$, so ist auch ${\displaystyle t(n)=l(n)+5\cdot r(n)}$ als Testkriterium für die Teilbarkeit durch ${\displaystyle 7}$ geeignet. Es empfiehlt sich aber hinsichtlich des Kopfrechnens den Faktor ${\displaystyle m}$ nicht zu weit entfernt von ${\displaystyle 0\in {\mathbb {Z} }}$ zu wählen. Wird ${\displaystyle m_{d}}$ nach dem oben beschriebenen Algorithmus festgelegt, ist dies automatisch garantiert. Bildet man ${\displaystyle \partial _{7}(7)=l(7)-2\cdot r(7)=0-2\cdot 7=-7}$, so ist das Ergebnis negativ und ${\displaystyle \partial _{7}(-7)}$ ist nicht definiert. Man kann daher das Zwischenergebnis nicht nochmal verbessern. Der kopfrechnende Anwender erkennt aber sofort, dass ${\displaystyle 7|-7}$ und entscheidet die Teilbarkeit positiv. Schließlich sei noch erwähnt, dass ${\displaystyle \partial _{3}=\partial _{9}}$ ist. Dies kann man unmittelbar aus Tabelle-1 ablesen. In der Regel hat ${\displaystyle \partial _{d}(n)}$ nicht den gleichen Rest bei der Division durch ${\displaystyle d}$ wie ${\displaystyle n}$. Dies trifft nur zu, wenn wirklich Teilbarkeit vorliegt. Im speziellen Fall ${\displaystyle d=9}$ bleiben aber die Reste auch bei Nichtteilbarkeit erhalte. Hinsichtlich der Reste kann man lediglich an der letzten Gleichung in der obigen Gleichungskette ableiten, dass die Reste von ${\displaystyle n}$ und ${\displaystyle 10\cdot \partial _{d}(n)}$ übereinstimmen : ${\displaystyle 10\cdot \partial _{d}(n)\equiv n{\pmod {d}}}$.

Wird die Bézout-Identität in der Form ${\displaystyle m_{d}\cdot 10-1=-k_{d}\cdot d}$ geschrieben, so erkennt man, dass ${\displaystyle m_{d}\cdot 10-1}$ ein Vielfaches von ${\displaystyle d}$ ist. Als Kongruenz bedeutet das

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

Daher ist in ${\displaystyle {\mathbb {Z} }/d{\mathbb {Z} }}$ die Restklasse ${\displaystyle [m_{d}]}$ von ${\displaystyle m_{d}}$ die Inverse von ${\displaystyle [10]}$. Es gilt ${\displaystyle [m_{d}]\cdot [10]=[1]}$, also ${\displaystyle [m_{d}]=[10]^{-1}}$.

Im Fall ${\displaystyle d=9}$ liest man aus Tabelle-1 ${\displaystyle m_{d}=1}$ ab. Daher gilt:

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

und es wir lediglich die letzte Ziffer von ${\displaystyle n}$ zum linken Teil ${\displaystyle l(n)}$ addiert. Vergleicht man das mit der Quersumme von ${\displaystyle n}$, bei der alle Dezimalziffern addiert werden, so kann man bezüglich ${\displaystyle \partial _{9}(n)}$ erkennen, dass die Quersumme gewissermaßen nur partiell gebildet wird. Daher wird hier für alle genannten Teiler der Begriff partielle Ziffernsumme für ${\displaystyle \partial _{d}}$ benutzt. Sowohl bei der Quersumme als auch bei ${\displaystyle \partial _{9}}$ kann man iterativ die Operation auf alle Zwischenresultate anwenden. Das führt nur solange zu neuen Resultaten, wie das zuvor erreichte Resultat nicht dezimal einstellig ist. Ab da bleiben Quersumme und ${\displaystyle \partial _{9}}$ konstant. Es kann auch elementar bewiesen werden, dass die finalen einstelligen Resultate identisch sind, obwohl Zwischenresultate in der Regel für Quersumme und ${\displaystyle \partial _{9}}$ differieren. Zum Beispiel ist ${\displaystyle \partial _{9}(1237)=123+7=130}$ und die Quersumme ist ${\displaystyle q(1237)=1+2+3+7=13}$. Wendet man ${\displaystyle \partial _{9}\;,q}$ iterativ noch mehrmals auf diese Zwischenresultate an, so ergibt sich in beiden Fällen ${\displaystyle 4}$ als Endresultat. Daher ist ${\displaystyle 1237}$ nicht durch ${\displaystyle 9}$ teilbar ${\displaystyle 9\nmid 1237}$.

Für ${\displaystyle d=19}$ ist gemäß Tabelle-1 ${\displaystyle m_{d}=2}$ und ${\displaystyle \partial _{19}(233)=23+2\cdot 3=29}$. Also ist ${\displaystyle 233}$ nicht durch ${\displaystyle 19}$ teilbar. Dagegen ist ${\displaystyle \partial _{19}(228)=22+2\cdot 8=22+16=38,\quad \partial _{19}(38)=3+2\cdot 8=19}$. Daher gilt ${\displaystyle 19|228}$.

Es sei auch nicht verschwiegen, dass es problematische Anwendungsfälle gibt. Solche treten z. B. systematisch für ${\displaystyle r(d)=3}$ auf. Sei ${\displaystyle d=43}$. Dafür liest man aus Tabelle-1 ${\displaystyle m_{d}=13}$ ab. Für ${\displaystyle n=129}$ ergibt sich ${\displaystyle \partial _{43}(129)=12+13\cdot 9=12+117=129}$. Obwohl ${\displaystyle 129=3\cdot 43}$ durch ${\displaystyle 43}$ teilbar ist, ergibt sich durch die Anwendung von ${\displaystyle \partial _{43}(129)}$ kein erkennbarer Vorteil. Wenn der Anwender nicht von selbst erkennt, dass ${\displaystyle 129=3\cdot 43}$ ist, kann er keine neuen Erkenntnisse zu Teilbarkeitsfrage ${\displaystyle 43|129?}$ erlangen. Der Wert ${\displaystyle 129}$ ist also ein Fixpunkt von ${\displaystyle \partial _{43}}$.

Ohne Beweis sei notiert, dass die ganzen Zahlen ${\displaystyle n\in \{0,43,86,129\}}$ genau die Fixpunkte von ${\displaystyle \partial _{43}}$ sind. Eine analoge Aussage gilt für alle Divisoren ${\displaystyle d\;,3\nmid d\;,r(d)=3\;,d\perp 10}$.

Tabelle 3 Beispiele für die Zuordnung ${\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}$

An dieser Tabelle kann man seine Fähigkeiten zum Kopfrechnen üben, wenn man den beschriebenen Algorithmus anwendet, um bei gegebenem ${\displaystyle d}$ in der oberen Zeile den zugeordneten Wert ${\displaystyle m_{d}}$ in der Zeile darunter zu berechnen.

Tabelle 4 Alternative Formeln der Zuordnung ${\displaystyle d\mapsto m_{d}}$

${\displaystyle r(d)}$	${\displaystyle 1}$	${\displaystyle 3}$	${\displaystyle 7}$	${\displaystyle 9}$
${\displaystyle m_{d}}$	${\displaystyle -l(d)}$	${\displaystyle 3\cdot l(d)+1}$	${\displaystyle -(3\cdot l(d)+2)}$	${\displaystyle l(d)+1}$

Diese Formeln ergeben die gleichen Resultate wie die in Tabelle-1 notierten Formeln. Dies ergibt sich aus den folgenden Gleichungen, bei denen immer die universell gültige Beziehung ${\displaystyle d=10\cdot l(d)+r(d)}$ benutzt wird:

${\displaystyle {\begin{aligned}r(d)=1&\Rightarrow m_{d}=-(d-1)/10=-(10\cdot l(d)+1-1)/10&=-l(d)\\r(d)=3&\Rightarrow m_{d}=(3\cdot d+1)/10={\Bigl (}3\cdot (10\cdot l(d)+3)+1{\Bigr )}/10=3\cdot l(d)+10/10&=3\cdot l(d)+1\\r(d)=7&\Rightarrow m_{d}=-(3\cdot d-1)/10=-(3\cdot (10\cdot l(d)+7)-1)/10&=-(3\cdot l(d)+2)\\r(d)=9&\Rightarrow m_{d}=(d+1)/10=(10\cdot l(d)+9+1)/10&=l(d)+1\end{aligned}}}$

Die alternativen Formeln benutzen durchgängig ${\displaystyle l(d)}$ als Ausdrucksmittel und bieten daher beim Kopfrechnen Vorteile. Insbesondere sind die erforderlichen Multiplikationen mit ${\displaystyle 3}$ auf Zahlen mit geringerer Stellenzahl anzuwenden.

• Datei:Teilbarkeitskriterien_und_partielle_Ziffernsummen.pdf