Решение уравнения в кольце вычетов

[Middle]

Здравствуйте, нужно решить уравнение $x^2=1$ в кольце вычетов по модулю 360

Понятно, что можно положить $x=100k +10n+r$ , найти $r$ , а дальше разбирать случаи для $k$ и $l$. Я, например, нашел, что

$x=91$

$x=181$

Но есть ли более конструктивный способ решения подобных уравнений, или всегда нужно готовиться к изнурительному перебору?

[Null]

Разложите 360 на простые множители.

[nnosipov]

Вы не решили это уравнение. Вообще, задача абсолютно стандартная, а Вы делаете что-то странное.

[Middle]

Null в сообщении #1549777 писал(а):

Разложите 360 на простые множители.

$360=2^3 \cdot 3^2 \cdot 5$

$x^2=1\Leftrightarrow (x-1)(x+1) \colon 360 $

$x=100k+10m+l$

Очевидно, либо $l=1$, либо $l=9$

Пусть выполнен первый вариант, тогда

$(10k+m)(50k+5m+1) \colon 18$

А дальше разбирать отдельно для каждого $k$ и $m$
Я так и делал, если вы об этом.

[Aritaborian]

Middle, но вы не нашли все корни.

[Null]

Middle в сообщении #1549782 писал(а):

$x^2=1\Leftrightarrow (x-1)(x+1) \colon 360 $

Ну решите для начала
$x^2-1\vdots 2$

$x^2-1\vdots 5$

$x^2-1\vdots 10$

$x^2-1\vdots 8$

$x^2-1\vdots 40$

$x^2-1\vdots 72$

[Slav-27]

Middle в сообщении #1549775 писал(а):

есть ли более конструктивный способ решения подобных уравнений

Китайская теорема об остатках позволяет свести задачу к решению уравнений по модулю степень простого числа. В данном случае она говорит, что $\mathbb Z/360\simeq \mathbb Z/8\times \mathbb Z/9\times \mathbb Z/5$, поэтому для нахождения квадратных корней из $1$ по модулю $360$ достаточно найти $\sqrt 1\mod 8$, $\mod 9$ и $\mod 5$.

Если простое $p$ нечётно либо $p^d=2$ или $4$, то группа обратимых вычетов $(\mathbb Z/p^d)^\times$ циклична, значит, $\sqrt 1$ -- это только $\pm 1$. Если $d\geqslant 3$, то $(\mathbb Z/2^d)^\times\approx\mathbb Z/2\times\mathbb Z/2^{d-2}$ и порождена, например, $-1$ и $3$, поэтому $\sqrt 1$ -- это только $\pm 1$ и $\pm 3^{2^{d-3}}$.