Решение сравнения первой степени

[das_das_das]

Здравствуйте, уважаемые посетители форума.
Возник общий вопрос по решениям сравнений 1-ой степени, а конкретно, начал решать уравнение $35x \equiv 20 \pmod{95}$. Итак, пошагово:

1. Нашел НОД(35, 20) $=$ 5 $\Rightarrow$ 5 решений.
2. Разделил почленно на 5, получилось сравнение $7x \equiv 4 \pmod{19}$
3. Нашел континуанту, равную 20 $\Rightarrow$ $x \equiv 20 \pmod{19} $

Что делать дальше?

[ИСН]

Что такое континуанта и какое отношение она имеет к сравнению в предыдущей строке?

[Cash]

Еще и вот это кажется подозрительным

Цитата:

НОД(35, 20) $=$ 5 $\Rightarrow$ 5 решений

С чего бы так?

-- Пт дек 21, 2012 17:35:34 --

das_das_das,
вы этот найденный $x$ пробовали подставить в уравнение?

[das_das_das]

Cash
, ну так по теореме получается 5 решений. Подставлять пробовал, получается один корень. Как остальные найти?
ИСН,
это $u$ в выражении $ux+vy=d$

[xmaister]

das_das_das в сообщении #661456 писал(а):

Как остальные найти?

Если $x$- решение сравнения, то $x+i\frac{95}{\gcd(35,95)}, i=1,2,3,4$- тоже.

[ИСН]

das_das_das в сообщении #661456 писал(а):

это $u$ в выражении $ux+vy=d$

Было уравнение с одной буквой (x). Хотел решить. Полез на антресоли. Оттуда вывалилось ещё четыре непонятных буквы (u, v, d, y), лопата без ручки и чучело бульдога. Почесал в затылке. Решил дальше не лезть.

[das_das_das]

xmaister, спасибо.
ИСН, я имел ввиду линейное представление НОД(4, 19), равное 1.

[Cash]

Т.е. уравнение $35x \equiv 20 \pmod{36}$ тоже имеет 5 решений? Что за теорема такая?
Вы подставили $20$ в уравнение $7x \equiv 4 \pmod{19}$ и у вас все сошлось?

[Sonic86]

das_das_das в сообщении #661404 писал(а):

Итак, пошагово:

1. Нашел НОД(35, 20) $=$ 5 $\Rightarrow$ 5 решений.

Cash в сообщении #661421 писал(а):

С чего бы так?

das_das_das, я Вам советую насчет пяти решений писать полную формулировку, чтобы поняли как окружающие, так и Вы сами. На самом деле, если сравнение $ax\equiv b\pmod m$ разрешимо, то оно имеет бесконечное множество решений для $x\in\mathbb{Z}$. Потому для меньшей тривиальности говорят о решении в кольце вычетов $\mathbb{Z}_m$. И в таком случае, если Вы переходите к сравнению по модулю $\frac{m}{d}$, а кольцо $\mathbb{Z}_m$ для значений $x$ сохраняете (а не заменяете его на кольцо $\mathbb{Z}_{\frac{m}{d}}$), то тогда Вы получаете $d$ решений в $\mathbb{Z}_m$. Но эти же $d$ решений эквивалентны одному решению в $\mathbb{Z}_{\frac{m}{d}}$. Потому, если Вы в тексте опускаете область значений $x$, текст становится непонятным. Вообще, я Вам советую перейти в $\mathbb{Z}_{\frac{m}{d}}$ и освободить свою память от ненужного пункта теоремы (тем более, в такой плохой формулировке.)

das_das_das в сообщении #661404 писал(а):

3. Нашел континуанту, равную 20 $\Rightarrow$ $x \equiv 20 \pmod{19} $

неверно. Проверьте подстановкой.


P.S.

das_das_das в сообщении #661404 писал(а):

НОД(35, 20) $=$ 5 $\Rightarrow$ 5

Формулы надо целиком оформлять ТеХом. В данном случае так:

\text{НОД}(35, 20)=5\Rightarrow 5

(Оффтоп)

ИСН в сообщении #661472 писал(а):

Было уравнение с одной буквой (x). Хотел решить. Полез на антресоли. Оттуда вывалилось ещё четыре непонятных буквы (u, v, d, y), лопата без ручки и чучело бульдога. Почесал в затылке. Решил дальше не лезть.

утащил в цитатник

[Cash]

das_das_das, возможно я излишне придираюсь, но если убрать частности, у вас записано следующее:

$ax\equiv b\pmod m$
$\gcd(a,b) = d \Rightarrow$ сравнение имеет $d$ решений (я так понимаю, что в $\mathbb{Z}_m$)
Это попросту неверно.

[xmaister]

Если рассматривать связь решений сранения и уравнения над $\mathbb{Z}/n\mathbb{Z}$, то на мой взгляд лучше рассмотреть $S$- множество всех решений вашего сравнения $f(x)\equiv 0\pmod{n}$, профаткоризовать его по очевидному отношению эквивалентности и состряпать биекцию на множество решений $\overline{f}(x)=0$, где $f\mapsto\overline{f}$- гомоморфизм колец многочленов, индуцированный факторотображением $\theta: \mathbb{Z}\to \mathbb{Z}/n\mathbb{Z}$.

[VAL]

xmaister в сообщении #661606 писал(а):

Если рассматривать связь решений сранения и уравнения над $\mathbb{Z}/n\mathbb{Z}$, то на мой взгляд лучше рассмотреть $S$- множество всех решений вашего сравнения $f(x)\equiv 0\pmod{n}$, профаткоризовать его по очевидному отношению эквивалентности и состряпать биекцию на множество решений $\overline{f}(x)=0$, где $f\mapsto\overline{f}$- гомоморфизм колец многочленов, индуцированный факторотображением $\theta: \mathbb{Z}\to \mathbb{Z}/n\mathbb{Z}$.

xmaister, не пугайте ТС. А то он прочтет Ваше сообщение и подумает, что у него очень сложное задание.