Bestimmen Sie das multiplikative Inverse von 17 im Z/31Z

Question

an sich ist es eigentlich einfach, aber irgendwo muss ich einen Fehler haben. Anscheinend ist es 11.

Ich hab aber 28 raus.

Mein Rechenweg

31 = 1* 17 +14

17 = 1* 14 +3

14= 4*3 +2

3 = 1*2 +1

2 = 2*1 +0

=> ggT(31,17)=1

Erweiterter Euklidischer Algorithmus:

1= 3-2 = 3-(14-4*3) = 5*3 -14 = 5*(17-14)-14

= 5*17 -6*14 = 5*17-6*(31-17) = 11*17 -6*31 +17*31-17*31 = 28*17 -23*31

Comments

1 = ... = 11*17 - 6*31

müsste doch reichen oder? 11 ist das Inverse zu 17.

Answer 1

es ist:

\(ggT(31,17)=1=3-2\cdot 1\\=3-1\cdot(14-4\cdot 3)=-1\cdot 14+5\cdot 3\\=-1\cdot 14+5\cdot (17-1\cdot 14)=-6\cdot 14+5\cdot 17\\=5\cdot 17-6\cdot (31-1\cdot 17)=\underbrace{11}_{\text{ Inverses }}\cdot 17-6\cdot 31\)

Du hast Dich nur verrechnet. Es ist doch: \(\underbrace{11}_{\text{ Inverses }}\cdot 17 -6\cdot 31 + \underbrace{17\cdot 31-17\cdot 31}_{=0}\)

André