Lösb. quadr. Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:15 Di 19.06.2012 | | Autor: | Lonpos |
| Aufgabe | | Legendre-Symbole [mm] (\bruch{-1}{31}) [/mm] und [mm] (\bruch{-1}{17}) [/mm] |
Dazu schaue ich mir die Lösbarkeit der quadratischen Kongruenz an
1) [mm] x^2\equiv{-1} [/mm] (31)
2) [mm] x^2\equiv{-1} [/mm] (17)
Ich habe mir bereits u.a hergeleitet, dass [mm] ax^2+bx+c\equiv{0} [/mm] (m) lösbar ist genau dann wenn [mm] (2ax+b)^2\equiv{b^2-4ac} [/mm] (4am) lösbar ist.
Daher erhalte ich
1) [mm] 4x^2 \equiv{-4} [/mm] (124) => [mm] 4x^2 \equiv{120} [/mm] (124) => [mm] x^2 \equiv{30} [/mm] (124)
2) [mm] 4x^2 \equiv{-4} [/mm] (68) => [mm] 4x^2 \equiv{64} [/mm] (68) => [mm] x^2 \equiv{17} [/mm] (124)
Wie kann ich die nun weitervereinfachen, um zu sehen ob sie lösbar sind oder nicht?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:25 Di 19.06.2012 | | Autor: | Lonpos |
Niemand einen Vorschlag?
|
|
|
| |
|
Hallo Lonpos,
musst Du das so kompliziert machen?
> Legendre-Symbole [mm](\bruch{-1}{31})[/mm] und [mm](\bruch{-1}{17})[/mm]
>
> Dazu schaue ich mir die Lösbarkeit der quadratischen
> Kongruenz an
>
> 1) [mm]x^2\equiv{-1}[/mm] (31)
>
> 2) [mm]x^2\equiv{-1}[/mm] (17)
Ja, darum gehts.
> Ich habe mir bereits u.a hergeleitet, dass
> [mm]ax^2+bx+c\equiv{0}[/mm] (m) lösbar ist genau dann wenn
> [mm](2ax+b)^2\equiv{b^2-4ac}[/mm] (4am) lösbar ist.
Mag sein, das will ich gerade gar nicht überblicken. 
Kennst Du die "übliche" Bedingung für quadratische Reste?
Darfst Du hier verwenden, dass sowohl 31 als auch 17 prim sind?
Dann müsste nämlich gelten [mm] (-1)^{\bruch{p-1}{2}}\equiv 1\mod{p}
[/mm]
Grüße
reverend
> Daher erhalte ich
>
> 1) [mm]4x^2 \equiv{-4}[/mm] (124) => [mm]4x^2 \equiv{120}[/mm] (124) => [mm]x^2 \equiv{30}[/mm]
> (124)
> 2) [mm]4x^2 \equiv{-4}[/mm] (68) => [mm]4x^2 \equiv{64}[/mm] (68) => [mm]x^2 \equiv{17}[/mm]
> (124)
>
> Wie kann ich die nun weitervereinfachen, um zu sehen ob sie
> lösbar sind oder nicht?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:24 Di 19.06.2012 | | Autor: | Lonpos |
Danke, ja ich darf hier das Euler-Kriterium verwenden.
Damit ist das 1.Legendre Symbol -1 und das 2. gleich 1.
Ich hätte noch eine Frage bzgl. einer anderen Kongruenz, und zwar möchte ich wissen ob
[mm] x^2\equiv{59} [/mm] (79) lösbar ist. 79 prim, daher wendet man wieder das Euler-Kriterium an.
=> [mm] 59^{39}\equiv{1} [/mm] (79), wie bestimme ich nun den Rest bei der Division von [mm] 59^{39} [/mm] mit 79 ?
|
|
|
| |
|
Hallo nochmal,
> Danke, ja ich darf hier das Euler-Kriterium verwenden.
>
> Damit ist das 1.Legendre Symbol -1 und das 2. gleich 1.
![[ok]](/images/smileys/ok.gif "[ok]")
> Ich hätte noch eine Frage bzgl. einer anderen Kongruenz,
> und zwar möchte ich wissen ob
>
> [mm]x^2\equiv{59}[/mm] (79) lösbar ist. 79 prim, daher wendet man
> wieder das Euler-Kriterium an.
Ja, das dürfte der einfachste Lösungsweg sein.
> => [mm]59^{39}\equiv{1}[/mm] (79), wie bestimme ich nun den Rest bei
> der Division von [mm]59^{39}[/mm] mit 79 ?
Mit einem Langzahlenrechner ist das ja kein Problem. Zu Fuß muss man sich allerdings ein paar Gedanken über den Rechenweg machen.
Variante 1)
[mm] 39_{10}=100111_2
[/mm]
Dann immer lustig quadrieren:
Klar ist [mm] 59^1\equiv 59\mod{79}
[/mm]
Dann [mm] 59^2\equiv 5\mod{79}
[/mm]
[mm] 59^4\equiv 25\mod{79}
[/mm]
[mm] 59^8\equiv 72\mod{79}
[/mm]
[mm] 59^{16}\equiv 49\mod{79}
[/mm]
[mm] 59^{32}\equiv 31\mod{79}
[/mm]
Schließlich also [mm] 59^{39}=59^{32+4+2+1}=59^{32}*59^4*59^2*59^1\equiv 31*25*5*59\equiv 78\equiv -1\mod{79}
[/mm]
Das funktioniert immer, ist aber - wie hier - manchmal trotzdem zu aufwändig.
Dann gilt es meist, eine geschicktere Darstellung des Exponenten zu finden.
Variante 2)
Eine Möglichkeit hier ist z.B. [mm] 39=2^2*3^2+3.
[/mm]
Außerdem kann man noch [mm] 59\equiv -20\mod{79} [/mm] nutzen.
Dann wäre zu berechnen:
[mm] 59^3\equiv (-20)^3\equiv 5*(-20)\equiv -21\mod{79}
[/mm]
[mm] 59^6=(59^3)^2\equiv 46\mod{79}
[/mm]
[mm] 59^{12}=(59^6)^2\equiv 62\equiv -17\mod{79}
[/mm]
[mm] 59^{36}=(59^{12})^3 \equiv 64\mod{79}
[/mm]
Und schließlich: [mm] 59^{39}=59^{36}*59^3\equiv 64*(-21)\equiv -1\mod{79}
[/mm]
Natürlich mag es noch praktischere Darstellungen des Exponenten 39 geben...
Grüße
reverend
|
|
|
|
