Kongruencja - znaleźć x

[szymonides]

Mam za zadanie znaleźć \(\displaystyle{ x}\) z takiego równania: \(\displaystyle{ 23x \equiv_{47} 1}\). Jak to szybko wyliczyć?

Jedyne co przychodzi mi do głowy to sprawdzać dzielenie modulo każdej liczby od \(\displaystyle{ x = 1}\) do \(\displaystyle{ x = 46}\), ale to chyba nie tędy droga...

[Premislav]

Korzystając z rozszerzonego algorytmu Euklidesa, możesz łatwo znaleźć takie całkowite \(\displaystyle{ x,y}\), że
\(\displaystyle{ 23x+47y=1}\). Wtedy iksy z tej równości będą spełniały kongruencję, którą rozważasz.