a) Wir verwenden den folgenden Satz. Sind p, q ganze Zahlen und r, s, ihre Reste bei Division durch eine ganze Zahl m ( m ≠ 0 ), so haben die Produkte p•q und r•s bei Division durch m den gleichen Rest. Kurz: Ein Produkt zweier Zahlen und das Produkt ihrer Reste haben den gleichen Rest.
Diese nützliche Regel ist einfach zu beweisen. Seien p = kp•m + r und q = kq•m + s . Bei der Multiplikation p•q = ( kp•m + r)( kq•m + s) erhält man drei Summanden, die alle den Faktor m enthalten plus das Produkt r•s . Also haben p•q und r•s bei Division durch m den gleichen Rest.
2 hat den Dreierrest - 1 . Also hat 2n den Dreierrest ( -1 )n ; das ist gleich 1 für gerades n und gleich –1 für ungerades n. Das heißt:
(1) 2n = kn•3 + ( - 1 )n ( n, kn natürliche Zahlen)
b) Sei z = anan-1...1a0 die Darstellung einer Zahl im Dualsystem. Es ist dann
(2) z = a0 + a1•2 + a2•22 + a3•23 + … + an•2n =
= a0 + a1•(1•3–1) + a2•(1•3+1) +a3•(3•3-1) + … +an•(kn•3 + (-1)n) =
= 3•( a1 + a2 + 3•a3 + … . kn•an) + a0 – a1 + a2 – a3 + … + (-1)nan
Das heißt: Die Zahl ist genau dann durch 3 teilbar, wenn ihre alternierende Quersumme durch 3 teilbar ist.
Da 10 den Elferrest – 1 hat, bleiben (1) und (2) richtig, wenn man die Zahl 2 durch die Zahl 10, die Zahl 3 durch die Zahl 11 ersetzt. Es ergibt sich die bekannte Regel, wonach eine Zahl genau dann durch 11 teilbar ist, wenn ihre alternierende Quersumme durch 11 teilbar ist.
Weil z.B. die Zahl 6 den Siebenerrest – 1, die Zahl 12 den Dreizehnerrest – 1 hat, folgen ebenso die Regeln: Eine Zahl ist genau dann durch 7 ( durch 13 ) teilbar, wenn ihre alternierende Quersumme im Sechsersystem ( im Zwölfersystem ) durch 7 ( durch 13 ) teilbar ist.
Zum Abschluss drei Zahlenbeispiele.
Im Dualsystem hat die Zahl 21 die Darstellung I0I0I2 (alternierende Quersumme = 3); die Zahl 201 hat die Darstellung II00I00I2 ( alternierende Quersumme = 0 ).
Die durch 13 teilbare Zahl 2626 hat wegen 2626 = 1•1728 + 6•144 + 2•12 + 10 im Zwölfersystem die Darstellung 162X12 ( alternierende Quersumme 10 – 2 + 6 – 1 = 13 )