Euklidischer Algorithmus: Eine ganze Zahl b finden

Question

Text erkannt:

Aufgabe 2. Benutze den euklidischen Algorithmus um eine ganze Zahl \( b \) zu finden, so dass
\( [6473]_{81} \cdot[b]_{81}=[1]_{81} \)

Ich weiß, dass :

6473 • b ≡ 1   (mod 81), also :     74 • b ≡ 1  (mod 81)

Wenn ich den Euklidischen Algor. formuliere sieht das so aus:

6473 = q • b + 1 | Wie gehe ich ab hier weiter vor?

b = q • 1 + r ??

Answer 1

Finde mit dem erweitertem Euklidischen Algorithmus \(x,y\in\mathbb Z\) mit \(74x+81y=1\).$$❶\quad81:74=1\text{ Rest }7\\\Longrightarrow7=81-1\cdot74$$$$❷\quad74:7=10\text{ Rest }4\\\Longrightarrow4=74-10\cdot7=74-10\cdot(81-1\cdot74)=11\cdot74-10\cdot81$$$$❸\quad7:4=1\text{ Rest }3\\\Longrightarrow3=7-1\cdot4=(81-1\cdot74)-1\cdot(11\cdot74-10\cdot81)=11\cdot81-12\cdot74$$$$❹\quad4:3=1\text{ Rest }1\\\Longrightarrow1=4-1\cdot3=(11\cdot74-10\cdot81)-1\cdot(11\cdot81-12\cdot74)=23\cdot74-21\cdot81.$$Damit ist \(23\cdot74\equiv1\bmod81\).