Matematyka.pl

Mógłby ktoś pokazać jak się rozwiązuje takie równania:

\(\displaystyle{ x\times x = 17}\) w \(\displaystyle{ Z_{59}}\)

wyniki to 28 i 31, ale kompletnie nie wiem jak się do nich dochodzi. Pomiędzy iksami jest działanie multiplikatywne. Z góry thx za pomoc!

W systemie dziesiętnym należałoby znaleźć taką liczbę, której kwadrat podzielony przez 59 daje resztę 17 oraz liczba ta spełnia warunek \(\displaystyle{ x\in \{0,1,2,3,...,57,58\}}\)

\(\displaystyle{ x^2 \equiv 17 (mod) 59}\)
Zauważmy, że:
\(\displaystyle{ (59-x)^2 = 59^2 - 2 59 x + x^2 = 59(59+2x)+x^2 \\
59(59+2x)+x^2 \equiv 17 (mod) 59}\)

to już zawęża krąg "podejrzanych"
znajdując \(\displaystyle{ x}\) w zbiorze \(\displaystyle{ \{1,2,3,...,28,29\}}\) otrzymamy od razu drugie rozwiązanie \(\displaystyle{ 59-x}\)
jakieś pomysły co dalej trochę kłopotliwe sprawdzić ręcznie 29 liczb

Tak jak Szemek pokazał, gdy rozważamy równanie \(\displaystyle{ x^2 \equiv k \ (mod \ p)}\), gdzie p jest liczbą pierwszą, to wśród \(\displaystyle{ x \lbrace 0,1,\ldots,p-1 \rbrace}\) każda wartość k ze zbioru \(\displaystyle{ \lbrace 0,1,\ldots,p-1 \rbrace}\) jest przyjmowana dokładnie 0 lub 2 razy. Tak pokrótce: niech zachodzi \(\displaystyle{ a^2 \equiv m \ (mod \ p)}\). Szukamy takich b różnych od a, że \(\displaystyle{ b^2 \equiv m \ (mod \ p)}\), czyli: \(\displaystyle{ a^2 \equiv b^2 \ (mod \ p)}\), a to ze wzorów skróconego mnożenia: \(\displaystyle{ (a-b)(a+b) \equiv 0 \ (mod \ p)}\). Ponieważ \(\displaystyle{ a\neq b}\) oraz \(\displaystyle{ 0qslant 29}\))