Question

Bestimmen Sie die multiplikative inverse von 17 in ℤ/71ℤ.

Answer 1

Erweiterter Euklidischer Algorithmus

https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

a	b	q	s	t
71	17	4	6	-25
17	3	5	-1	6
3	2	1	1	-1
2	1	2	0	1
1	0		1	0

71*6 + 17*(-25) = 1

Das multiplikativ Inverse ist -25 bzw. 46.

Comments

danke ich verstehe alles aber nur nicht wie man auf 46 kommt ?

---

Du darfst zu -25 Vielfache von 71 addieren.

-25 + 71 = 46

Solange du Modulo 71 rechnest darfst du zu jedem Wert 71 hinzuzählen oder abziehen.