Index, Lösen von x^17=7(mod19) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:00 Mo 10.09.2012 | | Autor: | Peon |
| Aufgabe | | Finde alle Lösungen von [mm] x^{15}\equiv7(mod19) [/mm] |
Hallo zusammen,
ich versuche die Aufgabe nachzuvollziehen.
Mir ist das weitestgehend klar, dass man das auch mit dem Index lösen kann, nur ist ein Rechenschritt für mich nicht nachvollziehbar.
1) [mm] x^{15}\equiv7(mod19)
[/mm]
2) [mm] \gdw 15*Ind_{2}(x) \equiv [/mm] 6(mod18) (man nimmt Basis 2, weil 2 eine Primitivwurzel mod 19 ist)
3) [mm] \gdw 5*Ind_{2}(x) \equiv [/mm] 2(mod6) (Kürzungsregel für mod, mit ggT(18,15)=3)
4) [mm] \gdw Ind_{2}(x) \equiv [/mm] -2 [mm] \equiv [/mm] 4 (mod6) (diesen Schritt verstehe ich nicht, ich bin alle mir bekannten Rechenregeln durchgegangen, aber finde keine die dazu passt, vielleicht kann mir einer weiterhelfen, oder ist das wieder so ein Trick, nach dem Motto "weil es klappt"?)
Man weiß es gibt genau 3 Lösungen, weil ggT(15,18)=3, die Lösungen sind [mm] Ind_{2}(x)=4, Ind_{2}(x)=10, Ind_{2}(x)=16, [/mm] also x=16, 17 und 5.
Danke
|
|
| |
|
moin,
> 3) [mm]\gdw 5*Ind_{2}(x) \equiv[/mm] 2(mod6) (Kürzungsregel für
> mod, mit ggT(18,15)=3)
> 4) [mm]\gdw Ind_{2}(x) \equiv[/mm] -2 [mm]\equiv[/mm] 4 (mod6) (diesen
> Schritt verstehe ich nicht, ich bin alle mir bekannten
> Rechenregeln durchgegangen, aber finde keine die dazu
> passt, vielleicht kann mir einer weiterhelfen, oder ist das
> wieder so ein Trick, nach dem Motto "weil es klappt"?)
Hmm, es ist $5 [mm] \equiv [/mm] -1$ (mod 6).
Damit ist es eine Einheit, du kannst also beide Seiten dadurch teilen.
> Man weiß es gibt genau 3 Lösungen, weil ggT(15,18)=3, die
> Lösungen sind [mm]Ind_{2}(x)=4, Ind_{2}(x)=10, Ind_{2}(x)=16,[/mm]
> also x=16, 17 und 5.
Als Tipp noch, falls du mal andere Aufgaben dieses Typs machen musst:
Wir können definitiv $x=0$ ausschließen.
Damit ist jede Lösung (falls existent) eine Einheit, es gilt also:
[mm] $x^{15} [/mm] = 7 [mm] \gdw x^{18} [/mm] = [mm] 7x^3$
[/mm]
Da wir modulo 19 sind und 19 eine Primzahl ist, gilt [mm] $x^{18} \equiv [/mm] 1$; und zwar für alle $0 [mm] \neq [/mm] x$.
Damit und mit [mm] $7^{-1} \equiv [/mm] 11$ erhält man:
[mm] $x^{15} [/mm] = 7 [mm] \gdw x^3 [/mm] = 11$ (mod 19)
Das hat an dieser Stelle in erster Linie den Vorteil, dass du die Lösungen ohne größere Probleme Einsetzen kannst um zu überprüfen, ob du richtig gerechnet hast.
Nehmen wir als sehr schönes Beispiel mal den Tippfehler aus deiner Überschrift:
[mm] $x^{17} [/mm] = 7 [mm] \gdw x^{18} [/mm] = 7x [mm] \gdw [/mm] 1=7x [mm] \gdw [/mm] x=11$.
In diesem Fall ist diese Berechnung deutlich leichter als die Berechnung eines Logarithmus.
Also kurz und knapp: Man sollte beide Verfahren kennen; welche du jeweils verwendest musst du wissen.
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:35 Di 11.09.2012 | | Autor: | Peon |
danke für die schnelle antwort, den alternativen lösungsweg werde ich mir auch mal bei gelegenheit anschauen, ist im moment was knapp bei mir. bei der aufgabe ging es um das einübungen des diskreten logarithmus, daher die ganze rechnerei... :)
eine vielleicht blöde fragen, aber wenn ich beide seiten durch 5 dividiere, dann komme ich doch auf der rechten seite nicht auf -1, oder habe ich jetzt ein brett vor dem kopf?
>
> Hmm, es ist [mm]5 \equiv -1[/mm] (mod 6).
> Damit ist es eine Einheit, du kannst also beide Seiten
> dadurch teilen.
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:10 Di 11.09.2012 | | Autor: | felixf |
Moin!
> danke für die schnelle antwort, den alternativen
> lösungsweg werde ich mir auch mal bei gelegenheit
> anschauen, ist im moment was knapp bei mir. bei der aufgabe
> ging es um das einübungen des diskreten logarithmus, daher
> die ganze rechnerei... :)
>
> eine vielleicht blöde fragen, aber wenn ich beide seiten
> durch 5 dividiere, dann komme ich doch auf der rechten
> seite nicht auf -1, oder habe ich jetzt ein brett vor dem
> kopf?
Welche Gleichung meinst du? $5 [mm] Ind_2(x) \equiv [/mm] 2 [mm] \pmod{6}$ [/mm] oder $5 [mm] \equiv [/mm] -1 [mm] \pmod{6}$?
[/mm]
> > Hmm, es ist [mm]5 \equiv -1[/mm] (mod 6).
> > Damit ist es eine Einheit, du kannst also beide Seiten
> > dadurch teilen.
Ich nehme mal an, du meinst zweiteres. Hier wird nicht durch 5 geteilt, hier wird einfach nur bemerkt, dass 5 und -1 bei Divison durch 6 den gleichen Rest lassen. Und mit -1 kann man viel besser rechnen als mit 5, womit $5 [mm] \cdot Ind_2(x) \equiv [/mm] (-1) [mm] \cdot Ind_2(x) [/mm] = [mm] -Int_2(x) \pmod{6}$ [/mm] ist. Also hast du [mm] $-Ind_2(x) \equiv [/mm] 2 [mm] \pmod{6}$, [/mm] was aequivalent zu [mm] $Int_2(x) \equiv [/mm] -2 [mm] \pmod{6}$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:59 Mi 12.09.2012 | | Autor: | Peon |
ding dong, ja klar, natürlich. brett abgeschraubt, danke! :)
|
|
|
|
