Ist die Zahl 999...99 durch die Anzahl ihrer Ziffern teilbar?
Die Lösung steht im unteren Teil der Seite.
Sei n die Anzahl der Neunen. Für n = 3 könnte man die Frage auch so stellen:
Kann man die Menge aller maximal 3-stelligen natürlichen Zahlen in 3 gleich große Teilmengen zerlegen?
Natürlich kann man das (die natürlichen Zahlen N sollen hier immer mit 1 beginnen). Denn 999 ist durch 3 teilbar.
Für n = 2 geht das nicht, und offenbar auch nicht, wenn n eine andere gerade Zahl ist. - Geht es auch für andere Zahlen als 3 ? Gibt es sogar unendlich viele n , für die sich die n-stelligen Zahlen in n gleich große Teilmengen zerlegen lassen?
Wir probieren das mal aus. Ein kleines Programm hilft uns dabei. Es zeigt sich, dass die gesuchten n selten sind. Die Zerlegung ist möglich für folgende n :
1
3
9
27
81
111
243
333
729
999
2187
2997
4107
...
Das bedeutet also konkret, dass z.B. 10243 bei Division durch 243 den Rest 1 lässt. - Die Zahlen aus der Liste (wir wissen noch nicht, ob diese endlich oder unendlich lang ist) wollen wir "erlaubte" Zahlen nennen. Offenbar müssen erlaubte Zahlen ungerade sein, denn auch 10n - 1 ist ungerade.
Frage 1
- Warum enden erlaubte Zahlen nie mit der Ziffer 5 ?
Für manche n , wie z.B. 9, 111, 333, 999 erkennt man unmittelbar, dass es sich um erlaubte Zahlen handelt. Nehmen wir beispielsweise n = 333 : Die Menge der 333-stelligen natürlichen Zahlen hat 999...999 Elemente; diese Anzahl besteht aus 333 Neunen, die sich in 111 Dreiergruppen einteilen lassen: 999.999.999. ... .999 . Man sieht jetzt, dass man durch 333 teilen kann und ohne Rest 3.003.003. ... .003 erhält.
Unser Problem reduziert sich also auf die Frage, ob es unendlich viele n ∈ N gibt, für die n | 10n -1 gilt.
Bis hierhin sind wir (stillschweigend) vom Dezimalsystem ausgegangen. Aber die Fragestellung könnte auch für andere Basen formuliert werden, z.B. so:
Frage 2
- Kann man die Menge aller maximal 3-stelligen natürlichen Zahlen in Hexadezimaldarstellung in 3 gleich große Teilmengen zerlegen?
(Antwort: Ja.)
- Geht das auch für andere Zahlen als 3 ?
Die naheliegende nächste Frage wäre dann:
- Gibt es sogar unendlich viele n , für die sich die Menge der n-stelligen Zahlen in Hexadezimaldarstellung in n gleich große Teilmengen zerlegen lässt?
Ehe man sich mit der Frage nach den unendlich vielen erlaubten n für die Dezimaldarstellung und die Hexadezimaldarstellung beschäftigt, erscheint es einfacher, gleich die allgemeine Problemstellung zu behandeln:
Frage 3
- Gibt es unendlich viele natürliche Zahlen n , für die sich die Menge der n-stelligen Zahlen in b-adischer Darstellung in n gleich große Teilmengen zerlegen lässt?
Die b-adische Darstellung ist die Darstellung mit Basis b . Hier soll b > 2 gelten.
Frage 3 lässt sich wieder umformulieren: Gilt n | bn -1 für unendlich viele n ∈ N ? Da nicht verlangt wird, alle erlaubten n anzugeben, reicht es, eine streng monoton wachsende erlaubte Folge anzugeben. Das erweist sich für b > 2 als recht einfach, wenn man für den Übergang von einem erlaubten n zu einem größeren einen Satz anwendet, der hier als Frage 4 formuliert wird.
Frage 4
- Zeigen Sie, dass a-1 | ak -1 für a, k ∈ N, a ≥ 2
Warum wurde in Frage 3 von b > 2 ausgegangen? Nun, für Dualzahlen ( b = 2 ) gilt nicht das Gleiche wie für andere Basen. Das genaue Gegenteil ist richtig:
n | 2n -1 gilt nur für n = 1 .
Das gehört allerdings nicht zur Aufgabenstellung. Ein Beweis kann hier nachgelesen werden.
Lösung
Vorab ein Hinweis: Bei der Suche nach den erlaubten Zahlen hilft die Website OEIS, die die meisten Zahlenfolgen findet. Die Weiterführung unserer Liste 1, 3, ..., 4107 findet man dort bei der Folge A014950.
Frage 1
- Warum enden erlaubte Zahlen nie mit der Ziffer 5 ?
Bei dieser Frage hatten wir noch das Dezimalsystem im Blick. Eine erlaubte Zahl mit Endziffer 5 hätte die Form j·5 . Aber 10j·5 ist durch 5 teilbar, also ist 10j·5 -1 nicht durch 5 teilbar und folglich auch nicht gleich j·5 .
Frage 2
- Kann man die Menge aller maximal 3-stelligen natürlichen Zahlen in Hexadezimaldarstellung in 3 gleich große Teilmengen zerlegen ?
- Geht das auch für andere Zahlen als 3 ?
Wir probieren das - wie beim Dezimalsystem - einfach aus. 3 ist für die Basis 16 eine erlaubte Zahl, denn 163 -1 = 4095 ist durch 3 teilbar. Es zeigt sich, dass die erlaubten n hier nicht so selten sind. Wieder mit einem kleinen Programm berechnet man, dass die Zerlegung für folgende n möglich ist:
1
3
5
9
15
21
25
27
39
45
55
63
75
81
105
117
125
135
147
155
165
171
189
195
205
...
Frage 3
- Gibt es unendlich viele natürliche Zahlen n , für die sich die Menge der n-stelligen Zahlen in b-adischer Darstellung in n gleich große Teilmengen zerlegen lässt?
Hier wird b > 2 vorausgesetzt.
(Quelle für b = 10 : Mathematical Excalibur 12/5, Problem 290)
Gilt also n | bn -1 für unendlich viele n ∈ N ? Da nicht verlangt wird, alle erlaubten n anzugeben, reicht es, eine streng monoton wachsende erlaubte Folge anzugeben. Es soll verwendet werden, dass
(1) a-1 | ak -1 für a, k ∈ N, a ≥ 2
gilt (der Beweis dafür wird bei Frage 4 nachgeholt). - Wir gehen von einem erlaubten n aus und suchen ein größeres erlaubtes n' .
Da n erlaubt ist, gilt bn -1 = k·n , k > 1 . (Man beachte, dass hier die Voraussetzung b > 2 wichtig ist. Denn für b = 2 und für das erste erlaubte n = 1 wäre k = 1 .)
Jetzt kommt (1) zum Einsatz: bn -1 | bk·n -1
Nun liegt es nahe, n' = bn -1 zu setzen ⇒ n'| bk·n -1 ⇒ n'| bn'-1 ⇒ n' ist erlaubt. Damit ist der Beweis geführt, da man mit n = 1 beginnen kann.
Dieses Verfahren führt ganz schnell zu astronomisch großen erlaubten Zahlen.
Wir wollen das ausprobieren für Dezimalzahlen, also für b = 10 :
n = 1 führt in zwei Schritten auf 9 und 999.999.999 (die nächste erlaubte Zahl ist schon viel zu groß, um sie hier darstellen zu können). Dass 9 ein Teiler von 109 -1 ist, ist trivial. 10999.999.999 -1 hat 999.999.999 Neunen und 999.999.999 hat 9 Neunen, also ist auch hier die Teilbarkeit klar.
n = 3 als Startwert erlaubt nur einen einzigen praktikablen Schritt auf n' = 999 , und dies ist offenbar ein Teiler von 10999 -1 mit 999 Neunen.
Aber auch für kleinere b kommt man nicht sehr weit, wenn man sich die streng monotone Zahlenfolge anschaulich machen möchte. Für b = 3 erhält man 1, 2, 8, 6560 . Schon der nächste Schritt erzeugt eine immens große erlaubte Zahl.
Frage 4
- Zeigen Sie, dass a-1 | ak -1 für a, k ∈ N, a ≥ 2 .
Der Satz ist genau dann richtig, wenn (ak -1)/(a-1) eine natürliche Zahl ist. Also führt man einfach diese Divison aus (Polynomdivision), und erhält (ak -1)/(a-1) = ak-1 + ak-2 + ... + 1 ∈ N .
Dieses Resultat kann man auch leicht durch Ausmultiplizieren überprüfen:
(a-1)·Σj=0..k-1 aj ergibt die Teleskopsumme Σj=0..k-1(aj+1 - aj) = ak - 1 .
Publiziert 2019-09-25 Stand 2016-12-06
voriges Problem | Liste aller Probleme mit Lösungen | nächstes Problem
Manfred Börgens |
zur Leitseite