Modulo liczby do minusowej potęgi.

[Michalgromadzki]

Ile to będzie \(\displaystyle{ 17^{-3}=x(mod 31)}\) i jak się wylicza modulo liczby do minusowej potęgi?

-- 12 lut 2011, o 13:39 --

Widzę, że nikt mi nie pomoże, to proszę chociaż o sprawdzenie:
\(\displaystyle{ 17^{-3}=x(mod 31)}\)
\(\displaystyle{ 17x=3(mod 31)}\)
\(\displaystyle{ 17*2=3(mod 31)}\)
\(\displaystyle{ 34=3(mod 31)}\)
\(\displaystyle{ x=2}\)

[ares41]

może to cię naprowadzi na to gdzie robisz błąd:
\(\displaystyle{ 17^{-3} \not\in \mathbb Z}\)

[Michalgromadzki]

może to cię naprowadzi na to gdzie robisz błąd:
\(\displaystyle{ 17^{-3} \not\in \mathbb Z}\)

No ale że o co chodzi ?
Wiem, że \(\displaystyle{ 17^{-3} \not\in \mathbb Z}\), bo to będzie jakiś tam ułamek... pytanie ile to będzie w ciele \(\displaystyle{ Z_{31}}\)?
Na zajęciach mieliśmy tylko jeden przykład \(\displaystyle{ 2^{-1}=3(mod 5)}\), bo \(\displaystyle{ 2*3=1(mod5)}\)... próbowałem więc tym sposobem rozkminiać.

[ares41]

hmh,... wydaje mi się można to tak zrobić:
\(\displaystyle{ 17^{-3} \equiv x(\text{mod} \ 31)\\ \\ 17x \equiv 3 (\text{mod} \ 31) \equiv 34 (\text{mod} \ 31)}\)

wiemy, że:
\(\displaystyle{ \bigwedge_{{a \in \mathbb Z}} a \equiv a (\text{mod} \ 31)}\),
więc:
\(\displaystyle{ 17x=34}\),
a z tego:
\(\displaystyle{ x=2}\)

PS. nie jestem stuprocentowo pewien tego rozwiązania, ale myślę że jest ok.

pozdrawiam
ares41

[abc666]

\(\displaystyle{ NWD(17,31)=1}\)
Element odwrotny do 17 znajdujesz przy pomocy algorytmu Euklidesa. Mamy
\(\displaystyle{ 17\cdot 11-6\cdot 31 =1\\
11^3=29 \pmod{31}\\
x=29}\)