Pseudoprimzahl < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:31 So 05.06.2011 | | Autor: | emulb |
| Aufgabe | n = 341 = 11+31
b) Es sei b [mm] \in \IN. [/mm] Ist n zusammengesetzt und gilt ggT(b,n) = 1 sowie [mm] b^{n-1}\equiv [/mm] 1 mod n, so heißt die Zahl n eine Pseudoprimzahl zur Basis b. Zeige: n= 341 ist eine Pseudoprimzahl zur Basis 2. |
Ich hab hier eine Lösung aber irgendwie kommt sie mir kurz vor.
[mm] 2^{340} \equiv [/mm] 1 mod 1023
[mm] 1023|2^{340} [/mm] -1
Wegen 341|1023 gilt natürlich auch [mm] 341|2^{340} [/mm] -1 also [mm] 2^{340}\equiv [/mm] 1 mod 341.
Wars das eigentlich schon?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:52 So 05.06.2011 | | Autor: | felixf |
Moin!
> n = 341 = 11+31
Da sollte sicher ein Mal und kein Plus stehen 
> b) Es sei b [mm]\in \IN.[/mm] Ist n zusammengesetzt und gilt
> ggT(b,n) = 1 sowie [mm]b^{n-1}\equiv[/mm] 1 mod n, so heißt die
> Zahl n eine Pseudoprimzahl zur Basis b. Zeige: n= 341 ist
> eine Pseudoprimzahl zur Basis 2.
>
> Ich hab hier eine Lösung aber irgendwie kommt sie mir
> kurz vor.
>
> [mm]2^{340} \equiv[/mm] 1 mod 1023
Das weisst du also schon irgendwo her?
> [mm]1023|2^{340}[/mm] -1
>
> Wegen 341|1023 gilt natürlich auch [mm]341|2^{340}[/mm] -1 also
> [mm]2^{340}\equiv[/mm] 1 mod 341.
>
> Wars das eigentlich schon?
Ja. Aber das kannst du auch nur machen, weil du vorher schon weisst dass [mm] $2^{340} \equiv [/mm] 1 [mm] \pmod{1023}$ [/mm] ist.
Wenn du das nicht hast, musst du [mm] $2^{340}$ [/mm] modulo 341 ausrechnen. Dazu kannst du $340 = [mm] 2^2 \cdot [/mm] 5 [mm] \cdot [/mm] 11$ schreiben und zuerst [mm] $2^{11} [/mm] = 2048$ modulo 341 ausrechnen, dann das ganze hoch 5 nehmen, und dann noch zweimal quadrieren (jeweils zwischendurch modulo 341 nehmen).
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:04 So 05.06.2011 | | Autor: | emulb |
jaa tippfehler :)
ich hätte da auch noch ne alternative:
340 = [mm] 2^{8}+2^{6}*2^{4}*2^{2}
[/mm]
sukzessiven Quadrate [mm] 2^{2}^{i}
[/mm]
also [mm] 2^{340} [/mm] = [mm] 2^{2}^{8}*2^{2}^{6}*2^{2}^{4}*2^{2}^{2} \equiv [/mm] 64*16*64*16 [mm] \equiv [/mm] 1 mod 341
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:55 So 05.06.2011 | | Autor: | felixf |
Moin!
> ich hätte da auch noch ne alternative:
>
> 340 = [mm]2^{8}+2^{6}*2^{4}*2^{2}[/mm]
>
> sukzessiven Quadrate [mm]2^{2}^{i}[/mm]
>
> also [mm]2^{340}[/mm] = [mm]2^{2}^{8}*2^{2}^{6}*2^{2}^{4}*2^{2}^{2} \equiv[/mm]
> 64*16*64*16 [mm]\equiv[/mm] 1 mod 341
Klar. Aber wenn du mit [mm] $2^{11}$ [/mm] modulo 341 anfaengst siehst du, dass [mm] $2^{11} \equiv [/mm] 2 [mm] \pmod{341}$ [/mm] und damit [mm] $2^{10} \equiv [/mm] 1 [mm] \pmod{341}$ [/mm] ist. Da $340$ ein Vielfaches von 10 ist folgt daraus sofort [mm] $2^{340} \equiv [/mm] 1 [mm] \pmod{341}$, [/mm] ohne weiteres Rechnen.
LG Felix
|
|
|
|
