algortm euklidesa

[nowik1991]

Witam serdecznie mam do rozwiązania następujące zadania... jedno z nich już zacząłem ale nie wiem jak skończyć a drugie chyba nie do końca rozumiem proszę o pomoc.


1)Znajdź \(\displaystyle{ 93^{-1}}\) w \(\displaystyle{ Z_{1223}}\)
2) Za pomocą rozszeżonego algorytmu Euklidesa znajdź a, b spełniające równanie:
znajdź takie \(\displaystyle{ a, b}\), że \(\displaystyle{ 312a + 403b = gcd(312, 403)}\)

2) \(\displaystyle{ NWD(312,403)}\)

\(\displaystyle{ 403=1 \cdot 312+91}\) \(\displaystyle{ r=91}\)
\(\displaystyle{ 312=3 \cdot 91+ 39}\) \(\displaystyle{ r=39}\)
\(\displaystyle{ 91=2 \cdot 39+13}\) \(\displaystyle{ r=13}\)
\(\displaystyle{ 39=3 \cdot 13+0}\) \(\displaystyle{ r=0}\)

Z tego wnioskujemy, że
\(\displaystyle{ 13 = 91-2 \cdot 39=91-2(312-3 \cdot 91)=403-312-2(312-3(403-312))=403-312-2(312-3 \cdot 403-3 \cdot -312))= 403-312-2 \cdot 312+6 \cdot 403-6 \cdot 312= 7 \cdot 403-9 \cdot 312}\)

Zatem \(\displaystyle{ a=-9}\) a \(\displaystyle{ b=7}\)

Proszę o pomoc.

[lightinside]

Nie wiem o co dokładnie chodzi w Twoim przykładzie 1, ale z tego co się spotkałam to zazwyczaj w takim wypadku, chodzi o to aby przedstawić podaną liczbę w ciele liczb w Twoim wypadku dość dużym to \(\displaystyle{ Z}\) to chyba chodzi o ciało

[nowik1991]

podpowiedź była taka:

x - elem. odwrotny do a mod n czyli:

\(\displaystyle{ a \cdot x=1}\)
\(\displaystyle{ 93x+k \cdot n=1}\)