Alternierende Quersumme im Dualsystem

Sind a0, a1, a2, ..., an die Ziffern einer Zahl z = anan-1...a1a0 , so wird die alternierende Quersumme wie folgt gebildet: a0 – a1 + a2 – a3 + ... + ( -1)nan.

Zeigen Sie:

  1. Eine Potenz der Form 2n hat bei Division durch 3 den Rest 1, wenn n eine gerade Zahl ist und den Rest – 1, wenn n ungerade ist.

  2. Sei eine Zahl im Dualsystem gegeben. Zeigen Sie: Die Zahl ist genau dann durch 3 teilbar, wenn ihre alternierende Quersumme durch 3 teilbar ist.

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 )