Arytmetyka Modularna

[AdamPpp]

Mam takie zadanie:
Dla danego \(\displaystyle{ a}\) i \(\displaystyle{ n}\) takiego, że \(\displaystyle{ NWD(a,n)= 1}\) znaleźć \(\displaystyle{ x}\) takie, że : \(\displaystyle{ a\cdot x \equiv 1 \mod n.}\)
Przykład: par \(\displaystyle{ (a,n): (3,4), (4,3), (8,5), (5,8)}\)

Kto pomoże mi to rozwiązać? Albo powie jak się za to w ogóle zabrać.

[robertm19]

Przykładowo dla \(\displaystyle{ (3,4)}\). Szukasz elementu odwrotnego do a, czyli takiego \(\displaystyle{ b}\), że \(\displaystyle{ a\cdot b =1\ \mod 4}\).
Reszty z dzielenia przez \(\displaystyle{ 4}\) masz tylko \(\displaystyle{ 4: 0,1,2,3.}\)
Mnóż \(\displaystyle{ a}\) przez każdą możliwą resztę. Tam gdzie w mnożeniu wyjdzie \(\displaystyle{ 1\mod 4}\) tam znajdziesz element odwrotny.
np
\(\displaystyle{ 3\cdot 0=0\ \mod4}\)
\(\displaystyle{ 3\cdot 1=3\ \mod4}\)
\(\displaystyle{ 3\cdot 2=2\ \mod4}\)
\(\displaystyle{ 3\cdot 3=1\ \mod4}\)
\(\displaystyle{ 3}\) to odwrotny do \(\displaystyle{ 3}\), więc rozwiązanie.

[AdamPpp]

Czyli np. do pary \(\displaystyle{ NWD(8,5)}\)
\(\displaystyle{ NWD(a,n)= 1}\)

\(\displaystyle{ a\cdot x \equiv 1 \mod n.}\)

\(\displaystyle{ 8\cdot x =1\ \mod 5}\)

Reszty z dzielenia przez \(\displaystyle{ 5}\) mam: \(\displaystyle{ 0,1,2,3,4}\)
I mnożę:
\(\displaystyle{ 8\cdot 0=0\ \mod5}\)
\(\displaystyle{ 8\cdot 1=3\ \mod5}\)
\(\displaystyle{ 8\cdot 2=1\ \mod5}\)
\(\displaystyle{ 8\cdot 3=4\ \mod5}\)
\(\displaystyle{ 8\cdot 4=2\ \mod5}\)

I wychodzi mi że \(\displaystyle{ x=2}\)

Nie wiem czy dobrze to zrozumiałem.

[robertm19]

Tak, bo \(\displaystyle{ 2\cdot 8=1\quad mod 5}\)

[Alister]

Polecam zapoznać się z rozszerzonym algorytmem Euklidesa. To jest najlepszy sposób na znajdywanie takiej liczby \(\displaystyle{ x}\) dla dużych \(\displaystyle{ a}\) i \(\displaystyle{ n}\), które ciężko by było rozwiązać przez zwykłe podstawianie.

[AdamPpp]

Dziękuje za pomoc