Pseudoprimzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:00 Mo 21.05.2007 | | Autor: | olhh |
| Aufgabe | | Sein n eine Pseudoprimzahl zur Basis 2. Zeigen Sie, dass N = [mm] 2^{n} [/mm] - 1 ebenfalls eine Pseudoprimzahl zur Basis 2 ist. |
Hallo,
bei dieser Aufgabe stehe ich leider total auf dem Schlauch. Ich meine, [mm] 2^n [/mm] - 1 ist ungerade und [mm] 2^{(2^n - 1) - 1} [/mm] gerade. Da könnte 1 bei herauskommen, aber das ist irgendwie noch kein Beweis. Hat jemand einen kleinen Hinweis, wie ich hier weiterkommen könnte? Braucht man irgendwelche modulo-Rechenregeln?
Danke vielmals und viele Grüße
OLHH
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:57 Mo 21.05.2007 | | Autor: | felixf |
Hallo OLHH!
> Sein n eine Pseudoprimzahl zur Basis 2. Zeigen Sie, dass N
> = [mm]2^{n}[/mm] - 1 ebenfalls eine Pseudoprimzahl zur Basis 2 ist.
>
> Hallo,
>
> bei dieser Aufgabe stehe ich leider total auf dem Schlauch.
> Ich meine, [mm]2^n[/mm] - 1 ist ungerade und [mm]2^{(2^n - 1) - 1}[/mm]
> gerade. Da könnte 1 bei herauskommen, aber das ist
> irgendwie noch kein Beweis. Hat jemand einen kleinen
> Hinweis, wie ich hier weiterkommen könnte? Braucht man
> irgendwelche modulo-Rechenregeln?
Ja :)
Also: $n$ ist ja genau dann eine Pseudoprimzahl zur Basis 2, wenn $2$ kein Teiler von $n$ ist und wenn [mm] $2^n \equiv [/mm] 1 [mm] \pmod{n}$ [/mm] ist, also wenn $n$ ein Teiler von [mm] $2^n [/mm] - 1$ ist. Dann gibt es also ein $m [mm] \in \IN$ [/mm] mit $n m = [mm] 2^n [/mm] - 1$.
So. Du sollst jetzt zeigen, dass [mm] $2^{2^n - 1} \equiv [/mm] 1 [mm] \pmod{2^n - 1}$ [/mm] ist; das bedeutet ja, dass [mm] $2^n [/mm] - 1$ eine Pseudoprimzahl zur Basis 2 ist (da 2 kein Teiler von [mm] $2^n [/mm] - 1$ ist).
Jetzt beachte, dass [mm] $2^{2^n - 1} [/mm] = [mm] 2^{n m} [/mm] = [mm] (2^n)^m$ [/mm] ist, und dass [mm] $2^n \equiv [/mm] 1 [mm] \pmod{2^n - 1}$ [/mm] ist. Wenn du das zusammensetzt bekommst du die Behauptung.
LG Felix
|
|
|
| |
|
| Status: |
(Korrektur) kleiner Fehler  | | Datum: | 19:29 Do 24.05.2007 | | Autor: | felixf |
Hallo
> > Sein n eine Pseudoprimzahl zur Basis 2. Zeigen Sie, dass N
> > = [mm]2^{n}[/mm] - 1 ebenfalls eine Pseudoprimzahl zur Basis 2 ist.
> >
> > Hallo,
> >
> > bei dieser Aufgabe stehe ich leider total auf dem Schlauch.
> > Ich meine, [mm]2^n[/mm] - 1 ist ungerade und [mm]2^{(2^n - 1) - 1}[/mm]
> > gerade. Da könnte 1 bei herauskommen, aber das ist
> > irgendwie noch kein Beweis. Hat jemand einen kleinen
> > Hinweis, wie ich hier weiterkommen könnte? Braucht man
> > irgendwelche modulo-Rechenregeln?
>
> Ja :)
>
> Also: [mm]n[/mm] ist ja genau dann eine Pseudoprimzahl zur Basis 2,
> wenn [mm]2[/mm] kein Teiler von [mm]n[/mm] ist und wenn [mm]2^n \equiv 1 \pmod{n}[/mm]
> ist,
Das sollte [mm] $2^{n-1} \equiv [/mm] 1 [mm] \pmod{n}$ [/mm] heissen; daraus folgt [mm] $2^n \equiv [/mm] 2 [mm] \pmod{n}$, [/mm] also $n$ teilt [mm] $2^n [/mm] - 2$.
> also wenn [mm]n[/mm] ein Teiler von [mm]2^n - 1[/mm] ist. Dann gibt es
> also ein [mm]m \in \IN[/mm] mit [mm]n m = 2^n - 1[/mm].
Sei $n m = [mm] 2^n [/mm] - 2$.
> So. Du sollst jetzt zeigen, dass [mm]2^{2^n - 1} \equiv 1 \pmod{2^n - 1}[/mm]
> ist; das bedeutet ja, dass [mm]2^n - 1[/mm] eine Pseudoprimzahl zur
> Basis 2 ist (da 2 kein Teiler von [mm]2^n - 1[/mm] ist).
Hier muss man zeigen, dass [mm] $2^{(2^n - 1) - 1} \equiv [/mm] 1 [mm] \pmod{2^n - 1}$ [/mm] ist. Aber das folgt wegen [mm] $2^{2^n - 2} [/mm] = [mm] 2^{n m} [/mm] = [mm] (2^n)^m \equiv 1^m [/mm] = 1 [mm] \pmod{2^n - 1}$.
[/mm]
Jetzt sollte es aber stimmen *g*
LG Felix
|
|
|
|
!!!
