kongruencja - metoda rozwiązania

[JakubCh]

\(\displaystyle{ x^2 = 13 \pmod{113}}\) jak robić tego typu kongruencje?

[PierwszyBrowarMacka]

\(\displaystyle{ x\equiv 37 (\text{ \bf mod } 113 ) \vee x\equiv 76 (\text{ \bf mod } 113 )}\)

[JakubCh]

jak do tego dojść?:)

[PierwszyBrowarMacka]

Nie znam innej metody jak kolejne podstawianie za \(\displaystyle{ x}\) liczb \(\displaystyle{ 0,1,2,...,56 .}\)

[JakimPL]

\(\displaystyle{ 113}\) jest liczbą pierwszą, więc nie trzeba martwić się o żadne dodatkowe założenia. Jeżeli znamy \(\displaystyle{ x_1}\), który spełnia równanie, \(\displaystyle{ x_2 = 113-x_1}\).

Najpierw warto było upewnić się, że rozwiązanie istnieje, korzystając z prawa wzajemności reszt kwadratowych (tu: istnieją, co widać).

Dla równania \(\displaystyle{ x^2\equiv a \pmod p}\), \(\displaystyle{ 2<p\in\mathbb{P}}\), gdzie \(\displaystyle{ a}\) jest resztą kwadratową modulo \(\displaystyle{ p}\) i \(\displaystyle{ a\equiv 3 \pmod 4}\) możemy stwierdzić, że \(\displaystyle{ a^{\frac{p+1}{4}}}\) spełnia dane równanie (nietrywialne).

Niestety, u nas nie możemy tak zrobić, pozostaje albo podstawianie, albo jakiś algorytm, na przykład .

EDIT: literówka.

[bakala12]

Polecam poczytać.