Inverse von 5 in Z13

Question

Ich probiere gerade die Inverse von 5 in Z13 zu bestimmen, jedoch scheitere ich kläglich.

Ich gehe über den Euklidischen Algorithmus. Ist dies hier nicht möglich oder muss man hier den Satz von Fermat-Euler anwenden?

Answer 1

Hallo Mikita,

wenn Du den erweiterten Euklidischen Algorithmus nutzt, so wie hier beschreiben, dann erhältst Du die Tabelle$$\begin{array}{rrr|rr}a& b& q& s& t\\ \hline 5& 13& 0& \colorbox{#ffff00}{-5}& 2\\ 13& 5& 2& 2& -5\\ 5& 3& 1& -1& 2\\ 3& 2& 1& 1& -1\\ 2& 1& 2& 0& 1\\ 1& 0& & 1& 0\end{array}$$Somit ist$$5 \cdot (-5) + 13 \cdot 2 = 1 \implies 5 \cdot (-5)  \equiv 1 \mod 13$$Die inverse von \(5\) wäre damit \(-5\) was im \(\mathbb Z_{13}\) einer \(8\) entspricht: $$- 5 \equiv 8 \mod 13$$... aber wie schon erwähnt, ist es bei so kleinen Zahlen ggf. einfacher, die Zahlen \(1\) bis \(12\) durch zu probieren.

Answer 2

Du suchst eine ganze Zahl z mit 5z ≡1 mod 13.

Dazu musst du für z nur die Zahlen 0 bis 12 durchprobieren, denn danach wiederholt sich alles.

Fündig wirst du bei z=8, denn 40 ≡1 mod 13.

Answer 3

Bei so kleinen Zahlen kannst du doch einfach probieren

 5* x ≡ 1  mod (13 )

x01 oder x=2 oder x03 oder x=4 oder x=5

tun es schon mal nicht, wie man leicht im Kopf rechnet.

für 6, 7 ,8 gibt

5*x dann ja 30 , 35 , 40 und bei der

40 hast du 3*13 + 1.

Also ist die 8 das Inverse von 5.