2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 корни уравнения в кольце вычетов
Сообщение08.12.2021, 04:43 


30/11/21
2
Имеем уравнение $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$" и тут я вообще без понятия что делать

 Профиль  
                  
 
 Re: корни уравнения в кольце вычетов
Сообщение08.12.2021, 05:42 
Заслуженный участник


20/12/10
9179
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}$.

 Профиль  
                  
 
 Re: корни уравнения в кольце вычетов
Сообщение08.12.2021, 10:30 
Заслуженный участник


13/12/05
4660
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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Skipper


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group