Erw. Eukl. Alg. Inverse < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:08 So 02.09.2012 | | Autor: | Jack159 |
Hallo,
Ich habe glaube ich noch nicht so ganz verstanden, wie man an die Inverse beim Erweiterten Euklidischen Algorithmus kommt.
Dazu hier 2 Beispiele.
1. Beispiel (Hier verstehe ich alles):
Es soll die modulare Inverse c berechnet werden, sodass gilt: 13*c=1 (mod 160)
Euklidischer Algorithmus:
160=12*13+4
13=3*4+1
4=4*1+0
Erweiteter Euklidischer Algorithmus:
1=13-3*(160-12*13)=13-3*160+36*13=37*13-3*16
Modulare Inverse c=37
Probe:
13*37=481=1 (mod 160)
--------------------------------------------------------------------------------------
2. Beispiel (hier habe ich ein Problem):
Es soll die modulare Inverse c berechnet werden, sodass gilt: 5*c=1 (mod 48)
Euklidischer Algorithmus:
48=9*5+3
5=1*3+2
3=1*2+1
2=2*1+0
Erweiteter Euklidischer Algorithmus:
1=3-1*(5-1*3)=3-1*5+1*3=2*3-1*5=2*48-18*5-1*5=2*48-19*5
Modulare Inverse c=-19
Probe:
5*(-19)=-95=-47 (mod 48)
c=-19 scheint also falsch zu sein?! Wo liegt mein Fehler?
|
|
| |
|
Hallo Jack,
nach wie vor: es geht nicht um Reste, sondern um Restklassen.
Du hast alles richtig gemacht.
Am Ende musst Du bedenken/erkennen, dass [mm] -47\equiv 1\mod{48} [/mm] ist.
Vielleicht wäre es daher auch besser, nicht -19 als Inverses zu [mm] 5\mod{48} [/mm] anzugeben, sondern den Hauptrepräsentanten der Restklasse, also 29, denn [mm] 29\equiv -19\mod{48}.
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:00 So 02.09.2012 | | Autor: | Jack159 |
> Am Ende musst Du bedenken/erkennen, dass [mm]-47\equiv 1\mod{48}[/mm]
> ist.
Ahh ok, jetzt weiß ich wie man darauf kommt:
-95 ist kongruent modulo 48 zu allen Zahlen, die sich von -95 um
ein Vielfaches von 48 unterscheiden.
[mm] 48\equiv-47\equiv1 [/mm] (mod 48)
> Vielleicht wäre es daher auch besser, nicht -19 als
> Inverses zu [mm]5\mod{48}[/mm] anzugeben, sondern den
> Hauptrepräsentanten der Restklasse, also 29, denn [mm]29\equiv -19\mod{48}.[/mm]
Dasselbe gilt dann auch hier:
-19 ist kongruent modulo 48 zu allen Zahlen, die sich von -19 um
ein Vielfaches von 48 unterscheiden.
[mm] -19\equiv29\equiv77 [/mm] (mod 48)
Diesen kleinen Satz sollte ich einfach Auswendig lernen, denn ich komme da ziemlich schnell durcheinander...
Danke schonmal bis hierhin ;)
1 kleine Frage habe ich noch:
Wenn ich das ganze in der Klausur nun formal/mathematisch sauber und korrekt hinschreiben will:
(Ich hab jetzt den erweiterten Eukl. Alg. angewandt und habe rausbekommen):
1=2*48-19*5
Somit gilt:
-19*5=1 (mod 48) |+48*5
29*5=1 (mod 48)
Wäre diese Rechnung mathematisch korrekt aufgeschrieben?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:54 So 02.09.2012 | | Autor: | leduart |
Hallo
richtig aufgeschrieben!
andere Möglichkeit ist -19=48-19=29 mod 48
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:12 So 02.09.2012 | | Autor: | teo |
> Hallo
> richtig aufgeschrieben!
> andere Möglichkeit ist -19=48-19=29 mod 48
> Gruss leduart
Hallo, ich wollt nur auf eins kurz hinweisen. Es muss eigentlich -19 [mm] \equiv [/mm] 48 -19 = 29 mod 48 sein. Denn -19 [mm] \not= [/mm] 48-19 und 48-19 = 29.
Grüße
|
|
|
|
