równanie modulo

[madziula1784]

Znaleźć x jeśli:
\(\displaystyle{ x ^{100}\equiv2\left( mod73\right)}\)

[fon_nojman]

\(\displaystyle{ x=\sqrt[100]{75}.}\)

[Qń]

\(\displaystyle{ x=\sqrt[100]{75}.}\)

Jesteś pewien?

Q.

[madziula1784]

a skąd się wziął ten wynik?

[cosinus90]

\(\displaystyle{ x^{100}}\) jest resztą z dzielenia \(\displaystyle{ 2:73}\).
Kolega fon_nojman coś musiał pomylić.

[Xitami]

2, 19, 54, 71

[Vax]

Trochę długi sposób, ale na razie nic lepszego nie mam:

\(\displaystyle{ x^{100} \equiv 2 \pmod{73}}\)

\(\displaystyle{ x^{100} \equiv 32^2 \pmod{73}}\)

\(\displaystyle{ (x^{50}-32)(x^{50}+32) \equiv 0 \pmod{73}}\)

\(\displaystyle{ x^{50} \equiv 32\pmod{73} \vee x^{50} \equiv 41\pmod{73}}\)

\(\displaystyle{ x^{50} \equiv 18^2\pmod{73} \vee x^{50} \equiv 25^2\pmod{73}}\)

\(\displaystyle{ (x^{25}-18)(x^{25}+18)\equiv 0\pmod{73} \vee (x^{25}-25)(x^{25}+25) \equiv 0 \pmod{73}}\)

\(\displaystyle{ x^{25} \equiv 18\pmod{73} \vee x^{25} \equiv 55\pmod{73} \vee x^{25} \equiv 25\pmod{73} \vee x^{25} \equiv 48\pmod{73}}\)

Z mtf mamy \(\displaystyle{ x^{72} \equiv 1 \pmod{73}}\)

Stąd nasze kongruencje można zapisać w postaci: (niestety zachodzi implikacja w jedną stronę, więc na końcu wszystkie rozwiązania trzeba będzie sprawdzić)

\(\displaystyle{ x^3 \equiv 65 \pmod{73} \vee x^3 \equiv 8\pmod{73} \vee x^3 \equiv 3\pmod{73} \vee x^3 \equiv 70\pmod{73}}\)

\(\displaystyle{ x^3 \equiv 18^3 \pmod{73} \vee x^3 \equiv 2^3 \pmod{73} \vee x^3 \equiv 25^3 \vee x^3 \equiv 6^3 \pmod{73}}\)

\(\displaystyle{ (x-18)(x^2+18x+32) \equiv 0\pmod{73} \vee (x-2)(x^2+2x+4) \equiv 0\pmod{73} \vee (x-25)(x^2+25x+41) \equiv 0\pmod{73} \vee (x-6)(x^2+6x+36) \equiv 0\pmod{73}}\)

\(\displaystyle{ (x-18)(x-57)(x-71) \equiv 0\pmod{73} \vee (x-2)(x-16)(x-55) \equiv 0\pmod{73} \vee (x-25)(x-54)(x-67) \equiv 0\pmod{73} \vee (x-6)(x-19)(x-48) \equiv 0\pmod{73}}\)

Skąd wynika, że możliwe jest jedynie:

\(\displaystyle{ x \equiv A \pmod {73}}\)

gdzie \(\displaystyle{ A \in \lbrace2;6;16;18;19;25;48;54;55;57;67;71\rbrace}\)

Jednak bezpośrednie sprawdzenie daje nam:

\(\displaystyle{ x \equiv 2 \pmod{73} \vee x\equiv 19\pmod{73} \vee x\equiv 54\pmod{73} \vee x\equiv 71\pmod{73}}\)

Pozdrawiam.

[Rogal]

Skoro MTF mówi, że \(\displaystyle{ x^{72} = 1 (mod \ 73)}\), to \(\displaystyle{ x^{100} = x^{72} \cdot x^{28} = 2 (mod \ 73) \Leftrightarrow x^{28} = 2 (mod \ 73)}\)
I teraz można by się pobawić w szukanie kwadratu (wszelkie równości są modulo 73):
\(\displaystyle{ x^{28} = 2 = 148 = 4 \cdot (37) = 4 \cdot (110) = 4 \cdot (256) = (2 \cdot 16)^{2} = 2^{10} \\
(x^{14} - 2^{5})(x^{14} + 2^{5}) = 0 \\
x^{14} = 32 \vee x^{14} = -32 \\
x^{14} = 105 \vee x^{14} = 41 \\
x^{14} = 251 \vee x^{14} = 187 \\
x^{14} = 324 \vee x^{14} = 260 \\
(x^{7} - 18)(x^{7} + 18) \vee x^{14} = 4 \cdot (65) \\
x^{7} = 18 \vee x^{7} = -18 \vee x^{14} = 4 \cdot (138) \\
x^{7} = 18 \vee x^{7} = 55 \vee x^{14} = 4 \cdot (284) \\
x^{7} = 18 \vee x^{7} = 128 \vee x^{14} = 4 \cdot 4 \cdot 71 \\
x^{7} = 18 \vee x = 2 \vee x^{14} = 16 \cdot 144 \\
x^{7} = 18 \vee x = 2 \vee x^{14} = (48)^{2} \\
x^{7} = 18 \vee x = 2 \vee (x^{7} - 48)(x^{7} + 48) = 0 \\
x = 2 \vee x^{7} = 18 \vee x^{7} = 48 \vee x^{7} = 25}\)

Stąd mamy rozwiązanie x = 2 (mod 73) i automatycznie x = 71 (mod 73) (niestety nie widać, które z tych równań powyżej opisuje to rozwiązanie).
Jak poradzić sobie z pozostałymi równaniami, nie mam pojęcia, ale może kogoś natchnąłem.

[xiikzodz]

Jeśli jakoś znajdziemy jedno rozwiązanie, a tu jest łatwo, bo \(\displaystyle{ 2^9=512=7\cdot 73+1}\), skąd \(\displaystyle{ 2^{99}=1}\) i \(\displaystyle{ 2^{100}=2}\), to pozostałe otrzymamy mnożąc to znalezione przez pierwiastki równania:

\(\displaystyle{ x^{100} = 1}\).

Z uwagi na mtF (bo nwd(100,72)=4) jego rozwiązaniami są pierwiastki równania

\(\displaystyle{ x^4=1}\).

Dwoma z czterech pierwiastków tego równania są liczby \(\displaystyle{ -1,1}\). Pozostaje więc wyznaczenie pierwiastków równania

\(\displaystyle{ x^2=-1}\).

Z kolei rozwiązanie tego równania polega zasadniczo na przedstawieniu \(\displaystyle{ 73}\) w postaci sumy kwadratów liczb całkowitych co jest możliwe na mocy innego tw. Fermata.. Tu nietrudno zauważyć, że \(\displaystyle{ 73=9+64=3^3+8^2}\).

Stąd szukane pierwiastkie to:

\(\displaystyle{ \pm 3^{-1}\cdot 8=\pm 49\cdot 8=\pm 27}\).

Można więc wypisać rozwiązania:

\(\displaystyle{ 2\cdot 1=2}\)

\(\displaystyle{ 2\cdot(-1)=-2=71}\)

\(\displaystyle{ 2\cdot 27=54}\)

\(\displaystyle{ 2\cdot(-27)=-54=19}\).