Teilbarkeit für alle zu 10 teilerfremden Divisoren

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

Beschreibung

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 $m_{d}$ im Kopf ermittelt werden kann. Es werden Divisoren $d\in {\mathbb {N} }$ betrachtet, die keine echten gemeinsamen Teiler mit der natürlichen Zahl $10$ haben. Für solche Divisoren werden Teilbarkeitskriterien vorgestellt, die vorrangig Teilbarkeitfragen mittels Kopfrechnen unterstützen und auf die Dezimaldarstellung der zu testenden Zahl $n\in {\mathbb {N} }_{0}$ angepasst sind. Die Behauptung, dass $n$ durch $d$ teilbar ist, wird durch $d|n$ ausgedrückt. Als Beispiel sei $7|476$ genannt. Teilerfremdheit von $m\;,n$ wird durch $m\perp n$ ausgedrückt. Der größte gemeinsame Teiler von $n,m$ wird mit $(n,m)$ bezeichnet. Es werden Teilbarkeitskriterien der folgenden Art betrachtet:

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

Beim Divisor $7$ ist $m=-2$ geeignet. Im Beispiel ergibt sich $47-2\cdot 6=47-12=35$ und daher gilt $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 $10$ sind. Es sei $r(d)$ der Wert der rechten Ziffer von $d$. Dann ist $d$ genau dann teilerfremd zu $10$, wenn $r(d)\in \{1,3,7,9\}$ ist. Zur Begründung sei genannt, dass die anderen möglichen rechten Ziffern $r(d)\in \{0,2,4,5,6,8\}$ die Teilbarkeit von $d$ durch $2$ oder $5$ nach sich ziehen würde. Solche Teiler können daher nicht teilerfremd zu $10$ sein. Umgekehrt lassen Divisoren $d$ mit $r(d)\in \{1,3,7,9\}$ niemals den Rest $0$ bei der Division durch $2\;,5$. Für $d\in \{2,5\}$ oder Vielfache davon sind die hier beschriebenen Teilbarkeitstests nicht geeignet. Alle anderen Primzahlen $\in \{3,7,11,13,17,19,\dots \}$ sind teilerfremd mit $10$ und gehören daher zum vorliegenden Thema.

Mathematische Formalisierung

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

$r(n)=mod(n,10)$ Rest von $n$ bei der Division durch $10$

$l(n)=(n-r(n))/10$ Der linke Teil von $n$

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

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

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

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

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

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

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

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

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

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

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

${\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 $k_{d}$ nach folgender Tabelle bestimmt, deren Werte aus der jeweiligen rechten Identität als Faktor vor $d$ abgelesen werden.

Tabelle 2 Ergebnisse für $d\mapsto k_{d}$

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

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

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

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

Satz über partielle Ziffernsummen

Es sei $d\in {\mathbb {N} }\;,d>1\;,d\perp 10$ und $m_{d}$ nach Tabelle-1 festgelegt. Dann gilt für die Funktion $\partial _{d}:{\mathbb {N} }_{0}\to {\mathbb {Z} },\quad \partial _{d}(n)=l(n)+m_{d}\cdot r(n)$ die Aussage $d|n\iff d|\partial _{d}(n)\;\forall n\in {\mathbb {N} }_{0}$.

Mit dieser Aussage wird die auf den Divisor $d$ spezialisierte Testfunktion $\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 $d$ auch identisch sein können. Das tritt z. B. für $r(d)=3$ auf. Wegen der $\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 $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 $d$ zu entscheiden. In jedem Fall entscheidet der Anwender selbst, wann er die Teilbarkeit als positiv oder negativ entschieden betrachtet. Mit der Anwendung von $\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 $n$ kann aus den Werten $d\!,\partial _{d}(n)\;,m_{d}\;,r(n)$ auf folgende Weise rekonstruiert werden:

${\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 $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 $n$ ist eine Summe von zwei Summanden, von denen der erste Summand ein Vielfaches von $d$ ist. Daher entscheidet sich die Teilbarkeit an der Teilbarkeit des zweiten Summanden. Es ergibt sich:

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

Da $d,10$ teilerfremd sind, ergibt sich:

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

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

Die Rolle von m_d im Restklassenring ℤ/dℤ

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

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

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

Beziehungen zur Quersumme

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

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

und es wir lediglich die letzte Ziffer von $n$ zum linken Teil $l(n)$ addiert. Vergleicht man das mit der Quersumme von $n$, bei der alle Dezimalziffern addiert werden, so kann man bezüglich $\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 $\partial _{d}$ benutzt. Sowohl bei der Quersumme als auch bei $\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 $\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 $\partial _{9}$ differieren. Zum Beispiel ist $\partial _{9}(1237)=123+7=130$ und die Quersumme ist $q(1237)=1+2+3+7=13$. Wendet man $\partial _{9}\;,q$ iterativ noch mehrmals auf diese Zwischenresultate an, so ergibt sich in beiden Fällen $4$ als Endresultat. Daher ist $1237$ nicht durch $9$ teilbar $9\nmid 1237$.

Weitere Anwendungsbeispiele

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

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

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

Tabelle 3 Beispiele für die Zuordnung $d\mapsto m_{d}$

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

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

Alternative Formeln zur Berechnung von m_d

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

$r(d)$	$1$	$3$	$7$	$9$
$m_{d}$	$-l(d)$	$3\cdot l(d)+1$	$-(3\cdot l(d)+2)$	$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 $d=10\cdot l(d)+r(d)$ benutzt wird:

${\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 $l(d)$ als Ausdrucksmittel und bieten daher beim Kopfrechnen Vorteile. Insbesondere sind die erforderlichen Multiplikationen mit $3$ auf Zahlen mit geringerer Stellenzahl anzuwenden.

Weblinks

• Datei:Teilbarkeitskriterien und partielle Ziffernsummen.pdf