Auf die Reste kommt es an

Eine Aufgabe aus der Schulrunde der Mathematikolympiade 1995/96, Klassenstufe 8


Alexander meint: "Die Summe zweier aufeinanderfolgender Zahlen, die beide nicht durch 3 teilbar sind, ist stets durch 3 teilbar."
(Er verdeutlicht dies durch ein Beispiel: Wie könnte ein solches Beispiel lauten?)

Bianca meint: "Die Summe von drei aufeinanderfolgenden natürlichen Zahlen, die nicht durch 4 teilbar sind, ist stets durch 2 teilbar."

Christian fährt schweres Geschütz auf, indem er diese beiden Aussagen als Spezialfälle der folgenden allgemeinen Aussage interpretiert: "Für jede natürliche Zahl m größer oder gleich 3 ist die folgende Behauptung richtig. Sei S die Summe von m - 1 aufeinanderfolgenden natürlichen Zahlen, die sämtlich nicht durch m teilbar sind. Falls m gerade ist, so ist S durch m/2 teilbar. Ist m ungerade, so ist S durch m teilbar."

Zeige, dass alle drei Aussagen wahr sind.


Um nicht ständig von „3-er-Rest“ oder „Rest bei Teilen durch m“ u.dgl. reden zu müssen, führen wir die folgende, in der Zahlentheorie übliche Schreibweise ein.

Wenn zwei natürliche Zahlen x und y beim Teilen durch eine natürliche Zahl n denselben Rest ergeben oder, was dasselbe ist, wenn zwei natürliche Zahlen x und y sich nur um ein ganzzahliges Vielfaches von n unterscheiden, so sagt man : „x ist kongruent y modulo n“. Im Zeichen:

x ≡ y mod n . Beispielsweise gilt : 14≡ 26 mod 3 oder 12 ≡ 2 mod 5 oder 144 ≡ 0 mod 12.

Ist eine Zahl r Teiler einer Zahl s ( im Zeichen r | s, so gilt s ≡ 0 mod r)

Fangen wir mit Alexanders Aussage an. Und wir liefern gleich ein Beispiel: 10 und 11 sind zwei aufeinanderfolgende natürliche Zahlen, die beide nicht durch 3 teilbar sind. Ihre Summe, die Zahl 21, ist durch 3 teilbar.

Seien nun x, y natürliche Zahlen, die beide nicht durch 3 teilbar sind, und sei y = x +1.

Wenn x nicht durch 3 teilbar ist, so gilt x ≡ 1 mod 3 oder x ≡ 2 mod 3. Im ersten Fall ist y≡2mod3, im zweiten Fall y≡3 mod 3 und damit y≡0mod 3, was aber nach Voraussetzung nicht sein darf, da y nicht durch 3 teilbar sein darf. Folglich muss gelten: x ≡ 1 mod 3 und y≡2mod3. Damit ist x + y ≡ 3mod 3 oder x + y ≡ 0mod 3, d.h. 3 | x +y.

Die Aussage Alexanders ließe sich auch noch ohne die hier eingeführte Schreibweise ohne größeren Aufwand beweisen: Zwei aufeinanderfolgende natürliche Zahlen, die beide nicht durch drei teilbar sein dürfen, haben die Dreierreste 1 und 2. Ihre Summe hat damit den Dreierrest 1+2 = 3, d.h. sie ist durch 3 teilbar.

Gehen wir nun zu Biancas Aussage. Seien x, y, z, drei aufeinanderfolgende natürliche Zahlen, die alle nicht durch 4 teilbar sind. Dann ist x ≡ 1 mod 4, y ≡ 2 mod 4, z ≡ 3 mod 4, und damit x+y+z ≡ (1+2+3)mod 4 , also x+y+z ≡ 6 mod 4 und schließlich x + y+ z ≡ 2 mod 4. Eine Zahl, welche den Viererrest 2 hat, muss gerade sein.

Und nun zur Aussage von Christian.

Seien x1, x2, ...., xm – 1 m-1 aufeinanderfolgende natürliche Zahlen, die alle nicht durch m teilbar sind.

Dann ist x1 ≡ 1 mod m, x2 ≡ 2 mod m und schließlich xm – 1 ≡ (m-1)mod m.

Für die Summe dieser Zahlen S gilt: S ≡ ( 1 + 2 + ... + (m-1)) mod m oder

S ≡ ( m•(m-1)/2) mod m ( Hier haben wir die Summenformel 1 + 2 + ... + n = n•(n+1)/2 benutzt)

Sei nun m gerade. Dann ist m/2 eine natürliche Zahl, nennen wir sie r.

S ≡ (r•(m-1)) mod m . Damit gilt S = r•(m – 1) + k•m = r•(m-1) + k•2r = r•(2k+m-1)

( k ist ganzzahlig). Es folgt r | S, was zu beweisen war.

Sei nun m ungerade. Dann ist (m-1)/2 eine natürliche Zahl, nennen wir sie p. Es folgt:

S ≡ (m•p)mod m . Damit ist S = m•p + u•m ( u ist ganzzahlig), und damit S = (p+u)•m

oder m | S , was zu beweisen war.