x^{2} ≡ 1 (mod n) hat ±1 Lsg < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:04 So 28.11.2010 | | Autor: | Lyrn |
| Aufgabe | | Ist n eine Primzahl, so besitzt [mm] x^{2} [/mm] ≡ 1 (mod n) genau die Lösungen ±1 (mod n) |
Hallo, ich habe bis jetzt:
a ≡ b (mod n) [mm] \gdw [/mm] a-b [mm] \in [/mm] n [mm] \gdw [/mm] a-b = [mm] \lambda [/mm] * n für ein [mm] \lambda \in \IZ
[/mm]
Also gilt [mm]x^{2}-1= \lambda * n \gdw \bruch{x^{2}-1}{n} = \lambda ( \lambda \in \IZ ) [/mm]
Damit dies erfüllt ist, muss [mm] x^2-1 [/mm] entweder 0, n oder ein Vielfaches von n sein.
Im Falle von [mm] x^{2}-1=0 [/mm] folgt leicht dass x= [mm] \pm [/mm] 1
Jetzt weiß ich aber nicht wie ich für den Fall dass [mm] x^{2}-1=n [/mm] und [mm] x^{2}-1=a*n [/mm] verfahren soll. Ich muss ja irgendwie noch weiter ausnutzen, dass n eine Primzahl ist.
Hoffe mir kann jemand weiterhelfen!
Viele Grüße Lyrn
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:28 So 28.11.2010 | | Autor: | felixf |
Moin!
> Ist n eine Primzahl, so besitzt [mm]x^{2}[/mm] ≡ 1 (mod n) genau
> die Lösungen ±1 (mod n)
> Hallo, ich habe bis jetzt:
> a ≡ b (mod n) [mm]\gdw[/mm] a-b [mm]\in[/mm] n [mm]\gdw[/mm] a-b = [mm]\lambda[/mm] * n für
> ein [mm]\lambda \in \IZ[/mm]
Bei der zweiten Bedingung soll wohl $n [mm] \IZ$ [/mm] anstelle $n$ stehen?
Du kannst das ganze auch umformulieren zu $a - b$ ist durch $n$ teilbar.
Das ist die Definition, die du brauchst.
> Also gilt [mm]x^{2}-1= \lambda * n \gdw \bruch{x^{2}-1}{n} = \lambda ( \lambda \in \IZ )[/mm]
>
> Damit dies erfüllt ist, muss [mm]x^2-1[/mm] entweder 0, n oder ein
> Vielfaches von n sein.
Ein Vielfaches von $n$ deckt die beiden anderen Faelle mit ab.
> Im Falle von [mm]x^{2}-1=0[/mm] folgt leicht dass x= [mm]\pm[/mm] 1
>
> Jetzt weiß ich aber nicht wie ich für den Fall dass
> [mm]x^{2}-1=n[/mm] und [mm]x^{2}-1=a*n[/mm] verfahren soll. Ich muss ja
> irgendwie noch weiter ausnutzen, dass n eine Primzahl ist.
Du weisst, dass $n$ ein Teiler von [mm] $x^2 [/mm] - 1 = (x - 1) (x + 1)$ ist.
Kennst du jetzt eine Teilbarkeitseigenschaft von Primzahlen (in Bezug auf Produkte)?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:26 So 28.11.2010 | | Autor: | Lyrn |
Hallo Felix,
danke erstmal!
> Du weisst, dass [mm]n[/mm] ein Teiler von [mm]x^2 - 1 = (x - 1) (x + 1)[/mm]
> ist.
>
> Kennst du jetzt eine Teilbarkeitseigenschaft von Primzahlen
> (in Bezug auf Produkte)?
>
> LG Felix
[mm]n|x^2 - 1 \gdw \bruch{(x - 1) (x + 1)}{n} \in \IZ[/mm]
Also muss [mm] x^{2}-1 [/mm] entweder [mm]n[/mm] oder [mm]\lambda*n[/mm] sein. Da man [mm] x^{2}-1 [/mm] auch als [mm](x - 1) (x + 1)[/mm] schreiben kann, folgt dass der Fall [mm]x^{2}-1=n[/mm] ausgeschlossen ist (da n Primzahl).
Für [mm]\lambda \not= 1[/mm] folgt dass [mm]x^{2}-1=\lambda *n \Rightarrow (x-1)[/mm] oder [mm](x+1)[/mm] muss n, also eine Primzahl, sein.
Nur weiß ich jetzt nicht wie auf [mm] x=\pm [/mm] 1 schließen soll.
lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:46 So 28.11.2010 | | Autor: | leduart |
Hallo
a*n=0 mod n
besser [mm] x^2-1=(x+1)*(x-1)=0 [/mm] mod n
also x-1=0 mod n oder x+1=0 mod n
mod p ist a*b=0 nur für a=0 oder b=0 wenn n keine primzahl ist, ist das falsch
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:03 So 28.11.2010 | | Autor: | Lyrn |
> Hallo
> a*n=0 mod n
> besser [mm]x^2-1=(x+1)*(x-1)=0[/mm] mod n
> also x-1=0 mod n oder x+1=0 mod n
> mod p ist a*b=0 nur für a=0 oder b=0 wenn n keine
> primzahl ist, ist das falsch
> Gruss leduart
Hi also ich hab verstanden, wie du auf deine Aussage kommst.
Aber jetzt hab ich mal eine Frage, warum diese Aussage (welche dem Beweis widerspräche) nicht gilt:
[mm]x^2 \equiv 1 (mod n)[/mm]
und sei nun [mm]x=6[/mm] und [mm]n=7[/mm]
dann ist die Kongruenz doch trotzdem noch erfüllt:
[mm]6^2=36 \equiv 1 (mod 7)[/mm]
danach wäre für x ja nicht mehr nur [mm]\pm 1[/mm] möglich.
Wo ist denn hier mein Denkfehler?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:15 So 28.11.2010 | | Autor: | felixf |
Moin,
> > a*n=0 mod n
> > besser [mm]x^2-1=(x+1)*(x-1)=0[/mm] mod n
> > also x-1=0 mod n oder x+1=0 mod n
> > mod p ist a*b=0 nur für a=0 oder b=0 wenn n keine
> > primzahl ist, ist das falsch
> > Gruss leduart
>
>
> Hi also ich hab verstanden, wie du auf deine Aussage
> kommst.
> Aber jetzt hab ich mal eine Frage, warum diese Aussage
> (welche dem Beweis widerspräche) nicht gilt:
>
> [mm]x^2 \equiv 1 (mod n)[/mm]
> und sei nun [mm]x=6[/mm] und [mm]n=7[/mm]
> dann ist die Kongruenz doch trotzdem noch erfüllt:
> [mm]6^2=36 \equiv 1 (mod 7)[/mm]
> danach wäre für x ja nicht mehr
> nur [mm]\pm 1[/mm] möglich.
>
> Wo ist denn hier mein Denkfehler?
$6 [mm] \equiv [/mm] -1 [mm] \pmod{7}$
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:03 Mo 29.11.2010 | | Autor: | Lyrn |
> [mm]6 \equiv -1 \pmod{7}[/mm]
>
> LG Felix
>
>
Hi!
Ich meine aber [mm]36 \equiv 1 \pmod{7}[/mm]. Die 6 bezog sich auf die Vorschrift [mm]x^{2} \equiv 1 \pmod{7}[/mm] für x=6.
Oder was ist hier mein Denkfehler?
lg
|
|
|
| |
|
Hallo Lyrn,
Du sollst nicht [mm] x^2 [/mm] betrachten, sondern x. Und da stimmt die Aussage.
Grüße
reverend
|
|
|
|
