euklidischer Algorithmus |
| 29.10.2011, 18:54 | DudiPupan | Auf diesen Beitrag antworten » | ||
| euklidischer Algorithmus ich habe da mal eine Frage: ich soll mithilfe des euklidischen Algorithmus und seiner Umkehrung das multiplikative Inverse von 5 in bestimmen. Mir fehlt der Ansatz, wie ich da am besten vorgehe. Vielen Dank |
||||
| 29.10.2011, 18:57 | lgrizu | Auf diesen Beitrag antworten » | ||
| RE: euklidischer Algorithmus Du suchst eine Zahl a aus Z/17Z für die gilt 5*a=1. Sicherlich ist der ggT von 5 und 17 eins, nun stelle den ggT dar in der Form 1=x*17+y*5, denn x*17 mod 17=0, also bleibt y*5 mod 17=1 |
||||
| 29.10.2011, 19:21 | DudiPupan | Auf diesen Beitrag antworten » | ||
Okay, dann habe ich x=-2 und y=7. Aber wie mache ich dann weiter? |
||||
| 29.10.2011, 20:15 | DudiPupan | Auf diesen Beitrag antworten » | ||
Ist y* 5mod17 nicht 2? |
||||
| 29.10.2011, 20:57 | lgrizu | Auf diesen Beitrag antworten » | ||
Okay, du hast richtig gerechnet, es ist Nun ist , also isst , das Inverse von 5 ist also 7. |
||||
| 30.10.2011, 10:40 | DudiPupan | Auf diesen Beitrag antworten » | ||
Okay, das ist mir jetzt irgendwie noch nicht all zu klar. Inverse von 5 ist 7? Aber du meintest doch vorhin, dass für die inverse gelten muss: 5*a=1, was für a=7 aber nicht zutrifft! |
||||
| Anzeige | ||||
|
|
||||
| 30.10.2011, 11:02 | ollie3 | Auf diesen Beitrag antworten » | ||
hallo dudipupan, ich misch mich hier mal ein. irgrizu hat völlig recht, 7 ist das inverse zu 5 im ring Z/17, denn es ist 5*7=35, und das ist kongruent zu 1 modulo 17 (denn 35=2*17+1). gruss ollie3 |
||||
| 30.10.2011, 13:23 | lgrizu | Auf diesen Beitrag antworten » | ||
Was rechnest du denn, dass das nicht zutrifft? Du musst das Ergebnis durch 17 teilen und den entstehenden Rest betrachten, gerade das ist doch modulo-Rechnung, Division mit Rest wie sie aus der Grunschule bekannt ist, es werden nur die entstehenden Reste betrachtet, also die Restklassen (in diesem Fall modulo 17). Zwei Elemente aus Z liegen genau dann in der selben Restklasse, wenn sie bei Division durch 17 den gleichen Rest hinterlassen und gesucht ist die Restklasse, die die 1 enthält, in dieser Restklasse liegt auch die 35, sie bestaht aus den Elementen für z aus Z. |
||||
| 30.10.2011, 17:34 | DudiPupan | Auf diesen Beitrag antworten » | ||
Okay, jetzt hab ich es so einigermaßen verstanden 
Ist dann das Inverse von 7 in Z/25Z -7? Stimmt das? |
||||
| 30.10.2011, 18:03 | lgrizu | Auf diesen Beitrag antworten » | ||
Jap, ist richtig, man kann jetzt noch den kleinsten positiven Repräsentanten der Restklasse wählen, in der -7 liegt. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
