Teilbarkeit für alle zu 10 teilerfremden Divisoren

Grundidee und Geltungsbereich

Die Methode prüft die Teilbarkeit einer natürlichen Zahl n durch jeden Divisor d, der zu 10 teilerfremd ist, also (10,d)=1. Sie ist an die Dezimaldarstellung angepasst und soll vor allem Kopfrechnen ermöglichen. Die Schreibweise d|n bedeutet „d teilt n“, während d ⟂ 10 die Teilerfremdheit ausdrückt.

Ein Divisor d ist genau dann zu 10 teilerfremd, wenn seine letzte Ziffer r(d) in {1,3,7,9} liegt. Endziffern aus {0,2,4,5,6,8} bedeuten dagegen Teilbarkeit durch 2 oder 5. Deshalb eignet sich das Verfahren nicht für 2, 5 oder deren Vielfache. Alle anderen Primzahlen wie 3, 7, 11, 13, 17 und 19 gehören zum Anwendungsbereich.

Die Regel lautet: Multipliziere die letzte Ziffer der zu prüfenden Zahl mit einem von d abhängigen Multiplikator m_d und addiere das Ergebnis zur Zahl aus den übrigen linken Ziffern. Für d=7 ist beispielsweise m₇=-2. Bei n=476 erhält man 47-2·6=35. Da 7|35 gilt, folgt 7|476. Der Anwender entscheidet selbst, wann das Ergebnis einfach genug ist, um die Teilbarkeit positiv oder negativ zu erkennen.

Formalisierung und Berechnung des Multiplikators

Für n∈ℕ₀ bezeichnet r(n)=mod(n,10) die letzte Ziffer und l(n)=(n-r(n))/10 den linken Zahlenteil. Damit gilt stets n=10·l(n)+r(n). Zum Beispiel sind r(476)=6 und l(476)=47.

Die auf d zugeschnittene Testfunktion, die partielle Ziffernsumme, ist ∂_d(n)=l(n)+m_d·r(n). Sie soll für alle n∈ℕ₀ die Äquivalenz d|n ⇔ d|∂_d(n) erfüllen.

Der Multiplikator m_d lässt sich im Kopf bestimmen. Man betrachtet zuerst e=d und nur bei Bedarf e=3d, bis die letzte Ziffer von e gleich 1 oder 9 ist. Dann gilt:

• r(e)=1: m_d=-(e-1)/10.

• r(e)=9: m_d=(e+1)/10.

Daraus folgen abhängig von der letzten Ziffer von d die Formeln:

• r(d)=1: m_d=-(d-1)/10.

• r(d)=3: m_d=(3d+1)/10.

• r(d)=7: m_d=-(3d-1)/10.

• r(d)=9: m_d=(d+1)/10.

Spätestens bei e=3d wird eine Endziffer 1 oder 9 erreicht, denn aus den Endziffern 3 und 7 werden bei der Multiplikation mit 3 die Endziffern 9 beziehungsweise 1. Zusammen mit einer ganzen Zahl k_d entsteht die Bézout-Identität m_d·10+k_d·d=1. Dabei ist k_d für r(d)=1,3,7,9 der Reihe nach 1,-3,3,-1. Diese Identität stellt den größten gemeinsamen Teiler (10,d)=1 dar.

Teilbarkeitssatz und mathematische Bedeutung

Für d∈ℕ mit d>1 und d ⟂ 10 sowie den angegebenen Multiplikator m_d gilt der Satz über partielle Ziffernsummen: d|n ⇔ d|∂_d(n) für alle n∈ℕ₀.

Die Begründung folgt aus der Rekonstruktion n=k_d·d·r(n)+10·∂_d(n). Der erste Summand ist stets durch d teilbar. Daher gilt d|n genau dann, wenn d|10·∂_d(n). Weil d und 10 teilerfremd sind, ist dies wiederum genau dann der Fall, wenn d|∂_d(n).

Im Restklassenring ℤ/dℤ folgt aus m_d·10+k_d·d=1 die Kongruenz m_d·10≡1 (mod d). Die Restklasse [m_d] ist somit die multiplikative Inverse von [10]: [m_d]=[10]⁻¹.

Die Bézout-Koeffizienten sind nicht eindeutig. m_d kann durch jede Zahl derselben Restklasse modulo d ersetzt werden, sofern k_d passend geändert wird. Für d=7 ist neben m₇=-2 daher auch m=5 geeignet, sodass l(n)+5r(n) ebenfalls ein Teilbarkeitskriterium bildet. Für das Kopfrechnen ist ein Multiplikator nahe 0 günstiger; der beschriebene Algorithmus gewährleistet dies.

Die Testfunktion kann wegen der Äquivalenz wiederholt angewandt werden, solange ihr Argument nicht negativ wird. Bei Multiplikatoren mit negativem Vorzeichen können negative Zwischenergebnisse auftreten: ∂₇(7)=-7 ist zwar nicht erneut im Definitionsbereich ℕ₀, doch 7|-7 ist unmittelbar erkennbar. Im Allgemeinen haben n und ∂_d(n) nicht denselben Rest modulo d. Sicher gilt nur 10·∂_d(n)≡n (mod d); für d=9 bleiben auch die Reste von n und ∂₉(n) gleich.

Beziehung zur Quersumme und Rechenbeispiele

Für d=9 ist m₉=1 und damit ∂₉(n)=l(n)+r(n): Nur die letzte Ziffer wird zum linken Zahlenteil addiert. Dies ähnelt der Quersumme, bei der alle Dezimalziffern addiert werden, und erklärt die Bezeichnung „partielle Ziffernsumme“. Beide Operationen können wiederholt werden, bis ein einstelliges Resultat erreicht ist; dieses Endresultat ist jeweils gleich, obwohl die Zwischenwerte verschieden sein können. So ist ∂₉(1237)=123+7=130, während die Quersumme q(1237)=13 beträgt. Nach weiteren Anwendungen enden beide Verfahren bei 4, also gilt 9∤1237. Außerdem ist ∂₃=∂₉.

Für d=19 ergibt sich m₁₉=2. Bei 233 erhält man ∂₁₉(233)=23+2·3=29, weshalb 233 nicht durch 19 teilbar ist. Für 228 gilt dagegen ∂₁₉(228)=22+2·8=38 und anschließend ∂₁₉(38)=3+2·8=19. Daher gilt 19|228.

Das Verfahren verkleinert eine Aufgabe nicht immer. Für d=43 ist m₄₃=13. Bei n=129 ergibt sich ∂₄₃(129)=12+13·9=129. Obwohl 129=3·43 gilt, liefert die Anwendung keinen einfacheren Wert; 129 ist ein Fixpunkt. Ohne Beweis nennt der Artikel 0, 43, 86 und 129 als genau die ganzzahligen Fixpunkte von ∂₄₃. Eine entsprechende Aussage gilt für alle d mit 3∤d, r(d)=3 und d ⟂ 10.

Alternative Kopfrechenformeln

Mit dem linken Zahlenteil l(d) lassen sich dieselben Multiplikatoren oft bequemer berechnen:

• r(d)=1: m_d=-l(d).

• r(d)=3: m_d=3·l(d)+1.

• r(d)=7: m_d=-(3·l(d)+2).

• r(d)=9: m_d=l(d)+1.

Diese Formeln folgen direkt aus d=10·l(d)+r(d) und stimmen mit den vorherigen Formeln überein. Beim Kopfrechnen sind sie vorteilhaft, weil insbesondere die Multiplikation mit 3 nur auf den kürzeren linken Zahlenteil angewandt wird. Beispiele für die Zuordnung sind m₃=1, m₇=-2, m₁₁=-1, m₁₃=4, m₁₇=-5, m₁₉=2, m₂₃=7, m₃₁=-3, m₄₁=-4 und m₄₃=13.