multiplikativ Inverse < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:12 Mo 22.01.2007 | | Autor: | erdoes |
Hallo alle zusammen,
habe nochmals eine Frgae, die mich brennend interessiert :
Wie berechnet man mit dem Erweiterten Euklidischen Algorithmus das multiplikative Inverse einer Restklasse in einem Restklassenring ?
z.B.: multiplikative Inverse von 3 in [mm] \IZ [/mm] \ [mm] 20\IZ
[/mm]
Danke schon mals
MfG
erdoes
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:27 Di 23.01.2007 | | Autor: | statler |
Guten Tag!
> Wie berechnet man mit dem Erweiterten Euklidischen
> Algorithmus das multiplikative Inverse einer Restklasse in
> einem Restklassenring ?
>
> z.B.: multiplikative Inverse von 3 in [mm]\IZ[/mm] \ [mm]20\IZ[/mm]
Du mußt dazu doch die Gleichung 3x [mm] \equiv [/mm] 1 mod20 lösen,
also 3x - 1 = 20y oder 3x - 20y = 1.
Nun ist
20 = 6*3 + 2 und
3 = 1*2 + 1
(Das ist der Euklid. Alg.)
Rückwärts eingesetzt ergibt das 1 = 3 - 1*2 = 3 - 1*(20 - 6*3) = 3*7 - 20*1.
Also ist 7 das Inverse zu 3.
Gruß aus HH-Harburg
Dieter
|
|
|
|
