Kongruenz zeigen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:57 So 17.06.2012 | | Autor: | hilbert |
Hallo, ich soll zeigen, dass [mm] 3^k [/mm] kongruent -1 modulo p ist, wenn p eine fermatsce Primzahl ist und zwar [mm] 2^{2^n} [/mm] mit [mm] l=2^n [/mm] und k die Form [mm] 2^{l-1} [/mm] hat.
Sprich, ich habe folgende Kongruenz zu zeigen:
[mm] 3^{2^{l-1}} \equiv [/mm] -1 modulo [mm] 2^{2^n} [/mm] also
[mm] 3^{2^{2^{n}-1}} \equiv [/mm] -1 modulo [mm] 2^{2^n} [/mm] bzw kürzer:
[mm] 3^{2^{l-1}} \equiv [/mm] -1 modulo [mm] 2^{l}
[/mm]
Hat hier jemand einen Tipp für mich? Stehe etwas auf dem Schlauch.
Ich hoffe ich habe mich bei dem ganzen hin und her einsetzen nicht vertan.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:06 Mo 18.06.2012 | | Autor: | felixf |
Moin!
> Hallo, ich soll zeigen, dass [mm]3^k[/mm] kongruent -1 modulo p ist,
> wenn p eine fermatsce Primzahl ist und zwar [mm]2^{2^n}[/mm] mit
> [mm]l=2^n[/mm] und k die Form [mm]2^{l-1}[/mm] hat.
> Sprich, ich habe folgende Kongruenz zu zeigen:
Du meinst eher $p = [mm] 2^{2^n} [/mm] + 1 = [mm] 2^\ell [/mm] + 1$ mit [mm] $\ell [/mm] = [mm] 2^n$?
[/mm]
> [mm]3^{2^{l-1}} \equiv[/mm] -1 modulo [mm]2^{2^n}[/mm] also
>
> [mm]3^{2^{2^{n}-1}} \equiv[/mm] -1 modulo [mm]2^{2^n}[/mm] bzw kürzer:
>
> [mm]3^{2^{l-1}} \equiv[/mm] -1 modulo [mm]2^{l}[/mm]
Auch hier: [mm] $3^{2^{\ell - 1}} \equiv [/mm] -1 [mm] \pmod{2^\ell + 1}$.
[/mm]
> Hat hier jemand einen Tipp für mich? Stehe etwas auf dem
> Schlauch.
In [mm] $\IZ/p\IZ$ [/mm] gibt es genau zwei Elemente, deren Quadrat gleich 1 ist: $+1$ und $-1$.
Wenn du also [mm] $3^{2^{\ell - 1}} \not\equiv [/mm] 1 [mm] \pmod{p}$ [/mm] und [mm] $(3^{2^{\ell - 1}})^2 \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] zeigst, hast du [mm] $3^{2^{\ell - 1}} \equiv [/mm] -1 [mm] \pmod{p}$ [/mm] bewiesen.
Dazu kannst du sicher den kleinen Satz von Fermat verwenden.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 11:45 Mo 18.06.2012 | | Autor: | hilbert |
Hallo!
Ja, natürlich, ich habe die +1 verschlampt, sorry.
Der Satz von Fermat sagt ja, dass
[mm] a^p \equiv [/mm] a mod p oder falls der ggT(a,p)=1 gilt außerdem [mm] a^{p-1} \equiv [/mm] 1 mod p.
Wenn ich mir jetzt [mm] 3^{2^{l-1}} [/mm] anschaue, muss für den kleinen Satz von Fermat ja entweder gelten, dass [mm] 2^{l-1} [/mm] = p ist oder [mm] 2^{l-1}=p-1. [/mm] Wobei mein p = [mm] 2^l [/mm] +1 ist. Aber das kommt ja beides nicht in Frage oder doch?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:49 Mo 18.06.2012 | | Autor: | hilbert |
Okay, das war wohl etwas voreilig. Wenn das klappen würde, käme ich ja auf kongruent 1 was ich gar nicht möchte.
Das heißt ich schaue mir erstmal das Quadrat an:
[mm] (3^{2^{l-1}})^2=3^{2^l} [/mm] und das ist nach kleinem Satz von Fermat kongruent 1 mod [mm] 2^l [/mm] +1. Hoffe das stimmt so, d.h. ich muss noch zeigen, dass [mm] 3^{2^{l-1}} \equiv [/mm] 1 falsch ist. (Wie macht man den Strich durch die Kongruenz?).
Wie zeige ich denn, dass eine Kongruenz nicht zutrifft?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:50 Mo 18.06.2012 | | Autor: | felixf |
Moin!
> Okay, das war wohl etwas voreilig. Wenn das klappen würde,
> käme ich ja auf kongruent 1 was ich gar nicht möchte.
>
> Das heißt ich schaue mir erstmal das Quadrat an:
>
> [mm](3^{2^{l-1}})^2=3^{2^l}[/mm] und das ist nach kleinem Satz von
> Fermat kongruent 1 mod [mm]2^l[/mm] +1.
Genau.
> Hoffe das stimmt so, d.h.
> ich muss noch zeigen, dass [mm]3^{2^{l-1}} \equiv[/mm] 1 falsch ist.
Genau.
> (Wie macht man den Strich durch die Kongruenz?).
Einfach \not\equiv anstelle \equiv eingeben.
> Wie zeige ich denn, dass eine Kongruenz nicht zutrifft?
Das ist an sich etwas muehsam. Ein direkter Weg faellt mir gerade nicht ein.
Hier kann man allerdings geschickt vorgehen, wenn man das Legendre-Symbol kennt. Und zwar gilt fuer eine Primzahl $p$, dass $(a/p) [mm] \equiv a^{\frac{p - 1}{2}} \pmod{p}$ [/mm] ist. Fuer $p = [mm] 2^{2^n} [/mm] + 1$ und $a = 3$ ist [mm] $a^{\frac{p - 1}{2}} [/mm] = [mm] 3^{2^{2^n-1}}$, [/mm] womit das Legendre-Symbol $(3/p)$ das Ergebnis liefert.
Wenn du jetzt die quadratische Reziprokitaet verwendest, kannst du $(3/p)$ durch [mm] $(-1)^{...} \cdot [/mm] (p/3)$ ausdruecken. Das Symbol $(p/3)$ kannst du einfach ausrechnen, da $(p/3) = ((p [mm] \mod [/mm] 3)/3)$ ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:50 Mo 18.06.2012 | | Autor: | hilbert |
Vielen Dank für die Antworten :)
Damit habe ich die Aufgabe jetzt auch endlich verstanden...
Findest du es schlimm, wenn man die Aufgaben nicht schafft und sich hier Hilfe holen muss?
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:40 Di 19.06.2012 | | Autor: | felixf |
Moin,
> Vielen Dank für die Antworten :)
bitte!
> Damit habe ich die Aufgabe jetzt auch endlich
> verstanden...
Gut.
> Findest du es schlimm, wenn man die Aufgaben nicht schafft
> und sich hier Hilfe holen muss?
Nein. Eine Aufgabe mit Hilfestellungen schaffen ist besser als sie gar nicht zu schaffen, da lernt man meist mehr bei.
LG Felix
|
|
|
|
