Berechnen mult. Inv. mit Eukl < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe 1 | | In [mm] \IZ_{449} [/mm] multiplikativ Inverses von 208 |
| Aufgabe 2 | | In [mm] \IZ_{100} [/mm] multiplikativ Inverses von 37 |
Ich berechne die Aufgaben wie folgt mit dem erweiterten euklidischen Algorithmus:
[mm] \IZ_{449} [/mm] multiplikativ Inverses von 208
449 = 2 * 208 + 33
208 = 6 * 33 +10
33 = 3 * 10 + 3
10 = 3 * 3 +1
1 = 10 - 3 * 3 = 10 - 3 * (33 - 3 * 10)
= 10 * 10 - 3 * 33 = 10 * (208 - 6 * 33) - 3 * 33
= 10 * 208 - 63 * 33 = 10 * 208 - 63 * (449 - 2 * 208 )
= 136 * 208 - 63 * 449
MI von 208 = 136 da 136 * 208 = 28288 un 28288 mod 449 = 1
[mm] \IZ_{100} [/mm] multiplikativ Inverses von 37
100 = 2 * 37 + 26
37 = 1 * 26 + 11
26 = 2 * 11 + 4
11 = 2 * 4 + 3
4 = 1 * 3 + 1
1 = 4 - 1 * 3 = 4 - 1 * (11 - 2 * 4) = 3 * 4 - 1 * 11
= 3 * (26 - 2 * 11) - 1 * 11 = 3 * 26 - 7 * 11
= 3 * 26 - 7 * (37 - 1 * 26) = 10 * 26 - 7 * 37
= 10 * (100 - 2 * 37) - 7 * 37 = 10 * 100 - 27 * 37
MI von 37 ist aber 100 - 27 = 73 da 73 * 37 = 2701 und 2701 mod 100 = 1
Warum kann ich bei der ersten Rechnung das Ergebnis direkt ablesen und muss
bei der Zweiten erst noch den erhaltenen Faktor von der Ringgröße abziehen?
Ich finde das sehr verwirrend und tu mir schwer das zu verstehen...
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:22 Di 30.12.2008 | | Autor: | Weisswurst |
Auf die Sache mit 100 - 27 bin ich per Zufall gekommen.
Ich habe mir ein kleines Programm geschrieben, dass mir die Multiplikationstafel ausgibt.
Dort konnte ich dann das Ergebnis (73) einfach ablesen.
Zufällig habe ich dann gesehen, dass 100 - 27 auch 73 gibt. Ich dachte dann, dass das der
Weg wäre wie man das Inverse berechnet. Aber eben musste ich feststellen, dass dem scheinbar
nicht so ist.
Deshalb habe ich oben etwas von "verwirrend" geschrieben.
|
|
|
| |
|
Alles ist gut. Du hast auch völlig richtig gerechnet.
Nur beim Ablesen gibt es ein Problem.
Die beiden Lösungzeilen sind ja:
> 1 = 136 * 208 - 63 * 449
und
> 1= 10 * 100 - 27 * 37
Dabei habe ich die 1 vom Anfang der Gleichungskette noch mit hineingenommen und Deine letzte Markierung - Modul rot, Inverses blau - in die andere Gleichung mit übernommen.
Dir fällt sicher auf, dass die "Farbverteilung" unterschiedlich ist.
> Warum kann ich bei der ersten Rechnung das Ergebnis direkt
> ablesen und muss
> bei der Zweiten erst noch den erhaltenen Faktor von der
> Ringgröße abziehen?
Du kannst beide Male das Ergebnis direkt ablesen. Das Produkt, das die Ringgröße enthält, darfst Du in der modulo-Betrachtung ersatzlos streichen.
Dann steht im ersten Fall noch da [mm] \blue{136}*208\equiv 1\mod{449}
[/mm]
und im zweiten Fall [mm] \red{-}\blue{27}*37 \equiv 1\mod{100}
[/mm]
Das (hier rot markierte) Minus gehört mit zum Ergebnis!
Das ist meistens nicht gewünscht, deswegen nimmst Du [mm] \blue{-27}+100=73.
[/mm]
> Ich finde das sehr verwirrend und tu mir schwer das zu
> verstehen...
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
lg,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:41 Di 30.12.2008 | | Autor: | Weisswurst |
Achso :)
Bin ich froh, dass ich auf dieses Forum gestossen bin.
Wenn's so weiter geht schaff ich die Klausur doch noch :)
Vielen Dank!
|
|
|
|
