Zu zeigen ist, dass keine solche Zahl durch 100 teilbar ist. 100 = 2²•5², 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 9ⁿ + 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 9ⁿ + 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.

9ⁿ = (3²)ⁿ = (3ⁿ)² 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 9ⁿ den Viererrest 0 oder 1. 0 ist nicht möglich, da 9ⁿ eine ungerade Zahl ist.

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

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