Manfred Börgens
Mathematische Probleme  # 108		 Liste aller Probleme mit Lösungen
voriges Problem      nächstes Problem		 zur Leitseite


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


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

Die naheliegende nächste Frage wäre dann:

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
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

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

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
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
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
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