Dzielenie modulo

[Sizer]

Witam.
Mam pewien problem. Mamy pewną dużą liczbę \(\displaystyle{ x}\) (przyjmijmy, że ta liczba jest za duża, żeby ją zapisać). Znamy jej resztę z dzielenia modulo \(\displaystyle{ p}\). Innymi słowy wiemy, że \(\displaystyle{ x \equiv k \pmod{p}\right)}\), gdzie \(\displaystyle{ p}\) jest liczbą pierwszą. Chcemy obliczyć \(\displaystyle{ \frac{x}{n} \mod \ p}\), dla jakiegoś \(\displaystyle{ n \in \mathbb{N}}\). Jak to zrobić? Słyszałem, że trzeba użyć odwrotności modulo, ale nie wiem jak się do tego zabrać

[Janusz Tracz]

O elementach odwrotnych w arytmetyce \(\displaystyle{ \mod p}\) można mówić w oderwaniu od "dużych liczb". Można więc na chwile zapomnieć o problemie z \(\displaystyle{ x}\) i kłopotami jakie rodzi zapis \(\displaystyle{ \frac{x}{n}\mod p}\). Sama definicja elementu odwrotnego do \(\displaystyle{ a}\) mówi, że jest to taki element \(\displaystyle{ a^{-1}}\), że \(\displaystyle{ aa^{-1}\equiv1\bmod p}\) oczywiście nie jest to ogólna definicja elementu odwrotnego a jej szczególna postać dla arytmetyki \(\displaystyle{ \mod p}\). O istnieniu takiego elementu mówi lemat Bezouta a warunkiem jest by \(\displaystyle{ a,p}\) były względnie pierwsze. Zatem jeśli liczby \(\displaystyle{ n,p}\) są względnie pierwsze to \(\displaystyle{ n}\) ma element odwrotny taki, że \(\displaystyle{ nn^{-1}\equiv1\bmod p}\) i można go policzyć stosując odwrotny algorytm Euklidesa do liczb \(\displaystyle{ n,p}\). Gdy mamy \(\displaystyle{ n^{-1}}\) to kongruencję \(\displaystyle{ x\equivk\bmod p}\) można pomnożyć przez \(\displaystyle{ n^{-1}}\) wtedy dostaniemy do czego przystaje \(\displaystyle{ \frac{x}{n}\mod p}\)