Achte auf die Reste!

Die folgende Aufgabe stammt aus einer Landesrunde der Mathematikolympiade (Mitte der neunziger Jahre).


Sei n eine natürliche Zahl. Zeige: Es gibt keine Zahl der Form 9n + 1, welche auf zwei Nullen endet.

Zu zeigen ist, dass keine solche Zahl durch 100 teilbar ist. 100 = 22•52, und die Menge der Teiler von 100 ist ( 2, 4, 5, 10, 20, 25, 50,100). Ist darunter wenigstens ein Element, das keine der Zahlen der Form 9n + 1 teilt?

2 teilt alle diese Zahlen, da es sich dabei immer um gerade Zahlen handelt. Aber bereits beim Teiler 4 werden wir "fündig": Wir werden zeigen, dass 9n + 1 nicht durch 4 teilbar ist.

Wir greifen dazu auf ein Hifsmittel aus der Zahlentheorie zurück, das wir in der Aufgabe singh1 bewiesen haben: Das Produkt zweier Zahlen und das Produkt ihrer Teilerreste (bezüglich irgendeiner Zahl n ) haben denselben Teilerrest bezüglich n. Und daraus folgt: Das Quadrat einer Zahl und das Quadrat ihres Teilerrestes ( bezüglich irgendeiner Zahl n) haben denselben Teilerrest bezüglich n.

9n = (32)n = (3n)2 ist für alle n eine Quadratzahl. Welche Reste bei Teilung durch 4 können Quadratzahlen haben? Das erwähnte Hilfsmittel gibt die Antwort: Die möglichen Reste bei Teilung irgendeiner natürlichen Zahl durch 4 sind 0, 1, 2, 3. Deren Quadrate haben bei Teilung durch 4 die Reste 0, 1,0,1. Und das heißt: Quadratzahlen haben als Viererrest entweder 0 oder 1.

Also hat 9n den Viererrest 0 oder 1. 0 ist nicht möglich, da 9n eine ungerade Zahl ist.

Demnach hat 9n für alle n den Viererrest 1. Und damit hat 9n + 1 für alle n den Viererrest 2.

Jedenfalls ist 9n + 1 nicht durch 4 ohne Rest teilbar. Das war zu beweisen.