Direkt zum Inhalt

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 \begin{eqnarray}n={({z}_{\ell}\ldots {z}_{1}{z}_{0})}_{g}=\displaystyle \sum _{j=0}^{\ell}{z}_{j}{g}^{j}.\end{eqnarray}

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, \begin{eqnarray}(\mathop{\underbrace{{z}_{mk-1}\ldots {z}_{(m-1)k}}}\limits_{{z}_{m-1}^{k}}\ldots \mathop{\underbrace{{z}_{2k-1}\ldots {z}_{k}}}\limits_{{z}_{1}^{(k)}}\mathop{\underbrace{{z}_{k-1}\ldots {z}_{0}}}\limits_{{z}_{0}^{(k)}}),\end{eqnarray}

um aus den g-adischen Ziffern von n die Zahlen \begin{eqnarray}{z}_{i}^{(k)}=\displaystyle \sum _{j=0}^{k-1}{z}_{ik+j}{g}^{j}\in \{0,\ldots, {g}^{k}-1\},\end{eqnarray}

für 0 ≤ i< m zu erhalten; \begin{eqnarray}n=\left({z}_{m-1}^{(k)}\cdots {z}_{0}^{(k)}\right)\end{eqnarray}

ist die Darstellung von n mit der Grundzahl gk anstelle von g. Die Quersumme k-ter Stufe ist nun gerade deren Summe: \begin{eqnarray}{Q}_{g}^{(k)}(n)={Q}_{{g}^{k}}(n)=\displaystyle \sum _{i=0}^{m-1}{z}_{i}^{(k)};\end{eqnarray}

analog hierzu definiert man die alternierende Quersumme k-ter Stufe durch \begin{eqnarray}{A}_{g}^{(k)}(n)={A}_{{g}^{k}}(n)=\displaystyle \sum _{i=0}^{m-1}{(-1)}^{i}{z}_{i}^{(k)}.\end{eqnarray}

Als Beispiel Quersumme und alternierende Quersumme dritter Stufe: \begin{eqnarray}\begin{array}{rll}n & = & 002810345293,\\ {Q}_{10}^{(3)}(n) & = & 293+345+810+2=1850,\\ {A}_{10}^{(3)}(n) & = & 293-345+810-2=756.\end{array}\end{eqnarray}

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 \begin{eqnarray}{Q}_{g}^{(k)}(n)\equiv n\quad \mathrm{mod}\quad a.\end{eqnarray}

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 \begin{eqnarray}999={3}^{3}\cdot 37\end{eqnarray}

erhält auf diese Weise ein Kriterium der Teilbarkeit durch 37 mit der Quersumme dritter Stufe der Dezimaldarstellung: \begin{eqnarray}{Q}_{10}^{(3)}(n)\equiv n\quad \mathrm{mod}\quad 37.\end{eqnarray}

Ist k = 2m eine gerade Zahl, und ist \begin{eqnarray}{g}^{m}\equiv -1\quad \mathrm{mod}\quad a,\end{eqnarray}

so folgt \begin{eqnarray}{A}_{g}^{(m)}(n)\equiv n\quad \mathrm{mod}\quad a,\end{eqnarray}

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 \begin{eqnarray}10\equiv -1\quad \mathrm{mod}\quad 11,\end{eqnarray}

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.