Fakultät < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 07:11 Mi 09.11.2005 | | Autor: | Toellner |
Hallo:
Wie finde ich alle Paare (n,k) natürlicher Zahlen mit (n-1)! = [mm] n^{k}-1 [/mm] ?
Gruß, Richard
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:02 Mi 09.11.2005 | | Autor: | Galois |
Hallo Richard,
Ist doch gaaanz einfach... 
Zunächst halten wir fest, daß n prim oder =1 sein muß, da jeder Teiler <n sowohl (n-1)! als auch [mm] $n^k$ [/mm] teilen würde. Wir können o.B.d.A. n als >1 und ungerade voraussetzen. (Man beachte: (n,k)=(2,1) ist eine Lösung.)
Ferner enthält (n-1)! mindestens [mm] $2^{[\log_2(n-1)]}-1\ge \frac{n-1}2-1=\frac{n-3}2$ [/mm] Zweierpotenzen.
Nun schreiben wir k als [mm] $k=2^l m^{}$ [/mm] mit [mm] $l\in \IN_0$ [/mm] und [mm] $m\in\IN$ [/mm] ungerade. Wir erhalten:
$(n-1)! = [mm] n^k-1=(n^{2^l})^m-1 [/mm] = [mm] (n^{2^l}-1) [/mm] * [mm] ((n^{2^l})^{m-1} [/mm] + [mm] (n^{2^l})^{m-2} [/mm] + [mm] \dots [/mm] + [mm] n^{2^l} [/mm] +1)$
Da wir n und m als ungerade vorausgesetzt haben, ist der hintere Faktor gleichfalls ungerade. Mithin enthält [mm] $n^{2^l}-1$ [/mm] ebenfalls mindestens [mm] $\frac{n-3}2$ [/mm] Zweierpotenzen.
Nun wenden wir l-mal die dritte Binomische Formel an:
[mm] $n^{2^l}-1=(n^{2^{l-1}}+1)*(n^{2^{l-2}}+1)*\dots*(n^2+1)*(n+1)*(n-1)$
[/mm]
Die Faktoren [mm] $n^{2^{l-1}}+1$, $n^{2^{l-2}}+1$, $\dots$, $n^2+1$ [/mm] sind als um 1 erhöhte ungerade Quadratzahlen jeweils [mm] $\equiv2$ [/mm] mod 4. Von den letzten beiden Faktoren n+1 und n-1 ist genau einer ebenfalls [mm] $\equiv2$ [/mm] mod 4.
Folglich enthält n+1 oder n-1 mindestens [mm] $\frac{n-3}2-l$ [/mm] Zweierpotenzen. ![[lichtaufgegangen]](/images/smileys/lichtaufgegangen.gif "[lichtaufgegangen]")
Daher ist notwendigerweise [mm] $n+1\ge 2^{\frac{n-3}2-l}\ge 2^{(n-3)/2}/k$.
[/mm]
Nun ist aber als Konsequenz aus der Stirlingschen Formel
[mm] $k=\frac{\ln((n-1)!+1)}{\ln n}\le \frac{\ln n!}{\ln n} \le \frac{2 + (n+\frac12)\ln n -n}{\ln n}\le [/mm] n+1$, und folglich [mm] $n+1\ge 2^{(n-3)/2}/(n+1)$, [/mm] d. h. [mm] $(n+1)^4\ge 2^{n-3}$.
[/mm]
Dies ist aber für [mm] $n\ge [/mm] 23$ auf jeden Fall falsch.
Es bleiben die Fälle n=3,5,7,11,13,17,19 zu überprüfen. Von diesen liefern nur die ersten beiden ganzzahlige Werte für k.
Insgesamt existieren daher genau die Lösungen (2,1), (3,1) und (5,2).
Grüße,
Galois
P.S.: Diese Lösung stammt nicht von mir, sondern von einem Bekannten.
![[]](/images/popup.gif) Bonner Matheforum
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:07 Mi 09.11.2005 | | Autor: | Toellner |
Hallo Galois,
ist wirklich einfach, aber ich habs mir noch einfacher gemacht ![[happy]](/images/smileys/happy.gif "[happy]") :
(n-1)! = [mm] n^{k}-1 [/mm] kann durch n-1 geteilt werden zu
(n-2)! = [mm] \summe_{i=1}^{k}n^{i-1}
[/mm]
(n-2)! = [mm] \summe_{i=1}^{k}n^{i-1} [/mm] = k mod (n-1)
Sei n-1 = [mm] \produkt_{i=1}^{m}p_i^{r_i} [/mm] die Primfaktorzerlegung von n-1, dann sind, falls n-1 mindestens zwei verschiedene Primteiler hat, die Primpotenzen [mm] p_i^{r_i} [/mm] alle < n-1, also enthält (n-2)! alle (untereinander verschiedenen) Primpotenzen und k = (n-2)! = 0 mod (n-1). Das geht nicht, wenn 0 < k < n-1.
Also k = n-1 (geht nicht für n>2) oder n-1 hat nur einen Primteiler, nämlich 2 (n-1 ist gerade): n-1 = [mm] 2^{r} [/mm] und damit ist [mm] 2^{r-1} [/mm] Faktor von (n-2)!. Das geht aber nur, wenn (n-2)! keinen weiteren geraden Faktor enthält sonst wäre ja wieder k = (n-2)! = 0 mod (n-1) und damit ist maximal r = 2, k=2 und n = 5.
Grüße, auch an Deinen Bekannten, Richard
|
|
|
|
![[ok]](/images/smileys/ok.gif "[ok]"){kind=small}
