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

[Dogya]

Имеем уравнение $x^2 - 1 \equiv 0 \mod 120$ оно не очень сложно решается в лоб

т.е. говорим что $120 = 2^3\cdot3\cdot5$ и решаем уже 3 уравнения полегче

и тут возникает 1 вопрос: как найти все корни уравнения $x^2-1\equiv 0 \mod 8$ не перебором(хотя перебором т легко)

Ну вот решили мы 3 уравнения получи $\pm1 \mod 3$, $\pm1 \mod 5$, $\pm1 , \pm3 \mod 8$

теперь нам надо применить К.Т.О.(китайская теорема) взяв по одному корню из каждого уравнения выше то есть 16 раз решить систему

И тут 2 вопрос как не решать это 16 раз , есть одна идея тк первый и последний корень в сумме дают 120 то можно решить всего 8 раз но тоже много

Ну ок получил я 16 корней и тут есть доп.задача дословно "Напишите соответствующее разложение на множители для $x^2-1$" и тут я вообще без понятия что делать

[nnosipov]

Dogya в сообщении #1542014 писал(а):

1 вопрос: как найти все корни уравнения $x^2-1\equiv 0 \mod 8$ не перебором

С помощью так называемого метода подъема Гензеля (гензелев подъем): каждое решения сравнения $f(x) \equiv 0 \pmod{p}$ нужно попытаться "поднять" (достроить) до решения сравнения $f(x) \equiv 0 \pmod{p^n}$.

Dogya в сообщении #1542014 писал(а):

И тут 2 вопрос как не решать это 16 раз

Никак, ведь искомых решений будет ровно 16 штук, и их все нужно выписать.

Dogya в сообщении #1542014 писал(а):

есть доп.задача дословно "Напишите соответствующее разложение на множители для $x^2-1$"

Таких разложений будет много, ибо это разложения над кольцом $\mathbb{Z}_{120}$, а оно содержит делители нуля. Подумайте, как подобрать коэффициенты $a$, $b$, чтобы было верно $x^2-1 \equiv (x-a)(x-b) \pmod{120}$.

[Padawan]

Dogya в сообщении #1542014 писал(а):

Ну вот решили мы 3 уравнения получи $\pm1 \mod 3$, $\pm1 \mod 5$, $\pm1 , \pm3 \mod 8$

теперь нам надо применить К.Т.О.(китайская теорема) взяв по одному корню из каждого уравнения выше то есть 16 раз решить систему

А вы посмотрите док-во китайской теоремы об остатках (одно из доказательств), там решение записывается в общем виде, участвуют только модули ($3, 5, 8$ в вашем случае), а правые части -- произвольные.

-- Ср дек 08, 2021 12:34:17 --

Dogya в сообщении #1542014 писал(а):

и тут возникает 1 вопрос: как найти все корни уравнения $x^2-1\equiv 0 \mod 8$ не перебором(хотя перебором т легко)

Виноградов И.М. Основы теории чисел, глава 4, параграф 5, b