Matematyka.pl

Niech \(\displaystyle{ m}\) i \(\displaystyle{ a}\) będą względnie pierwsze. Pokazać, że równanie
\(\displaystyle{ x^n=a \mod m}\)
ma rozwiązanie wtedy i tylko wtedy gdy
\(\displaystyle{ a^{\phi (m)/d}=1 \mod m}\)
gdzie \(\displaystyle{ d=NWD(n,\phi(m))}\)

Jak to zrobić? Może mi ktoś pomóc?

Powiedzmy, że istnieje takie \(\displaystyle{ x}\), że
\(\displaystyle{ x^n\equiv a\pmod{m}}\). Podnosimy tę kongruencję stronami do potęgi \(\displaystyle{ \frac{\phi(m)}{d}}\) i mamy
\(\displaystyle{ \left(x^{\phi(m)}\right)^{\frac{n}{d}}\equiv a^{\frac{\phi(m)}{d}}\pmod{m} \ (*)}\).
Musi być oczywiście \(\displaystyle{ (x,m)=1}\), bo łatwo udowodnić, że \(\displaystyle{ (x,m)|a}\), no i naturalnie \(\displaystyle{ (x,m)|m}\), a z założenia \(\displaystyle{ (a,m)=1}\).
Wobec tego z tw. Eulera mamy \(\displaystyle{ x^{\phi(m)}\equiv 1\pmod{m}}\) i lewa strona \(\displaystyle{ (*)}\) przystaje do \(\displaystyle{ 1\pmod{m}}\), więc prawa także musi.

W drugą stronę: powiedzmy, że \(\displaystyle{ (a,m)=1}\) i \(\displaystyle{ n\in \NN^{+}}\) jest takie, że
\(\displaystyle{ a^{\frac{\phi(m)}{d}}\equiv 1\pmod{m}}\), gdzie \(\displaystyle{ d=(n, \phi(m))}\).
Mamy \(\displaystyle{ \left(n, \frac{\phi(m)}{d}\right)=1}\), zatem z algorytmu Euklidesa wynika istnienie takich \(\displaystyle{ s,t\in \ZZ}\), że
\(\displaystyle{ ns+t\frac{\phi(m)}{d}=1}\). Oczywiście nie może być jednocześnie \(\displaystyle{ s<0, \ t<0}\).
Jeśli \(\displaystyle{ t< 0}\), to zapisujemy
\(\displaystyle{ ns-1=-t\frac{\phi(m)}{d}}\) i mamy:
\(\displaystyle{ a^{ns-1}\equiv a^{-t\frac{\phi(m)}{d}}\pmod{m}\\a^{ns-1}\equiv 1\pmod{m}\\a^{ns}\equiv a\pmod{m}}\)
czyli wystarczy wziąć
\(\displaystyle{ x:=a^s}\) (mogliśmy pomnożyć kongruencję stronami przez \(\displaystyle{ a}\), bo z założenia jest \(\displaystyle{ (a,m)=1}\)).
Jeśli \(\displaystyle{ t\ge 0}\), to robimy taką sztuczkę, żeby znaleźć inne \(\displaystyle{ t}\), ujemne:
skoro
\(\displaystyle{ ns+t\frac{\phi(m)}{d}=1}\), to dla dowolnej liczby całkowitej \(\displaystyle{ k}\) zajdzie
\(\displaystyle{ n\left(s+k\frac{\phi(m)}{d}\right)+\frac{\phi(m)}{d}\cdot\left(t-kn\right)=1}\)
i dobieramy takie \(\displaystyle{ k\in \ZZ}\), by \(\displaystyle{ t-kn<0}\), a potem bierzemy \(\displaystyle{ t'=t-kn}\) i postępujemy jak poprzednio
(wówczas można wziąć \(\displaystyle{ x:=a^{s+k\frac{\phi(m)}{d}}}\) i wszystko gro i bucy).

Implikacja w lewo jest nieprawdziwa, na przykład równanie

\(\displaystyle{ x^2 \equiv 3 \pmod{8}}\)

nie ma rozwiązań mimo że \(\displaystyle{ 3^2 \equiv 1 \pmod{8}}\).

Do jasnej cholery, jak zwykle coś źle, a tak się starałem.
Oczywiście zły jest fragment \(\displaystyle{ \left(n, \frac{\phi(m)}{d}\right)=1}\), tak wcale nie musi być, dopiero \(\displaystyle{ \left(\frac{n}{d}, \frac{\phi(m)}{d}\right)=1}\).
A ja sobie myślałem „no przecież dzielimy przez \(\displaystyle{ \NWD}\) i powinno być w porządku", ale zapomniałem, że dzielimy tylko jedną liczbę.
Chrzanię matmę i swoje życie.

Implikacja w drugą stronę jest prawdziwa, o ile istnieje pierwiastek pierwotny modulo \(\displaystyle{ m}\).