Multiplikatives Inverses

Aufrufe: 36     Aktiv: 08.03.2021 um 19:59

0
Ich suche das multiplikative Inverse von 17 in 71Z.
Meine Idee ist, den Euklidischen Algorithmus anzuwenden. Ich habe mir mal überlegt, was zB das multiplikative Inverse von 2 in 5Z ist. Das wäre ja 3. Wieso? Weil 2 * 3 ergibt 6 und das ist in 5Z gleich der 1.

Ich hab rausgefunden, dass der ggT von 17 und 71 = 1 ist, also gibt es das mult. Inverse.
Außerdem hab ich rausgefunden, dass 1 = 71 * 6 + 17 * (-25) gilt.
Ich hätte gedacht, dass dann die 25 mein gesuchtes mult. Inverses ist, aber das haut nicht hin.
25 * 17 = 425 und das stimmt offensichtlich nicht.
Was ist mein Denkfehler und wie wäre es richtig?
Diese Frage melden
gefragt

Student, Punkte: 141

 

Kommentar schreiben

1 Antwort
1
Der Denkfehler ist, dass du hier das Minus nicht vergessen darfst. \( -25 \) ist das multiplikative Inverse zur \( 17 \). Die \( -25 \) entspricht in \( \mathbb{Z}/71\mathbb{Z} \) auch der \( 46 \) (das ist vielleicht schöner).

Zur Probe: \( 17 \cdot 46 = 782 = 1 \) in \( \mathbb{Z}/71\mathbb{Z} \).
Diese Antwort melden
geantwortet

Student, Punkte: 5.54K
 

Tatsächlich. Aber wie hätte ich schnell rausgefunden, dass -25 der 46 entspricht? In der Aufgabenstellung ist übrigens explizit angegeben, dass die Lösung nur zwischen 0 und 70 sein darf.   ─   akimboslice 08.03.2021 um 19:52

Hat sich erledigt.   ─   akimboslice 08.03.2021 um 19:59

Kommentar schreiben