Pseudoprimzahl mit Mersenne < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:04 Mo 06.06.2011 | | Autor: | Physy |
| Aufgabe | | k sei eine Pseudoprimzahl der Form k = 2r-1 (also ungerade) mit der Basis zwei. Folgere daraus, dass auch f = [mm] 2^{k} [/mm] - 1 eine Pseudoprimzahl zur selben Basis ist. |
Es gilt [mm] ggT(2^{k}-1,2)=1. [/mm] Daraus folgt mit Euler: [mm] 2^{\phi(f)} \equiv [/mm] 1 (mod f). Ich muss ja zeigen, dass [mm] 2^{f-1} \equiv [/mm] 1 (mod f) ist. D.h. aber doch in dem Zusammenhang, dass [mm] \phi(f) [/mm] = f-1, also f prim sein müsste.
Ich komme an dieser Stelle nun nicht mehr weiter und verzweilfe noch...Wie kann ich zeigen, dass f prim ist bzw. das [mm] \phi(f) [/mm] = f-1 gilt?
|
|
| |
|
Hallo Physy,
nur ein kleiner Denkfehler:
> k sei eine Pseudoprimzahl der Form k = 2r-1 (also ungerade)
> mit der Basis zwei. Folgere daraus, dass auch f = [mm]2^{k}[/mm] - 1
> eine Pseudoprimzahl zur selben Basis ist.
>
> Es gilt [mm]ggT(2^{k}-1,2)=1.[/mm] Daraus folgt mit Euler:
> [mm]2^{\phi(f)} \equiv[/mm] 1 (mod f). Ich muss ja zeigen, dass
> [mm]2^{f-1} \equiv[/mm] 1 (mod f) ist.
Bis hier ok. ![[ok]](/images/smileys/ok.gif "[ok]")
> D.h. aber doch in dem
> Zusammenhang, dass [mm]\phi(f)[/mm] = f-1, also f prim sein
> müsste.
Nein, das heißt es nicht. Es gilt aber [mm] \phi(f)|f-1. [/mm]
> Ich komme an dieser Stelle nun nicht mehr weiter und
> verzweilfe noch...Wie kann ich zeigen, dass f prim ist bzw.
> das [mm]\phi(f)[/mm] = f-1 gilt?
Es geht doch gerade darum, dass f nicht prim ist! Allerdings verhält es sich in mindestens einer Hinsicht so, als ob es prim wäre.
Der spezielle Typ von Pseudoprimzahl heißt ![[]](/images/popup.gif) Fermatsche Pseudoprimzahl, aber das hilft für die Lösung nicht wirklich weiter. Zur Basis 2 ist 341 die kleinste solche Zahl.
Es gilt also [mm] 2^{340}\equiv 1\mod{341}, [/mm] obwohl 341=11*31 ist.
Weitere Verweise, Listen und Zahlen findest Du über den verlinkten Wikipedia-Artikel. Einen Beweis zur Aufgabe habe ich auf Anhieb dort aber nicht gefunden. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:41 Mo 06.06.2011 | | Autor: | Physy |
Danke für die ausführliche Erklärung. Aber wie kommst Du darauf, dass [mm] \phi(f)|(f-1) [/mm] gilt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:36 Mo 06.06.2011 | | Autor: | Physy |
Ich komme leider immer noch nicht weiter ... Ich weiß leider nicht, wie ich weitermachen soll.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:53 Di 07.06.2011 | | Autor: | felixf |
Moin!
> nur ein kleiner Denkfehler:
>
> > k sei eine Pseudoprimzahl der Form k = 2r-1 (also ungerade)
> > mit der Basis zwei. Folgere daraus, dass auch f = [mm]2^{k}[/mm] - 1
> > eine Pseudoprimzahl zur selben Basis ist.
> >
> > Es gilt [mm]ggT(2^{k}-1,2)=1.[/mm] Daraus folgt mit Euler:
> > [mm]2^{\phi(f)} \equiv[/mm] 1 (mod f). Ich muss ja zeigen, dass
> > [mm]2^{f-1} \equiv[/mm] 1 (mod f) ist.
>
> Bis hier ok.
>
> > D.h. aber doch in dem
> > Zusammenhang, dass [mm]\phi(f)[/mm] = f-1, also f prim sein
> > müsste.
>
> Nein, das heißt es nicht. Es gilt aber [mm]\phi(f)|f-1.[/mm]
Das muss nicht gelten.
Bei der Pseudoprimzahl $431 = 11 [mm] \cdot [/mm] 31$ gilt etwa [mm] $\phi(431) [/mm] = 300$, aber 300 ist kein Teiler von $431 - 1$.
Die Ordnung von 2 in der Multiplikativen Gruppe muss ein Teiler von $430 - 1$ sein. Und sie ist gleichzeitig immer ein Teiler von [mm] $\phi(431)$ [/mm] (sogar von [mm] $kgV(\phi(11), \phi(31))$, [/mm] was ein echter Telier von [mm] $\phi(431)$ [/mm] ist). Aber [mm] $\phi(431)$ [/mm] muss nicht $430 - 1$ teilen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:26 Di 07.06.2011 | | Autor: | reverend |
Moin Felix,
> > Nein, das heißt es nicht. Es gilt aber [mm]\phi(f)|f-1.[/mm]
>
> Das muss nicht gelten.
>
> Bei der Pseudoprimzahl [mm]431 = 11 \cdot 31[/mm] gilt etwa
> [mm]\phi(431) = 300[/mm], aber 300 ist kein Teiler von [mm]431 - 1[/mm].
Hmpf. Das Beispiel habe ich sogar selber gegeben...
Sorry für die unnötige Verwirrung.
> Die Ordnung von 2 in der Multiplikativen Gruppe muss ein
> Teiler von [mm]430 - 1[/mm] sein. Und sie ist gleichzeitig immer ein
> Teiler von [mm]\phi(431)[/mm] (sogar von [mm]kgV(\phi(11), \phi(31))[/mm],
> was ein echter Telier von [mm]\phi(431)[/mm] ist). Aber [mm]\phi(431)[/mm]
> muss nicht [mm]430 - 1[/mm] teilen.
Ja, klar.
Ich stelle die aus meiner falschen Behauptung resultierenden Fragen mal auf nicht mehr aktiv.
> LG Felix
Danke!
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:58 Di 07.06.2011 | | Autor: | felixf |
Moin!
> k sei eine Pseudoprimzahl der Form k = 2r-1 (also ungerade)
> mit der Basis zwei. Folgere daraus, dass auch f = [mm]2^{k}[/mm] - 1
> eine Pseudoprimzahl zur selben Basis ist.
Du kannst hier benutzen, dass [mm] $2^k [/mm] - 1$ ein Teiler von [mm] $2^\ell [/mm] - 1$ ist, wenn $k$ ein Teiler von [mm] $\ell$ [/mm] ist. (Mit der geometrischen Summenformel kannst du den Quotienten explizit hinschreiben.)
Damit kannst du explizit nachpruefen, dass [mm] $2^{f - 1} [/mm] - 1$ durch $f$ geteilt wird: damit ist $f$ dann eine Pseudoprimzahl zur Basis 2.
LG Felix
PS: reverend: falls das in deinem Link drinnenstand, sorry fuer's wiederholen, aber bei mir hat der Link nicht funktioniert (den Teil des Buches durfte ich mir nicht anschauen).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:22 Di 07.06.2011 | | Autor: | Physy |
Könntest Du mir das etwas genauer erklären? Ich verstehe immer noch nicht, warum [mm] \phi(f) [/mm] = f-1 sein soll ... Ich würde gerne verstehen, wie man auf [mm] \phi(f) [/mm] = f-1 kommt, da dieses Blatt den Satz von Euler und Fermat betrifft. Du, also Felix, hast glaube ich eine andere Lösung gewählt ...
|
|
|
| |
|
Hallo Physy,
ich muss mich erstmal entschuldigen, dass ich gestern eine falsche Spur gelegt habe. Sieh Dir dazu auch die Mitteilung von Felix weiter oben an.
> Könntest Du mir das etwas genauer erklären? Ich verstehe
> immer noch nicht, warum [mm]\phi(f)[/mm] = f-1 sein soll ...
Soll es doch gar nicht. Lies nochmal genauer.
> Ich
> würde gerne verstehen, wie man auf [mm]\phi(f)[/mm] = f-1 kommt, da
> dieses Blatt den Satz von Euler und Fermat betrifft.
[mm] \phi(f)=f-1 [/mm] gilt nur für [mm] f\in\IP, [/mm] also eben nicht, wenn f nur pseudoprim ist.
> Du,
> also Felix, hast glaube ich eine andere Lösung gewählt
> ...
In der Tat. Zeige erst, dass [mm] 2^f-1 [/mm] zerlegbar ist, wenn f zerlegbar ist, und nutze dann den Hinweis von Felix, um zu zeigen, dass [mm] 2^f-1 [/mm] dann auch pseudoprim zur Basis 2 ist, wenn f pseudoprim zur gleichen Basis ist.
Grüße
reverend
|
|
|
|
