2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Решение уравнения в Z/nZ
Сообщение13.12.2014, 22:51 
provincialka в сообщении #945803 писал(а):
Вы знаете китайскую теорему об остатках?

(Оффтоп)

только в теории проходил, никогда не применял. Понял, сейчас подумаю, как здесь ее применить.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение13.12.2014, 22:56 
Аватара пользователя
Так. Я окончательно запуталась в потоке буковок. Простой прогон на Excel дает 4 решения. Это факт. Осталось, чтобы ZumbiAzul указал их все.

-- 13.12.2014, 23:06 --

ZumbiAzul, честно говоря, чтение рассуждений, раздробленных по кускам, не способствует пониманию. Похоже, я где-то потеряла нить. Вы уж запишите кратко всё рассуждение, хотя бы после того, как разложили левую часть на множители.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 00:51 
Вопрос немного вбок: а почему у уравнения второй степени в одном кольце 4 корня?

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 01:00 
Аватара пользователя
А сколько должно быть? Например, уравнение $x^2=\overline1$ в кольце остатков по основанию 60 имеет 8 решений: $(\overline1; \overline{11}; \overline{19}; \overline{29}; \overline{31}; \overline{41}; \overline{49}; \overline{59})$

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 01:04 
А, понял. Это только в кольце без делителей нуля может быть корней не больше, чем степень уравнения, верно?

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 01:12 
Аватара пользователя
Ну да. Тут вся тема стоит на том, что 221 раскладывается на множители, а потом это все надо обратно в кучку собрать.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 10:58 

(Оффтоп)

greg2 в сообщении #945889 писал(а):
Это только в кольце без делителей нуля может быть корней не больше, чем степень уравнения, верно?
provincialka в сообщении #945892 писал(а):
Ну да.
:shock: а доказательство можете написать, ради интереса?
Понятно, что в поле уравнение имеет число корней не больше, чем его степень, а вот почему именно в кольце без делителей нуля число корней может быть больше?
Пусть оно еще коммутативно для того, чтобы можно было говорить об уравнениях в обычном смысле.

Пусть $a_nx^n+...+a_1x+a_0=0$. Пусть оно имеет корни $\alpha_j$ кратности $m_j, j=\overline{1,r}$. Перемножим $\prod (x-\alpha_j)$, получим $b_mx^m+...+b_1x+b_0=0, m>n$. Применяя алгоритм Евклида... ага, которого нет... И не факт, что $a_0=b_0$.
В общем, мне не очевидно :-(

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 12:23 
Аватара пользователя
Sonic86, я не вдумывалась в "без делителей". Наверное, надо подумать, но мне неохота.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 12:47 
Аватара пользователя
Дык $b_m=1$ и деление на многочлен со старшим коэффициентом 1 есть. А лучше Безу применить - она-то есть.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 13:33 

(Оффтоп)

bot в сообщении #946028 писал(а):
Дык $b_m=1$
А, ну да.
bot в сообщении #946028 писал(а):
и деление на многочлен со старшим коэффициентом 1 есть.
нету: $m>n$. Или я чего-то не вижу.
bot в сообщении #946028 писал(а):
А лучше Безу применить - она-то есть.
Нет: Безу есть и в кольцах с делителями нуля. Например, $x^2\equiv 1\pmod 8$ имеет 4 корня, как тут применить Безу? Либо я не так вижу Вашу аргументацию.
Или Вы имеете ввиду, что если $P(x)=(x-a)Q(x)$ и в кольце нет делителей нуля и $P(x)=0$, то либо $x-a=0$, либо $Q(x)=0$?
А, ну да, так работает, спасибо. :-)

provincialka в сообщении #946021 писал(а):
Sonic86, я не вдумывалась в "без делителей".
Ну я понял: Вы отвечали на другой вопрос. Просто я не уверен, что вопрошающий это понял. Пытаюсь внести ясность.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 13:38 
Sonic86 в сообщении #946048 писал(а):

(Оффтоп)

bot в сообщении #946028 писал(а):
Дык $b_m=1$
А, ну да.
bot в сообщении #946028 писал(а):
и деление на многочлен со старшим коэффициентом 1 есть.
нету: $m>n$. Или я чего-то не вижу.
bot в сообщении #946028 писал(а):
А лучше Безу применить - она-то есть.
Нет: Безу есть и в кольцах с делителями нуля. Например, $x^2\equiv 1\pmod 8$ имеет 4 корня. Либо я не так вижу Вашу аргументацию.


Не помню точно, но вроде бы если нет делителей нуля, то не выполняются некоторые из условий "наличие наибольшего общего делителя", "наименьшего общего кратного" и т.д., что ведет за собой возможность различного расклада элементов кольца(в данном случае кольца многочленов) на неразложимые множители. С этого и имеем наличие корней больше, чем степень

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 13:42 

(Оффтоп)

greg2 в сообщении #946052 писал(а):
если нет делителей нуля, то не выполняются некоторые из условий "наличие наибольшего общего делителя", "наименьшего общего кратного" и т.д.
Это по контрапозиции получаем, что Вы утверждаете, что если всегда есть НОД, НОК, то есть делители нуля :shock:
Может переформулируете?

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 14:04 
provincialka в сообщении #945810 писал(а):
ZumbiAzul, честно говоря, чтение рассуждений, раздробленных по кускам, не способствует пониманию. Похоже, я где-то потеряла нить. Вы уж запишите кратко всё рассуждение, хотя бы после того, как разложили левую часть на множители.

Итак, вот, что есть на данный момент. Надо было решить следующее уравнение в кольце $\mathbb{Z}/221\mathbb{Z}$:$$x^2+\overline{10}x+\overline{182}=\overline{0}$$ $$x^2+\overline{10}x+\overline{25}+\overline{157}=\overline{0}$$ $$(x+\overline{5})^2-\overline{64}=\overline{0}$$ $$(x+\overline{5}-\overline{8})(x+\overline{5}+\overline{8})=\overline{0}$$ $$(x-\overline{3})(x+\overline{13})=\overline{0}$$ Т.о., должно быть целым следующее выражение: $$\frac{(x-3)(x+13)}{13\cdot17}$$ Т.е. возможны 4 варианта:

1 вариант: $$x\equiv3\pmod{13} \text{   и   } x\equiv-13\pmod{17}$$$$x\equiv3\pmod{13} \text{   и   } x\equiv4\pmod{17}$$
2 вариант: $$x\equiv3\pmod{17} \text{   и   } x\equiv-13\pmod{13}$$$$x\equiv3\pmod{17} \text{   и   } x\equiv0\pmod{13}$$
3 вариант: $$x\equiv3\pmod{13\cdot17}$$
4 вариант: $$x\equiv-13\pmod{13\cdot17}$$$$x\equiv208\pmod{13\cdot17}$$

Сейчас попробую написать первые два варианта по модулю 221.

Как я понял, надо применить китайскую теорему об остатках.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 14:05 
Аватара пользователя
Sonic86 в сообщении #946048 писал(а):
Нет: Безу есть и в кольцах с делителями нуля.

Есть, но там она нам без надобности. Нам она нужна в кольцах без делителей нуля. Если $a$ корень, то раскладываем $p(x)=(x-a)q(x)$. Число корней у $q(x)$ стало на 1 меньше (здесь и нужно отсутствие делителей нуля) и степень тоже.

 
 
 
 Re: Решение уравнения в Z/nZ
Сообщение14.12.2014, 14:13 
Аватара пользователя
ZumbiAzul в сообщении #946076 писал(а):
Как я понял, надо применить китайскую теорему об остатках.
Да бог с ней! Просто подбором решите.

 
 
 [ Сообщений: 49 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group