Teilbarkeitsregeln

Teilbarkeit im Dezimalsystem

Es gilt

Theorem 1

Eine Zahl ist genau dann durch 33 teilbar, wenn es ihre Quersumme ist.

Proof

Sei n∈Nn\in\mathbb{N} im Dezimalsystem geschrieben,

n=arar−1…a1a0,n=a_ra_{r-1}\dots a_1a_0,

so ist explizit

n=a0+10⋅a1+⋯+10r⋅ar.n=a_0+10\cdot a_1+\dots+10^r\cdot a_r.

Modulo 33 ist jetzt 10≡1mod  310\equiv1\mod3, also [10]=[1][10]=[1]. Damit ist

[n]=[a0+10⋅a1+⋯+10r⋅ar]=[a0]+[10]⋅[a1]+⋯+[10]r⋅[ar]=[a0]+[a1]+⋯+[ar]=[a0+a1+⋯+ar].\begin{align*} [n]&=[a_0+10\cdot a_1+\dots+10^r\cdot a_r]\\ &=[a_0]+[10]\cdot[a_1]+\dots+[10]^r\cdot[a_r]\\ &=[a_0]+[a_1]+\dots+[a_r]\\ &=[a_0+a_1+\dots+a_r]. \end{align*}

Das heisst, die Zahl nn ist Modulo 33 gleich ihrer Quersumme. Insbesondere ist also nn genau dann durch 33 teilbar, wenn die Quersumme es ist.

Exercise 1: Teilbarkeit durch \dots

Vervollständigen und begründen Sie folgende Aussage:

Eine natürliche Zahl ist genau dann durch ... teilbar, wenn es ihre alternierende Quersumme ist.

Unter der alternierenden Quersumme verstehen wir die von rechts nach links gelesene "Quersumme" mit abwechselnden Vorzeichen. Also beispielsweise wäre zur Zahl 123123 die alternierende Quersumme 3−2+1=23-2+1=2.

Solution

Die Antwort ist 1111. Denn für n∈N0n\in\mathbb{N}_0 gilt

10n≡(−1)nmod  11,10^n\equiv(-1)^n\mod11,

da ja 10≡−1mod  1110\equiv -1\mod11. Daraus folgt

ak⋅10k+ak−1⋅10k−1+⋯+a1⋅101+a0⋅100≡ak⋅(−1)k+ak−1⋅(−1)k−1+⋯+a1⋅(−1)1+a0⋅(−1)0mod  11≡(−1)kak+(−1)k−1ak−1+⋯−a1+a0mod  11\begin{align*} & a_k\cdot10^k+a_{k-1}\cdot10^{k-1}+\dots+ a_1\cdot10^1+a_0\cdot10^0\\ &\equiv a_k\cdot(-1)^k+a_{k-1}\cdot(-1)^{k-1}+\dots+a_1\cdot(-1)^1+a_0\cdot(-1)^0\mod11\\ &\equiv (-1)^k a_k+(-1)^{k-1}a_{k-1}+\dots- a_1+a_0\mod11 \end{align*}

Das heisst, man kann bequem von rechts nach links die alternierende Quersumme bilden und gucken, ob diese durch 1111 teilbar ist.

Example 1

1237512375 ist durch 1111 teilbar, denn

5−7+3−2+1=0≡0mod  11.5-7+3-2+1=0\equiv0\mod11.

Teilbarkeit im Hexadezimalsystem

Exercise 2: Teilbarkeitsregel für ...

Überlege dir Teilbarkeitsregeln im Hexadezimalsystem. Betrachte dazu die Teilbarkeit einer Hexadezimalzahl durch 33, 55 und 1717.

Solution

Für das Hexadezimalsystem (1616er System) könnte man eine Teilbarkeitsregel mit Quersumme für die Teilbarkeit mit 33 oder 55 formulieren, da für n∈N0n\in\mathbb{N}_0 gilt: 16n≡1mod  316^n\equiv 1\mod3 bzw. mod  5\mod5. Für die alternierende Quersumme kann man sinngemäss eine Teilbarkeitsregel mod  17\mod17 formulieren, da 16n≡(−1)nmod  1716^n\equiv(-1)^n\mod17.