Решить уравнение в целых числах

[fiztech]

$19x+17y=1$

Может кто нибудь показать как его решить с помощью алгоритма Евклида ? Наверно можно же найти два числа (каким нибудь способом) таких, чтобы разность их произведения на 19 и 17 равна была единице?

[mihailm]

Находите НОД 19 и 17 с помощью алгоритма Евклида

[bot]

Искомое представление даст также разложение $\dfrac{19}{17}$ в цепную дробь.
Обратите там внимание на подходящие дроби и соотношение $p_nq_{n-1}-q_np_{n-1}=(-1)^{n-1}$

[Батороев]

fiztech в сообщении #629261 писал(а):

Наверно можно же найти два числа (каким нибудь способом) таких, чтобы разность их произведения на 19 и 17 равна была единице?

Могу предложить свой "доморощенный" способ (не знаю, дает ли он все решения), который заключается в том, чтобы при рассмотрении выражения $ax-by=1$ оттолкнуться от выражения $a-b=m$.
Далее последнее выражение немного изменяю $a\cdot\dfrac {1}{m}-b\cdot\dfrac {1}{m}=a\cdot\dfrac {1}{m}+abn\cdot\dfrac {1}{m} -b\cdot\dfrac {1}{m}-abn\cdot\dfrac {1}{m}=1$ и получаю $x=(1+bn)\cdot\dfrac {1}{m}$; $y=(1+an)\cdot\dfrac {1}{m}$
($m,n$ - целые числа)

[bot]

Дык, достаточно найти одно решение - в этом и есть чисто техническая сложность, а общее тогда сразу получается добавлением очевидного решения однородного.
Про цепные дроби уже сказал, а вот Евклид (расширенный):
$\begin{pmatrix}1&0&|&19\\ 0&1&|&17\\ 1&-1&|&2\\ -8&9&|&1\end{pmatrix}$
Слева у нас коэффициенты при 19 и 17, справа результат этой комбинации, последний столбик - это остатки в обычном алгоритме Евклида. Итого $-8\cdot 19+9\cdot 17=1$. Общее решение:
$\begin{pmatrix}x\\ y\end{pmatrix}=\begin{pmatrix}-8\\ 9\end{pmatrix}+t\cdot \begin{pmatrix}17\\ -19\end{pmatrix}\, \, t\in \mathbb Z $

[vorvalm]

Надо решить два сравнения:

$19x\equiv 1(\mod17)$
$17y\equiv 1(\mod19)$

с учетом знака (-).

[Батороев]

(Оффтоп)

Попробовал своим "доморощенным" способом рассмотреть ВТФ и получил (если нигде не наврал, что вполне возможно в виду трудного дня и позднего времени):

$\left( \dfrac{c}{a}\right)\cdot \left(\dfrac{c}{a}\right)^{n-1} - \left(\dfrac{b}{a}\right)\cdot \left(\dfrac{b}{a}\right)^{n-1}=\left(\dfrac{c}{a}\right)x -\left(\dfrac{c}{a}\right)y= 1$

Используем равенство: $\dfrac{c}{a}-\dfrac{b}{a}=\dfrac {c-b}{a}$

Тогда:

$x=\left(\dfrac{c}{a}\right)^{n-1}=\dfrac{a+bk}{c-b}$

$y=\left(\dfrac{b}{a}\right)^{n-1}=\dfrac{a+ck}{c-b}$,

где $k$ - эквивалент $n$ из моего предыдущего сообщения.

или

$ c^{n-1}(c-b)=(a+bk)a^{n-1}$

$b^{n-1}(c-b)=(a+ck)a^{n-1}$

Откуда в виду взаимной простоты $(a,b,c)=1$ получается то, что $a^{n-1}|(c-b)$, что невозможно.

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

-- 11 окт 2012 23:44 --

(Оффтоп)

Что-то у меня, похоже, не то, т.к. для ВТФ второй степени не все получается.

[bot]

vorvalm в сообщении #629584 писал(а):

Надо решить два сравнения:

Достаточно одного, но это не проще ни алгоритма Евклида ни цепных дробей, что по сути одно и то же.

[vorvalm]

У предложенного уравнения два решения.

[Shadow]

vorvalm в сообщении #629659 писал(а):

У предложенного уравнения два решения.

Даже одно
$x=9-17k \text{ и } y=19k-10$

[vorvalm]

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

[bot]

Разъясните, что имелось в виду. Общее решение выше указано - это вектор. Что такое абсолютная величина вектора - его длина? В какой метрике? Если в евклидовой, то решение минимальной длины одно - это $x=-8, \, y=9$

[vorvalm]

Приведенное общее решение не вектор, но комплекс классов.
По Бухштабу решением уравнения являются
$x_0=9,\;y_0=-10$, но
$x_1=-8,\;y_1=9.$

[TOTAL]

vorvalm в сообщении #629814 писал(а):

Приведенное общее решение не вектор, но комплекс классов.
По Бухштабу решением уравнения являются
$x_0=9,\;y_0=-10$, но
$x_1=-8,\;y_1=9.$

Называйте любыми словами, но решением является следующее и только оно:

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

$\begin{pmatrix}x\\ y\end{pmatrix}=\begin{pmatrix}-8\\ 9\end{pmatrix}+t\cdot \begin{pmatrix}17\\ -19\end{pmatrix}\, \, t\in \mathbb Z $