kongruenzen lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Bestimme das kleinste positive $x [mm] \in \IZ$ [/mm] mit
$ 54x [mm] \equiv [/mm] 1 $ mod 173 |
hey,
wie gehe ich solche Aufgaben ran?
Erweiterter Euklidischer Algorithmus?
Wenn ja kann man mir einer Starthilfe geben? als Lösung soll 157 raus kommen.
MfG
|
|
| |
|
Hallo Striker,
ja, erweiterter euklidischer Algorithmus ist gut. Probiers mal aus und frag nach, wenn Du steckenbleibst.
Allerdings...
> Bestimme das kleinste positive [mm]x \in \IZ[/mm] mit
>
> [mm]54x \equiv 1 [/mm] mod 173
> hey,
> wie gehe ich solche Aufgaben ran?
> Erweiterter Euklidischer Algorithmus?
> Wenn ja kann man mir einer Starthilfe geben? als Lösung
> soll 157 raus kommen.
...gibt es noch einen einfacheren Weg.
Zuerst musst Du natürlich sicherstellen, dass [mm] \ggT{(54,173)}=1 [/mm] ist. Das ist hier erfüllt. Außerdem ist 173 prim, da kann also eigentlich nichts schiefgehen, wenn Du mechanisch vorgehst, s.o.
Da es hier aber letztlich darum geht, das Inverse von 54 [mm] \bmod{173} [/mm] zu bestimmen, geht es eben auch noch einfacher.
Es gilt ja $54=6*9$ und [mm] 173=-1\bmod{6}.
[/mm]
Sei [mm] \overline{54} [/mm] das Inverse von 54, also [mm] 54*\overline{54}\equiv 1\bmod{173}. [/mm]
Dann gilt auch [mm] 54*\overline{54}\equiv 6*9*\overline{6}*\overline{9}\bmod{173}.
[/mm]
Da wir wissen, dass 173+1 durch 6 teilbar ist, ist also 174/6 das Inverse von 6. [mm] \rightarrow\quad \overline{6}\equiv 29\bmod{173}
[/mm]
Andererseits ist 173+1 nicht durch 9 teilbar, aber es ist sehr leicht zu ermitteln, dass 4*173+1 durch 9 teilbar ist (überleg mal, was daran einfach ist).
Also ist (4*173+1)/9 das Inverse von 9 bzw. [mm] \overline{9}\equiv 77\bmod{173}
[/mm]
Und damit bist Du ja praktisch schon am Ziel.
Probier aber unbedingt auch die "mechanische" Lösung über den erw. Euklidischen Algorithmus.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:58 Do 23.04.2015 | | Autor: | Marcel |
Hallo,
> Bestimme das kleinste positive [mm]x \in \IZ[/mm] mit
>
> [mm]54x \equiv \red{1} [/mm] mod 173
> hey,
> wie gehe ich solche Aufgaben ran?
> Erweiterter Euklidischer Algorithmus?
> Wenn ja kann man mir einer Starthilfe geben? als Lösung
> soll 157 raus kommen.
es gilt folgender Satz (4.8 in "Elementare und algebraische Zahlentheorie
von Müller-Stach/Piontkowski"):
Gegeben sei die Gleichung
$ax [mm] \equiv [/mm] b [mm] \mod [/mm] n$ mit $a,b [mm] \in \IZ$ [/mm] und $n [mm] \in \IN.$
[/mm]
Sei [mm] $d:=\ggT(a,n)$.
[/mm]
1. Falls $d [mm] \nmid [/mm] b$, dann besitzt die Gleichung keine Lösung.
2. Sei $d [mm] \mid b\,.$ [/mm] Wähle $y,z [mm] \in \IZ$ [/mm] mit $ya+zn=d$ (etwa mit Hilfe des
euklidischen Alg.). Dann ist obige Gleichung gleichwertig mit
$x [mm] \equiv [/mm] y [mm] \frac{b}{d} \mod \frac{n}{d}$ [/mm] (und hat damit eine Lösung).
Das kleinste $x [mm] \in \IN$, [/mm] dass die letzte Gleichung erfüllt, bekommst Du dann
sicher selbst berechnet.
Also: Vorgehen mit diesem Satz:
I) [mm] $\ggT(54,173)=1\,.$ [/mm] Offenbar $1 [mm] \mid b=\red{1}\,.$ [/mm] Weiter ist [mm] $a=54\,,$ $b=1\,$ [/mm] und [mm] $n=173\,.$
[/mm]
Ergebnis des ![[a]](/images/paperclip.gif "Dateianhänge") eukl. Algorithmus (Matlab):
[mm] $1=(-16)*54+5*173\,,$ [/mm] also $y=-16$ (und $z=5$).
Zur obigen Kongruenz gleichwertig ist also
$x [mm] \equiv (-16)*\frac{1}{1} \mod \frac{173}{1}$
[/mm]
Der Rest ist klar, oder?
P.S. Das Matlab-Programm läuft auch in Octave - ich empfehle allerdings,
nicht direkt Octave, sondern cygwin und dann Octave in Cygwin nachzu-
installieren (nachladen). Evtl. kannst Du den Quellcode auch anschauen
und in eine andere Programmiersprache (python?) übertragen.
Ich glaube, der Code, so, wie er dort steht, passt zu dem aus dem Buch von
Johannes Buchmann: Einführung in die Kryptographie.
Gruß,
Marcel
Dateianhänge:
Anhang Nr. 1 (Typ: m) [nicht öffentlich]
|
|
|
| |
|
Hallo,
ja habe doch noch ein Problem bei der Aufgabe
ggT(173,54)
$173= 3 *54 +11$
$54 = 4*11+10$
$11= 1*10+1$
$10 = 10*1+0$
beim "rückwärts" durchgehen habe ich mein Problem:
$ 1 = 11-1*10 = 11-1*(54-4*11) = $ und nun komme ich irgendwie nicht weiter
wie kommt man am ende auf die Lösung von 157?
ps: sry marcel ich finde es ist noch nicht klar ^^ aber vielen dank für deine Antwort.
LG
|
|
|
| |
|
Hallo,
> ggT(173,54)
>
> [mm]173= 3 *54 +11[/mm]
> [mm]54 = 4*11+10[/mm]
> [mm]11= 1*10+1[/mm]
> [mm]10 = 10*1+0[/mm]
>
> beim "rückwärts" durchgehen habe ich mein Problem:
>
> [mm]1 = 11-1*10 = 11-1*(54-4*11) =[/mm] und nun komme ich irgendwie
> nicht weiter
1=5*11 - 54
1=5*(173-3*54) -54
1= 5*173 -16*54
Da [mm] \overline{-16}=\overline{157} \in \IZ_{173} [/mm] ist, ist [mm] \overline{157}=\overline{54}^{-1} \in \IZ_{173}.
[/mm]
Viele Grüße
|
|
|
| |
|
Danke, bei aufgabenteil b) ist wieder dasselbe Problem dar.
ggT(201,154)
$201=1*154+47$
$154=3*47+13$
$47=3*13+5$
$13=1*8+5$
$8=1*5+3$
$5=1*3+2$
$3= 1*2+1$
$2= 2*1+0$
dann $1 = 3-1*2 = 3-1*(5-1*3) =$ nun komme ich wieder durcheinander und weiß nicht was ich machen soll..
die 3 kann ich schreiben als $8-1*5$ usw. aber keine ahnung wie ich das umschreiben soll..
das Ergebnis ist halt $x=124$.
LG
|
|
|
| |
|
Hallo nochmal,
> ggT(201,154)
>
> [mm]201=1*154+47[/mm]
> [mm]154=3*47+13[/mm]
> [mm]47=3*13+5[/mm]
> [mm]13=1*8+5[/mm]
> [mm]8=1*5+3[/mm]
> [mm]5=1*3+2[/mm]
> [mm]3= 1*2+1[/mm]
> [mm]2= 2*1+0[/mm]
>
Zeile 3 soll wohl heißen:
47=3*13+8
Beim rückwärts rechnen immer gucken, welche Zahl als nächstes in der Gleichung wegfällt:
1=3-2 da 2 als erstes wegfällt, ersetzen:
1=3-(5-3)
1=2*3-5, da 3 als nächstes wegfällt, ersetzen:
1=2*(8-5)-5
1=2*8 - 3*5, da 5 als nächstes wegfällt, ersetzen:
1=2*8 - 3*(13-8)
1=5*8 - 3*13, da 8 als nächstes wegfällt, ersetzen:
1=5*(47-3*13) - 3*13
1=5*47 -18*13, da 13 als nächstes wegfällt, ersetzen:
1=5*47 -18*(154-3*47)
1= 59*47 -18*154, da 47 als nächstes wegfällt, ersetzen:
1=59*(201-154) -18*154
1=59*201 - 77*154
Damit ist [mm] \overline{-77} =\overline{124}= \overline{154}^{-1} \in \IZ_{201}
[/mm]
Viele Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:24 Mo 27.04.2015 | | Autor: | Marcel |
Hallo,
> Danke, bei aufgabenteil b) ist wieder dasselbe Problem dar.
>
> ggT(201,154)
>
> [mm]201=1*154+47[/mm]
> [mm]154=3*47+13[/mm]
> [mm]47=3*13+5[/mm]
> [mm]13=1*8+5[/mm]
> [mm]8=1*5+3[/mm]
> [mm]5=1*3+2[/mm]
> [mm]3= 1*2+1[/mm]
> [mm]2= 2*1+0[/mm]
>
> dann [mm]1 = 3-1*2 = 3-1*(5-1*3) =[/mm] nun komme ich wieder
> durcheinander und weiß nicht was ich machen soll..
> die 3 kann ich schreiben als [mm]8-1*5[/mm] usw. aber keine ahnung
> wie ich das umschreiben soll..
> das Ergebnis ist halt [mm]x=124[/mm].
vielleicht interessiert Dich ja auch eine Herleitung der Formel für die Koeffizienten?
Mein Zusammenschrieb
Gruß,
Marcel
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:17 Mo 27.04.2015 | | Autor: | Marcel |
Hallo,
> Hallo,
>
> ja habe doch noch ein Problem bei der Aufgabe
>
> ggT(173,54)
>
> [mm]173= 3 *54 +11[/mm]
> [mm]54 = 4*11+10[/mm]
> [mm]11= 1*10+1[/mm]
> [mm]10 = 10*1+0[/mm]
>
> beim "rückwärts" durchgehen habe ich mein Problem:
>
> [mm]1 = 11-1*10 = 11-1*(54-4*11) =[/mm] und nun komme ich irgendwie
> nicht weiter
>
> wie kommt man am ende auf die Lösung von 157?
>
> ps: sry marcel ich finde es ist noch nicht klar ^^ aber
> vielen dank für deine Antwort.
dafür brauchst Du Dich nicht zu entschuldigen - Rückfragen zeigen, dass
Du selbstständig nachdenkst. 
Btw.: Ich habe ja auch den eukl. Alg. fertig programmiert zur Verfügung
gestellt, einfach, weil ich auch zu faul war, alles vorzurechnen. Ich würde
das hier genauso wie Du von Hand machen (wollen), wäre ich an Deiner
Stelle.
Gruß,
Marcel
|
|
|
|
