Primzahlen und Teilbarkeiten < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:54 Di 08.12.2009 | | Autor: | da_kiwi |
| Aufgabe | a) Beweisen Sie für alle natürlichen Zahlen [mm] n\ge1 [/mm] und alle natürlichen Zahlen [mm] k\ge2, [/mm] dass [mm] k^n-1 [/mm] stets durch k-1 teilbar ist!
b) Sei die natürliche Zahl n so gewählt, dass [mm] 2^n-1 [/mm] eine Primzahl ist. Beweisen Sie, dass auch n eine Primzahl sein muss!
(Tipp: Benutzen Sie Teil a)) |
Hey,
Also a) habe ich durch vollständige Induktion gelöst:
[mm] A(n)=k-1|k^n-1
[/mm]
A(1)=k-1|k-1 stimmt offensichtlich für [mm] k\ge2
[/mm]
A(n)->A(n+1)
[mm] k^{n+1}-1=k^{n}-1+x
[/mm]
[mm] x=k^n(k-1)
[/mm]
[mm] k^{n+1}-1=k^n-1+k^n(k-1)
[/mm]
Weil laut I.V. [mm] k^n-1 [/mm] teilbar durch k-1 ist und [mm] k^n(k-1) [/mm] ebenso folgt [mm] k-1|k^{n+1}-1.
[/mm]
So, das Problem liegt jetzt bei der Aufgabe b)
Aus dem Tipp(benutze Teil a)) schließe ich, k=2
[mm] k-1|k^n-1 [/mm] => [mm] 1|2^n-1 [/mm]
Weil [mm] 2^n-1 [/mm] eine Primzahl sein soll, muss [mm] 2^n-1 [/mm] zwangsläufig durch 1 oder p teilbar sein.
1|2^-1 und p|2^-1
Jetzt mir ist mir folgender Satz eingefallen:
a|c und b|c mit ggT(a,b)=1 => ab|c
Also reduziert sich doch nur noch auf [mm] p|2^n-1 [/mm] was zuzeigen wäre. Aber das macht ja alles keinen Sinn, weil die Induktion nicht zu beweisen ist,da n nur [mm] \in [/mm] IP ist. Irgendwie steh ich ziemlich aufm Schlauch^^? Habt ihr vllt paar Tipps auf Lager :) ?
Grüße, Da_Kiwi
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:12 Di 08.12.2009 | | Autor: | abakus |
> a) Beweisen Sie für alle natürlichen Zahlen [mm]n\ge1[/mm] und
> alle natürlichen Zahlen [mm]k\ge2,[/mm] dass [mm]k^n-1[/mm] stets durch k-1
> teilbar ist!
> b) Sei die natürliche Zahl n so gewählt, dass [mm]2^n-1[/mm] eine
> Primzahl ist. Beweisen Sie, dass auch n eine Primzahl sein
> muss!
> (Tipp: Benutzen Sie Teil a))
> Hey,
>
> Also a) habe ich durch vollständige Induktion gelöst:
Kann man machen. Steht euch die Summenformel für die geometrische Reihe zur Verfügung?
Es gilt schließlich [mm] (k-1)(1+k+k^2+...+k^{n-1})=k^n-1. [/mm] Damit ist klar, dass der Faktor k-1 drinsteckt.
>
> [mm]A(n)=k-1|k^n-1[/mm]
>
> A(1)=k-1|k-1 stimmt offensichtlich für [mm]k\ge2[/mm]
>
> A(n)->A(n+1)
>
> [mm]k^{n+1}-1=k^{n}-1+x[/mm]
>
> [mm]x=k^n(k-1)[/mm]
>
> [mm]k^{n+1}-1=k^n-1+k^n(k-1)[/mm]
>
> Weil laut I.V. [mm]k^n-1[/mm] teilbar durch k-1 ist und [mm]k^n(k-1)[/mm]
> ebenso folgt [mm]k-1|k^{n+1}-1.[/mm]
>
> So, das Problem liegt jetzt bei der Aufgabe b)
> Aus dem Tipp(benutze Teil a)) schließe ich, k=2
>
> [mm]k-1|k^n-1[/mm] => [mm]1|2^n-1[/mm]
>
> Weil [mm]2^n-1[/mm] eine Primzahl sein soll, muss [mm]2^n-1[/mm]
> zwangsläufig durch 1 oder p teilbar sein.
Was ist, wenn n keine Primzahl wäre?
Dann wäre n das Produkt zweier natürlicher Zahlen a und b (die beide größer als 1 sind).
Dann würde gelten [mm] 2^n-1=2^{ab}-1=(2^a)^b-1. [/mm] Nach Augabenteil a) wäre dieser Ausdruck durch [mm] 2^a-1 [/mm] (was ein Faktor >1 wäre) teilbar und somit keine Primzahl mehr.
Gruß Abakus
>
> 1|2^-1 und p|2^-1
>
> Jetzt mir ist mir folgender Satz eingefallen:
>
> a|c und b|c mit ggT(a,b)=1 => ab|c
>
> Also reduziert sich doch nur noch auf [mm]p|2^n-1[/mm] was zuzeigen
> wäre. Aber das macht ja alles keinen Sinn, weil die
> Induktion nicht zu beweisen ist,da n nur [mm]\in[/mm] IP ist.
> Irgendwie steh ich ziemlich aufm Schlauch^^? Habt ihr vllt
> paar Tipps auf Lager :) ?
>
> Grüße, Da_Kiwi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:48 Mi 09.12.2009 | | Autor: | da_kiwi |
Hey,
hab die Lösung dank deiner Hilfe gefunden.
Danke ;)
|
|
|
|
