Lexikon der Mathematik: Teilbarkeitskriterien
Kriterien für das Testen der Teilbarkeit einer natürlichen Zahl n durch eine andere natürliche Zahl a anhand einer geeigneten Quersumme von n.
Beispiele hierfür sind nicht nur die Dreierprobe, die Neunerprobe und die Elferprobe, sondern auch die weniger bekannte Siebenerprobe und Dreizehnerprobe.
Die allgemeine Theorie beruht auf dem Begriff der Quersumme k-ter Stufe: Sei n ∈ ℕ in der g-adischen Darstellung (mit einer Grundzahl g ∈ ℕ, g ≥ 2) mit Ziffern z1,…,zℓ ∈ {0, 1,…,g − 1} gegeben, also
Man kann ohne Einschränkung ℓ + 1 = mk für ein m ∈ ℕ annehmen, indem man die Darstellung von n durch so viele führende Nullen wie nötig ergänzt. Um die Quersumme k-ter Stufe zu ermitteln, faßt man zunächst jeweils k Ziffern zusammen,
um aus den g-adischen Ziffern von n die Zahlen
für 0 ≤ i< m zu erhalten;
ist die Darstellung von n mit der Grundzahl gk anstelle von g. Die Quersumme k-ter Stufe ist nun gerade deren Summe:
analog hierzu definiert man die alternierende Quersumme k-ter Stufe durch
Als Beispiel Quersumme und alternierende Quersumme dritter Stufe:
Ein Test für die Teilbarkeit von n durch a mittels einer Quersumme k-ter Stufe der g-adischen Darstellung von n ist genau dann möglich, wenn ggT(a, g) = 1. In diesem Fall muß k die Ordnung von g modulo a sein (oder ein Vielfaches davon), dann gilt nämlich gk ≡ 1 mod a, also auch
Darauf beruht die Dreier- und die Neunerprobe (für k = 1); für k = 2 würde man eine Elferprobe erhalten (die aber von der üblichen abweicht). Wegen der Primfaktorzerlegung
erhält auf diese Weise ein Kriterium der Teilbarkeit durch 37 mit der Quersumme dritter Stufe der Dezimaldarstellung:
Ist k = 2m eine gerade Zahl, und ist
so folgt
und die Teilbarkeit durch n läßt sich anhand der alternierenden Quersumme m-ter Stufe der g-adischen Darstellung überprüfen. Beispielsweise ergibt sich die Elferprobe aus der Kongruenz
also m = 1.
Wegen 1001 = 7 · 11 · 13 gilt 103 ≡ −1 mod 7 und mod 13, also ergibt die alternierende Quersumme dritter Stufe ein Teilbarkeitskriterium sowohl für den Teiler 7 als auch für den Teiler 13.
Unser obiges Beispiel n = 2 810 345 293 ist demzufolge durch 7 teilbar, nicht aber durch 13.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.