Inverses modulo n < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe folg. Kongruenz gegeben:
[mm] 84\equiv26 [/mm] mod 29. Ich suche hierfür das Inverse modulo 29. Ein Online-Programm hat mir gerade 19 ausgerechnet. Kann mir das jemand schrittweise erklären oder einen Link schicken, wo es einigermaßen vernünftig aufgeschrieben ist? Ich weiß, dass es mit dem erweiterten euklidischen Algorithmus geht, verstehe das aber nicht!
Vielen Dank schon mal.
Grüße Daniel
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:07 Fr 02.12.2005 | | Autor: | felixf |
> Hallo,
>
> ich habe folg. Kongruenz gegeben:
>
> [mm]84\equiv26[/mm] mod 29. Ich suche hierfür das Inverse modulo 29.
Wovon suchst du das Inverse? Von 84 bzw. 26?
> Ein Online-Programm hat mir gerade 19 ausgerechnet. Kann
> mir das jemand schrittweise erklären oder einen Link
> schicken, wo es einigermaßen vernünftig aufgeschrieben ist?
> Ich weiß, dass es mit dem erweiterten euklidischen
> Algorithmus geht, verstehe das aber nicht!
Weisst du wie man eine Bezout-Gleichung ausrechnet (bzw. was das ist)?
Nun sind 84 und 29 teilerfremd. (Ansonsten hat 84 kein Inverses modulo 29!) In diesem Fall ist der ggT also 1, womit es eine Bezout-Gleichung zu 84 und 29 gibt, etwa 1 = a * 84 + b * 29 fuer passende ganzzahlige a, b.
Wenn du die Gleichung jetzt modulo 29 betrachtest, steht da gerade $1 [mm] \equiv [/mm] a * 84 + b * 29 [mm] \equiv [/mm] a * 84 [mm] \pmod{29}[/mm], [/mm] da [mm]29 \equiv 0 \pmod{29}[/mm] ist. Aber damit ist a modulo 29 gerechnet das Inverse von 84! Und damit du nun als Ergebnis etwas zwischen 0 und 29 herausbekommt nimmst du anstelle a den Rest von a bei Division mit 29: das ist dann ''das'' Inverse modulo 29.
HTH, Felix
|
|
|
|
