Квадратичное сравнение [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!

Указать способ решения сравнения $x^2\equiv 1 \pmod m$, основанный на том обстоятельстве, что указанное сравнение равносильно такому: $(x-1)(x+1)\equiv 0 \pmod m$

Подскажите пожалуйста как тут действовать? Что-то сам не могу понять.

С уважением, Whitaker.

[Sonic86]

Найдите $\gcd(x-1,x+1)$.
Вспомогательный вопрос: пусть $x,y$ неизвестны и взаимно просты и $m\mid x,y$ (другими словами, $xy\equiv 0\pmod m$), $m$ дано. Каковы все решения это делимости?
Можете также начать с рассмотрения решения сравнения $x^2\equiv 1\pmod p$.

[Whitaker]

Уважаемый Sonic86
просто я не совсем понимаю то, что вы написали. А точнее связь написанного с исходной задачей.
Можете как-то пояснить

-- Ср авг 06, 2014 21:14:19 --

$\text{gcd}(x-1, x+1)$ равно 1 или 2, соответственно если $x$-нечетное или четное.

[ИСН]

Ну если произведение двух чисел делится на $m$ (у Вас именно это и происходит), что это значит?

[Whitaker]

Тогда один из них делится на какой-то делитель $d$, а другой на делитель $m/d$. Так да?

[Whitaker]

Объясните пожалуйста смысл Вашего поста? Каким образом он относится к задаче?

[Whitaker]

Пусть $m=2^{\alpha}p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Тогда число $m$ можно представить как $2^{\alpha}ab$, где $(a,b)=1$ ровно $2^k$ способами.
Пусть $\alpha=0$ тогда получается системы сравнений вида $x-1\equiv 0 \pmod a, \quad x+1\equiv 0 \pmod b$. Таких систем будет всего $2^k$. Как показать, что все их решения будут различными по модулю $ab$?

[ИСН]

Ну пусть $\alpha=0$. Пусть два решения одинаковы. В одном из них $x-1$ делится на одни простые, а $x+1$ - на все остальные. В другом (напоминаю, одинаковом с первым) то же самое, только наборы другие. В чём-то они совпадают, может быть, но в чём-то же должны и отличаться. Значит, какое-то простое $p$ входит и в $x-1$, и в $x+1$. Хорошо ли это?