Rozwiąż równanie w ciele liczb Zn

[gruch]

Witam, mam zadanie,
rozwiąż równanie w ciele liczb \(\displaystyle{ Z_{47}}\)
Równanie wygląda następująco:
\(\displaystyle{ 13x=35}\)

Jaki jest ogólny algorytm na rozwiązywanie takich zadań?

[Qń]

Jeśli znajdziesz taką liczbę \(\displaystyle{ a}\), że \(\displaystyle{ 13a=1}\), to będzie wystarczyło pomnożyć równanie stronami przez \(\displaystyle{ a}\). Taka liczba \(\displaystyle{ a}\) (czyli odwrotność trzynastki w tym ciele) może być znaleziona przy pomocy rozszerzonego algorytmu Euklidesa, który pozwala nam wyznaczyć takie liczby \(\displaystyle{ k,l}\), że \(\displaystyle{ 13k+35l=1}\).

Q.

[Vax]

Wyznaczamy element odwrotny do \(\displaystyle{ 13}\) w \(\displaystyle{ Z_{47}}\) i mnożymy przez niego nasze równanie, aby go wyznaczyć możemy posłużyć się rozszerzonym algorytmem Euklidesa (na forum było o tym wiele razy np tutaj 39038.htm?hilit=rozszerzonego%20algorytmu%20euklidesa), korzystając z niego otrzymujemy \(\displaystyle{ 13^{-1} = 29}\), na koniec mnożąc nasze równanie przez \(\displaystyle{ 29}\) otrzymujemy \(\displaystyle{ x = 28}\)

Pozdrawiam.

PS.