Pseudoprimzahl zur Basis b < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:19 Sa 19.11.2016 | | Autor: | MarcHe |
| Aufgabe | | Sei $n$ eine Pseudoprimzahl zur Basis $b$ mit $ ggT(b-1,n) = 1 $. Zeigen Sie, dass dann auch [mm] $N=\frac{b^n-1}{b-1}$ [/mm] eine Pseudoprimzahl zur Basis $b$ ist. |
Hallo,
mein Ansatz lautet aktuell leider nur:
Sei $n$ eine Pseudoprimzahl zur Basis $b$, sodass [mm] $b^{n-1}\equiv [/mm] 1 (mod n)$ oder [mm] $b^n \equiv [/mm] b (mod n)$ oder auch [mm] $b^n-b \equiv [/mm] 0 (mod n)$. Wie gehe ich hier weiter vor?
Viele Grüße,
Marc
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:19 So 20.11.2016 | | Autor: | felixf |
Moin Marc!
> Sei [mm]n[/mm] eine Pseudoprimzahl zur Basis [mm]b[/mm] mit [mm]ggT(b-1,n) = 1 [/mm].
> Zeigen Sie, dass dann auch [mm]N=\frac{b^n-1}{b-1}[/mm] eine
> Pseudoprimzahl zur Basis [mm]b[/mm] ist.
> Hallo,
>
> mein Ansatz lautet aktuell leider nur:
>
> Sei [mm]n[/mm] eine Pseudoprimzahl zur Basis [mm]b[/mm], sodass [mm]b^{n-1}\equiv 1 (mod n)[/mm]
> oder [mm]b^n \equiv b (mod n)[/mm] oder auch [mm]b^n-b \equiv 0 (mod n)[/mm].
> Wie gehe ich hier weiter vor?
Wegen $ggT(b-1, n) = 1$ kannst du $b - 1 [mm] \equiv [/mm] x [mm] \pmod{n}$ [/mm] schreiben für ein passendes $x$. Da [mm] $b^n [/mm] - 1$ durch $n$ teilbar ist, ist somit $N [mm] \equiv (b^n [/mm] - 1) [mm] \cdot [/mm] x [mm] \equiv [/mm] 0 [mm] \pmod{n}$, [/mm] also $N = n [mm] \cdot [/mm] y$ für passendes $y [mm] \in \IN$.
[/mm]
Damit kannst du jetzt [mm] $b^N \pmod{n}$ [/mm] ausrechnen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 08:55 Mo 21.11.2016 | | Autor: | MarcHe |
Hallo,
wieso gilt [mm] $n|b^n-1$ [/mm] und warum kann ich aus $ [mm] N=\frac{b^n-1}{b-1} [/mm] $ folgendes $N = [mm] (b^n-1) [/mm] * (b-1) mod (n)$ machen?
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:20 Di 29.11.2016 | | Autor: | Marcel |
Hallo,
> Hallo,
>
> wieso gilt [mm]n|b^n-1[/mm]
das erschließt sich mir auch nicht. Aber wegen [mm] $b^{n-1} \equiv [/mm] 1$ mod [mm] $n\,$ [/mm] gilt
sicher [mm] $n|(b^{n-1}-1)\,.$
[/mm]
Zunächst ist
[mm] $N-1=\frac{b^n-1}{b-1}-\frac{b-1}{b-1}=\frac{b^n-b}{b-1}=\frac{b*(b^{n-1}-1)}{b-1}$
[/mm]
Wegen $n | [mm] (b^{n-1}-1)$ [/mm] (da [mm] $b^{n-1}\equiv [/mm] 1$ mod [mm] $n\,$) [/mm] gibt es also ein $k [mm] \in \IZ$
[/mm]
mit
[mm] $N-1=\frac{bkn}{b-1}=b*n*\frac{k}{b-1}\,.$
[/mm]
Da $b$ und $b-1$ teilerfremd sind ($(-1)*(b-1)+1*b=1$ zeigt ja [mm] $\ggT(b,b-1)=1$), [/mm] und weil
nach Voraussetzung [mm] $\ggT(b-1,n)=1$ [/mm] gilt, muss wegen $N-1 [mm] \in \IN$ [/mm] dann $b-1$ ein Teiler
von [mm] $k\,$ [/mm] sein.
Also folgt $N-1 [mm] \equiv [/mm] 0$ mod $n$ bzw. $N [mm] \equiv [/mm] 1$ mod n. Es gibt also ein
$y [mm] \in \IZ$ [/mm] mit
$N=1+yn$
...
Vielleicht jetzt nochmal gucken, was Hippias weiter vorgeschlagen hat ^^
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:04 Di 29.11.2016 | | Autor: | hippias |
Indem Du mit der Formel für die geometrische Reihe herumspielst, kannst Du zeigen, dass
1. $N=1 [mm] \pmod [/mm] n$
2. [mm] $b^{n}= [/mm] 1 [mm] \pmod [/mm] N$
Damit folgt dann die Behauptung.
|
|
|
|
