forum.zadania.info

Witam,

\(x^2\equiv 1 (mod 784)\)

Może ktoś pomóc ?

\(x^2\equiv1\ (mod\ 784)\\x_1\equiv1\ (mod\ 784)\ \vee\ x\equiv-1\ (mod\ 784)\equiv783\ (mod\ (784)\)

\(785^2=786\cdot784+1\\783^2=782\cdot784+1\)

To niestety nie jest rozwiązanie, bo np liczba 97 spełnia kongruencje.
Takich liczb jest zdecydowanie więcej

\(784=2^4 \cdot 7^2\)
kongruencja \(\\) \(x^2 \equiv 1\) \(\\) \(mod\)\((\)\(\\)\(784\)\()\)\(\\) jest równoważna układowi kongruencji \(\begin{cases} x^2 \equiv 1 mod(2^4)\\ x^2 \equiv 1 mod(7^2) \end{cases}\)

Kongruencja \(\\) \(x^2 \equiv 1\) \(\\) \(mod\)\((\)\(\\)\(7^2\)\()\)
jest równoważna podzielności \(7^2 |x^2-1=(x-1)(x+1)\) stąd \(\\) \(7^2|x-1\)\(\vee 7^2|x+1\)
Stąd \(x=7^2k+1\)\(\\)\(\vee\)\(x=7^2k+48\)

Kongruencja \(\\) \(x^2 \equiv 1\) \(\\) \(mod\)\((\)\(\\)\(2^4\)\()\)
Ona ma cztery rozwiązania \(x=2^4l+1\)\(\\)\(\vee\) \(x=2^4l+7\)\(\\)\(\vee\) \(x=2^4l+9\)\(\\)\(\vee\) \(x=2^4l+15\)\(\\)

Rozwiązania wyjściowej kongruencji to
\(x=(7^2k+1) \cdot ( 2^4l+1 )\)\(\\)\(\vee\)\(x=(7^2k+1) \cdot ( 2^4l+7 )\) \(x=(7^2k+1) \cdot ( 2^4l+9 )\)\(\\)\(\vee\)\(x=(7^2k+1) \cdot ( 2^4l+15 )\)
\(x=(7^2k+48) \cdot ( 2^4l+1 )\)\(\\)\(\vee\)\(x=(7^2k+48) \cdot ( 2^4l+7 )\) \(x=(7^2k+48) \cdot ( 2^4l+9 )\)\(\\)\(\vee\)\(x=(7^2k+48) \cdot ( 2^4l+15 )\)
Zapewne można to sprytnie pozbierać.