Решение уравнения в Z/nZ

[ZumbiAzul]

provincialka в сообщении #945803 писал(а):

Вы знаете китайскую теорему об остатках?

(Оффтоп)

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

[provincialka]

Так. Я окончательно запуталась в потоке буковок. Простой прогон на Excel дает 4 решения. Это факт. Осталось, чтобы ZumbiAzul указал их все.

-- 13.12.2014, 23:06 --

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

[greg2]

Вопрос немного вбок: а почему у уравнения второй степени в одном кольце 4 корня?

[provincialka]

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

[greg2]

А, понял. Это только в кольце без делителей нуля может быть корней не больше, чем степень уравнения, верно?

[provincialka]

Ну да. Тут вся тема стоит на том, что 221 раскладывается на множители, а потом это все надо обратно в кучку собрать.

[Sonic86]

(Оффтоп)

greg2 в сообщении #945889 писал(а):

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

provincialka в сообщении #945892 писал(а):

Ну да.

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

Пусть $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$.
В общем, мне не очевидно

[provincialka]

Sonic86, я не вдумывалась в "без делителей". Наверное, надо подумать, но мне неохота.

[bot]

Дык $b_m=1$ и деление на многочлен со старшим коэффициентом 1 есть. А лучше Безу применить - она-то есть.

[Sonic86]

(Оффтоп)

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, я не вдумывалась в "без делителей".

Ну я понял: Вы отвечали на другой вопрос. Просто я не уверен, что вопрошающий это понял. Пытаюсь внести ясность.

[greg2]

Sonic86 в сообщении #946048 писал(а):

(Оффтоп)

bot в сообщении #946028 писал(а):

Дык $b_m=1$

А, ну да.

bot в сообщении #946028 писал(а):

и деление на многочлен со старшим коэффициентом 1 есть.

нету: $m>n$. Или я чего-то не вижу.

bot в сообщении #946028 писал(а):

А лучше Безу применить - она-то есть.

Нет: Безу есть и в кольцах с делителями нуля. Например, $x^2\equiv 1\pmod 8$ имеет 4 корня. Либо я не так вижу Вашу аргументацию.

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

[Sonic86]

(Оффтоп)

greg2 в сообщении #946052 писал(а):

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

Это по контрапозиции получаем, что Вы утверждаете, что если всегда есть НОД, НОК, то есть делители нуля
Может переформулируете?

[ZumbiAzul]

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.

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

[bot]

Sonic86 в сообщении #946048 писал(а):

Нет: Безу есть и в кольцах с делителями нуля.

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

[provincialka]

ZumbiAzul в сообщении #946076 писал(а):

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

Да бог с ней! Просто подбором решите.