Quelltext der Seite Teilbarkeit für alle zu 10 teilerfremden Divisoren

'''Teilbarkeit für alle zu 10 teilerfremden Divisoren'''<ref>{{Literatur |Autor=Reinhold Remmert, Peter Ullrich |Titel=Elementare Zahlentheorie |Auflage=Dritte Auflage |Verlag=Birkhäuser |Ort=Basel-Boston-Berlin |ISBN=978-3-7643-7730-4 |Seiten=267 |Fundstelle=Korollar auf Seite 64 zur Teilerfremdheit}}</ref> 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 [[Teilerfremdheit|teilerfremden]] [[Division (Mathematik)|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 <math>m_d</math> im Kopf ermittelt werden kann. Es werden Divisoren <math>d\in {\mathbb N}</math> betrachtet, die keine echten gemeinsamen Teiler mit der natürlichen Zahl <math>10</math> haben. Für solche Divisoren werden Teilbarkeitskriterien vorgestellt, die vorrangig Teilbarkeitfragen  mittels Kopfrechnen unterstützen und auf die Dezimaldarstellung der zu testenden Zahl <math>n\in {\mathbb N}_0</math> angepasst sind.
Die Behauptung dass <math>n</math> durch <math>d</math> teilbar ist wird durch <math>d|n</math> ausgedrückt. Als Beispiel sei <math>7|476</math> genannt.Teilerfremdheit von <math>m\;,n</math> wird durch <math>m\perp n</math> ausgedrückt. Der größte gemeinsame Teiler von <math>n,m</math> wird mit <math>(n,m)</math> bezeichnet. Es werden Teilbarkeitskriterien der folgenden Art betrachtet:

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

Beim Divisor <math> 7 </math> ist <math>m=-2</math> geeignet. Im Beispiel ergibt sich <math>47-2*6=47-12=35</math> und daher gilt <math>7|476</math>.

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

=== Mathematische Formalisierung ===

Es werden die folgenden beiden Funktionen <math>l,r:{\mathbb N}_0\to {\mathbb N}_0 </math> definiert:

<math> r(n)=mod(n,10)</math> Rest von <math>n</math> bei der Division durch <math>10</math>

<math> l(n)=(n-r(n))/10</math> Der linke Teil von <math>n</math>

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

<math> \partial_d:{\mathbb N}_0\to {\mathbb Z}</math>

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

<math>d|n\iff d|\partial_d(n)\; \forall n\in {\mathbb N}_0 </math>

wobei <math>\iff </math> die logische – genau dann wenn – Beziehung bedeutet.

Es wird jetzt ein Algorithmus beschrieben, der bei gegebenem Divisor <math>d</math> den Multiplikator <math>m_d</math> festlegt und sogar so einfach beschaffen ist, dass er im Kopf ausführbar ist.
# Betrachte <math>e\in \{d\;,3*d\}</math> in dieser Reihenfolge und prüfe ob <math>r(e)\in\{1,9\}</math> ist.
# Gehe nur dann zu <math>e=3*d</math> über, wenn diese Bedingung nicht schon bei <math>e=d</math> erfüllt ist.
# Setze <math>m_d=-(e-1)/10</math>, falls <math>r(e)=1</math>, hier ist <math>m_d<0</math>
# Setze <math>m_d=(e+1)/10</math>, falls <math>r(e)=9</math>, hier ist <math>m_d>0</math>
Man kann sich klarmachen, dass man für <math>r(d)\in\{1,3,7,9\}</math> spätestens bei <math>e=3*d</math> bei <math>r(e)\in\{1,9\}</math> landet. Das beruht darauf, dass bei <math>r(d)\in \{3,7\}</math> gilt <math>r(3*d)\in\{9,1\}</math>, wegen <math>3*3=9\;,3*7=21</math>. Die Resultate dieses Algorithmus werden jetzt noch als Tabelle dargestellt.
{| class="wikitable centered"  |- id="Tabelle-1"
|+ Tabelle 1 Ergebnisse <math>d\mapsto m_d</math> für den obigen Algorithmus
!<math>r(d)</math> !! <math>1</math> !! <math>3</math> !! <math>7</math> !! <math>9</math>
|-
|<math>m_d</math>|| <math>-(d-1)/10</math> || <math>(3*d+1)/10</math>||<math> -(3*d-1)/10</math> ||<math> (d+1)/10</math>
|}
Es wird außer <math>m_d</math> noch eine weitere ganze Zahl <math>k_d</math> ins Spiel gebracht, mit dem Ziel die sogenannte  [[Lemma von Bézout|Bézout-Identität]] für den größten gemeinsamen Teiler <math>(10,d)=1</math> darzustellen. Dazu werden die einzelnen Fälle <math>r(d)\in\{1,3,7,9\}</math> unter Bezugnahme auf die obige Tabelle analysiert.

<math>
\begin{align}
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{align}
</math>

Es sei <math>k_d</math> nach folgender Tabelle bestimmt, deren Werte aus der jeweiligen rechten Identität als Faktor vor <math>d</math> abgelesen werden.
{| class="wikitable centered"
|+ Tabelle 2 Ergebnisse für <math>d\mapsto k_d</math>
! <math>r(d)</math> !! <math>1</math> !! <math>3</math> !! <math>7</math>!! <math>9</math>
|-
|<math>k_d</math> || <math>1</math> || <math>-3</math> || <math>3</math> || <math>-1</math>
|}
Damit können die vier rechten Identitäten einheitlich in folgender Form geschrieben werden:

{{Anker|BID}} <math>m_d*10+k_d*d=1</math> mit <math>k_d\in\{1,-3,3,-1\}</math>

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

=== Satz über partielle Ziffernsummen ===
{{Kasten |Es sei <math>d\in{\mathbb N}\;,d>1\;,d\perp 10</math> und <math>m_d</math> nach  [[#Tabelle-1|Tabelle-1]] festgelegt. Dann gilt für die Funktion
<math> \partial_d:{\mathbb N}_0\to {\mathbb Z},\quad\partial_d(n)=l(n)+m_d*r(n) </math> die Aussage
<math>d|n\iff d|\partial_d(n) \;\forall n\in {\mathbb N}_0</math>.
}}
Mit dieser Aussage wird die auf den Divisor <math>d</math> spezialisierte Testfunktion <math>\partial_d</math> 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 <math>d</math> auch identisch sein können. Das tritt z. B. für <math>r(d)=3</math> auf. Wegen der <math>\iff</math>-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 <math>r(d)\in \{1,7\}</math> 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 <math>d</math> zu entscheiden. In jedem Fall entscheidet der Anwender selbst, wann er die Teilbarkeit als positiv oder negativ entschieden betrachtet. Mit der Anwendung von <math>\partial_d</math> 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 <math>n</math> kann aus den Werten <math>d\!,\partial_d(n)\;,m_d\;,r(n)</math> auf folgende Weise rekonstruiert werden:

<math>
\begin{align}
\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{align}
</math>

Dabei ergibt sich die vorletzte Gleichung durch geeignete äquivalente Umformung der [[#BID|Bézout-Identität]] in der Form <math>m_d*10+k_d*d=1\iff -(m_d*10-1)=k_d*d</math>. Mit Blick auf die letzte Gleichung kann wie folgt argumentiert werden: Der Wert <math>n</math> ist eine Summe von zwei Summanden, von denen der erste Summand ein Vielfaches von <math>d</math> ist. Daher entscheidet sich die Teilbarkeit an der Teilbarkeit des zweiten Summanden. Es ergibt sich:

<math>d|n\iff d|10*\partial_d(n)</math>

Da <math>d,10</math> teilerfremd sind, ergibt sich:

<math>d|n\iff d|\partial_d(n)</math>

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

=== Die Rolle von ''m<sub>d</sub>'' im [[Restklassenring]] &Zopf;/''d''&Zopf; ===

Wird die  [[#BID|Bézout-Identität]] in der Form <math>m_d*10-1=-k_d*d</math> geschrieben, so erkennt man, dass <math>m_d*10-1</math> ein Vielfaches von <math>d</math> ist. Als Kongruenz bedeutet das

<math>m_d*10\equiv 1 \pmod{d}</math>

Daher ist in <math>{\mathbb Z}/d{\mathbb Z}</math> die Restklasse <math>[m_d]</math> von <math>m_d</math> die Inverse von <math>[10]</math>. Es gilt <math>[m_d]*[10]=[1]</math>, also <math>[m_d]=[10]^{-1}</math>.

=== Beziehungen zur [[Quersumme]] ===

Im Fall <math>d=9</math> liest man aus  [[#Tabelle-1|Tabelle-1]] <math>m_d=1</math> ab. Daher gilt:

<math>\partial_9(n)=l(n)+r(n)</math>

und es wir lediglich die letzte Ziffer von <math>n</math> zum linken Teil <math>l(n)</math> addiert. Vergleicht man das mit der Quersumme von <math>n</math>, bei der alle Dezimalziffern addiert werden, so kann man bezüglich <math>\partial_9(n)</math> erkennen, dass die Quersumme gewissermaßen nur partiell gebildet wird. Daher wird hier für alle genannten Teiler der Begriff '''partielle Ziffernsumme''' für <math>\partial_d</math> benutzt. Sowohl bei der Quersumme als auch bei <math>\partial_9</math> 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 <math>\partial_9</math> konstant. Es kann auch elementar bewiesen werden, dass die finalen einstelligen Resultate identisch sind, obwohl Zwischenresultate in der Regel für Quersumme und <math>\partial_9</math> differieren. Zum Beispiel ist <math>\partial_9(1237)=123+7=130</math> und die Quersumme ist <math>q(1237)=1+2+3+7=13</math>. Wendet man <math>\partial_9\;,q</math> iterativ noch mehrmals auf diese Zwischenresultate an, so ergibt sich in beiden Fällen <math>4</math> als Endresultat. Daher ist <math>1237</math> nicht durch <math>9</math> teilbar <math>9\nmid 1237</math>.

=== Weitere Anwendungsbeispiele ===

Für <math>d=19</math> ist gemäß [[#Tabelle-1|Tabelle-1]] <math>m_d=2</math> und <math>\partial_{19}(233)=23+2*3=29</math>. Also ist <math>233</math> nicht durch <math>19</math> teilbar. Dagegen ist <math>\partial_{19}(228)=22+2*8=22+16=38,\quad \partial_{19}(38)=3+2*8=19</math>. Daher gilt <math>19|228</math>.

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

Ohne Beweis sei notiert, dass die ganzen Zahlen <math>n\in\{0,43,86,129\}</math> genau die Fixpunkte von <math>\partial_{43}</math> sind. Eine analoge Aussage gilt für alle Divisoren <math>d\;,3\nmid d\;,r(d)=3\;,d\perp 10</math>.
{| class="wikitable center"
|+ Tabelle 3 Beispiele für die Zuordnung <math>d\mapsto m_d</math>
! <math>d</math>!!<math>3</math>!!<math>7</math>!!<math>9</math>!!<math>11</math>!!<math>13</math>!!<math>17</math>!!<math>19</math>!!<math>23</math>!!<math>29</math>!!<math>31</math>!!<math>33</math>!!<math>39</math>!!<math>41</math>!!<math>43</math>!!<math>47</math>!!<math>49</math>!!<math>59</math>!!<math>69</math>!!<math>71</math>!!<math>73</math>!!<math>79</math>!!<math>89</math>!!<math>99</math>
|-
| <math>m_d</math>||<math>1</math>||<math>-2</math>||<math>1</math>||<math>-1</math>||<math>4</math>||<math>-5</math>||<math>2</math>||<math>7</math>||<math>3</math>||<math>-3</math>|| <math>10</math> || <math>4</math>||<math>-4</math>||<math>13</math>||<math>-14</math>||<math>5</math>||<math>6</math>||<math>7</math>||<math>-7</math>||<math>22</math>||<math>8</math>||<math>9</math>||<math>10</math>
|}
An dieser Tabelle kann man seine Fähigkeiten zum Kopfrechnen üben, wenn man den beschriebenen Algorithmus anwendet, um bei gegebenem <math>d</math> in der oberen Zeile den zugeordneten Wert <math>m_d</math> in der Zeile darunter zu berechnen.

=== Alternative Formeln zur Berechnung von ''m<sub>d</sub>'' ===

{| class="wikitable centered"  |- id="Tabelle-4"
|+ Tabelle 4 Alternative Formeln der Zuordnung <math> d\mapsto m_d</math>
!<math>r(d)</math> !! <math>1</math> !! <math>3</math> !! <math>7</math> !! <math>9</math>
|-
|<math>m_d</math>|| <math>-l(d)</math> || <math>3*l(d)+1</math>||<math> -(3*l(d)+2)</math> ||<math> l(d)+1</math>
|}

Diese Formeln ergeben die gleichen Resultate wie die in [[#Tabelle-1|Tabelle-1]] notierten Formeln. Dies ergibt sich aus den folgenden Gleichungen, bei denen immer die universell gültige Beziehung <math>d=10*l(d)+r(d)</math> benutzt wird:

<math>
\begin{align}
r(d)=1&\Rightarrow m_d=-(d-1)/10=-(10*l(d)+1-1)/10&=-l(d)\\
r(d)=3&\Rightarrow m_d= (3*d+1)/10=\Bigl(3*(10*l(d)+3)+1\Bigr)/10=3*l(d)+10/10&=3*l(d)+1\\
r(d)=7&\Rightarrow m_d=-(3*d-1)/10=-(3*(10*l(d)+7)-1)/10&=-(3*l(d)+2)\\
r(d)=9&\Rightarrow m_d= (d+1)/10=(10*l(d)+9+1)/10&=l(d)+1
\end{align}
</math>

Die alternativen Formeln benutzen durchgängig <math>l(d)</math> als Ausdrucksmittel und bieten daher beim Kopfrechnen Vorteile. Insbesondere sind die erforderlichen Multiplikationen mit <math>3</math> auf Zahlen mit geringerer Stellenzahl anzuwenden. Bei den Beispielen in [[#Tabelle-3|Tabelle-3]] kann man das ausprobieren.

== Weblinks ==
* [[:Datei:Teilbarkeitskriterien_und_partielle_Ziffernsummen.pdf]]

== Einzelnachweise ==
<references responsive/>

[[Kategorie:Division (Mathematik)]]
[[Kategorie:Zahlentheorie]]
[[Kategorie:Mathematische Logik]]