Диофантово уравнение с N неизвестными

[Andrey A]

Ладно. Принцип ясен, на досуге разберусь.
Спасибо.

[Andrey A]

Врубился. $n=2$ решается не хуже, должна быть удобная форма записи - что-то вроде $n$-кратных дробей. Оно и есть алгоритм Евклида для многочленов, чудо неизъяснимое. Интересно, кто это изобрел?

[Andrey A]

Тут хочется еще порассуждать. Решая уравнение $6x_1+10x_2+15x_3=c\ (1)$ указанным способом, получаем

$x_1=\ c+5y_1-5y_2$
$x_2=\ c+0y_1-3y_2$
$x_3=-c-2y_1+4y_2$, где $y_1,y_2$ - пара свободных переменных.

Первые слагаемые многочленов от верхнего к нижнему образуют некоторое решение: $6\cdot c+10\cdot c+15\cdot -c=c$. Вторые и третьи слагаемые образуют пару непропорциональных решений уравнения $6x_1+10x_2+15x_3=0$. Запишем коэффициенты при переменных в квадратную матрицу:

$$\begin{pmatrix} 1 & 5 & -5\\ 1 & 0 & -3\\ -1 & -2 & 4 \end{pmatrix}$$

Элементы первого столбца, подставленные в уравнение $(1)$ возвращают единицу, остальных столбцов - ноль. В некотором смысле они "почти пропорциональны".
Пусть теперь дана матрица $\begin{pmatrix} k_{11} & k_{12} & k_{13}\\ k_{21} & k_{22} & k_{23}\\ k_{31} & k_{32} & k_{33} \end{pmatrix}$ , и нужно определить какому из возможных уравнений она соответствует (выражает решение). Из $\left\{\begin{matrix} k_{12}a+k_{22}b+k_{32}c=0\\ k_{13}a+k_{23}b+k_{33}c=0 \end{matrix}\right.$ , перенося различные слагаемые в правую часть, получаем $\dfrac{a}{b}=\dfrac{k_{22}k_{33}-k_{23}k_{32}}{k_{12}k_{33}-k_{13}k_{32}},\ \dfrac{a}{c}=\dfrac{k_{22}k_{33}-k_{23}k_{32}}{k_{12}k_{23}-k_{13}k_{22}}$. Обозначим $k_{22}k_{33}-k_{23}k_{32}=m_1, k_{12}k_{33}-k_{13}k_{32}=m_2,k_{12}k_{23}-k_{13}k_{22}=m_3$. Тогда $\dfrac{a}{b}=\dfrac{m_1}{m_2},\dfrac{b}{c}=\dfrac{m_2}{m_3},\dfrac{c}{a}=\dfrac{m_3}{m_1}$. Тройка $ a,b,c$ по предположению взаимно проста, отсюда $a=\pm m_1,b=\pm m_2,c=\pm m_3$, и должно выполняться $k_{11}m_1+k_{21}m_2+k_{31}m_3=\pm 1$. В противном случае (а так же в случае $\gcd (m_1,m_2,m_3)>1$) матрица не выражает никакого решения. То есть не любые три столбца "почти пропорциональны" даже в некотором смысле. Всё сказанное можно продолжить на квадратную матрицу со стороной $>3$. Иными словами, решение целочисленного уравнения первой степени с $k$ неизвестными выражается $k$ многочленами, коэффициенты которых образуют определитель $k$-того порядка $=\pm 1$, а правые миноры равны по абсолютной величине заданным аргументам (правые - значит образованные вычеркиванием первого столбца и строк от первой до $k$-той). Операция прибавления/вычитания к элементам некоторого столбца нескольких элементов другого столбца за исключением первого оставляет неизменными значения как определителя, так и правых миноров. Как следствие - существование если не приведенных (как в случае $k=2$), то хотя бы нормализованных решений с "маленькими" коэффициентами. Решение $(1)$ из начала поста можно немножко подровнять, прибавляя к третьему столбцу второй или удвоенный второй:

$$\begin{pmatrix} 1 & 5 & -5\\ 1 & 0 & -3\\ -1 & -2 & 4 \end{pmatrix}\rightarrow \begin{pmatrix} 1 & 5 & 0\\ 1 & 0 & -3\\ -1 & -2 & 2 \end{pmatrix}\rightarrow \begin{pmatrix} 1 & 5 & 5\\ 1 & 0 & -3\\ -1 & -2 & 0 \end{pmatrix}$$

Изменим несколько терминологию и будем говорить о решении уравнения

$$a_1x_1-a_2x_2+a_3x_3-...\pm a_kx_k=\pm 1\ (2),$$

где попарно отличные натуральные аргументы $a_1,a_2,...,a_k$ не имеют общего делителя $>1$ и расположены от большего к меньшему в порядке убывания: $a_1>a_2>...>a_k$. Вопрос: нельзя ли получить матрицу решения $(2)$ посредством нескольких операций с определителями $k$-того порядка из некой сингулярной матрицы подобно последовательности подходящих дробей, которая и есть в сущности последовательность единичных определителей второго порядка? Заключение домашней лаборатории дает положительный ответ на этот вопрос при соблюдении некоторых правил.

1) Последовательность остатков $r_n$.
$r_{1-k}=a_1,r_{2-k}=a_2,...,r_{-1}=a_{k-1},r_0=a_k.$ $r_1$ есть остаток от деления $a_1\mod a_2,r_2=a_2\mod a_3,...,r_n=r_{n-k}\mod r_{n-k+1}.$ Вычисления заканчиваются при достижении подпоследовательности из $k-1$ нулей. При достижении подпоследовательности из меньшего количества нулей с последующим ненулевым членом нулевые остатки меняются на соответствующие делители (возврат на $k-1$ шаг), и вычисления продолжаются.

2) Последовательность неполных частных $u_n$ (аналог непрерывной дроби). $u_1=\dfrac{a_1-r_1}{a_2},u_2=\dfrac{a_2-r_2}{a_3},...,u_n=\dfrac{r_{n-k}-r_n}{r_{n-k+1}}.$

3) Последовательность столбцов единичных определителей $k$-того порядка (аналог последовательности подходящих дробей). $k$ начальных членов суть столбцы сингулярной матрицы

$$\begin{pmatrix} -1 & 0 & \ 0 & \cdots & 0 \\ 0 & 1 & \ 0 & \cdots & 0 \\ 0 & 0 & \ \ & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ 0 & \cdots & (-1)^k \end{pmatrix}$$

Начиная с $n=1$, члены каждой строки вычисляются по формуле $q_n=-u_nq_{n-k+1}+q_{n-k}$. $k$ последних столбцов образуют матрицу решения уравнения $(2)$.




При вычислении последовательности $r_n$ можно брать вместо остатков абсолютно наименьшие вычеты, а при замене локальных нулевых остатков уменьшать на единицу неполные частные по абсолютной величине. При $k>2$ разница весьма ощутима. Для уравнения $140x_1-105_2+84x_3-60x_4=\pm 1$, к примеру, в первом случае получаем дробь из $25$-и знаков и большие числа в решении, во втором - всего из четырнадцати: $u_n=1,1,1,2,2,1,-2,1,2,-1,-1,3,-1,1$ и вполне симпатичную последовательность

$$\begin{matrix} -1 & 0 & 0 & 0 & -1 & 0 & 0 & 2 & -1\\ 0 & 1 & 0 & 0 & -1 & 1 & 0 & 2 & -3\\ 0 & 0 & -1 & 0 & 0 & 1 & -1 & 0 & -2\\ 0 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 \end{matrix}\ \ \ \ \begin{matrix} 0 & 4 & 3 & -1 & 4 & 7 & 6 & 3 & -3\\ 1 & 4 & 5 & -5 & 5 & 9 & 20 & 0 & -4\\ 2 & -1 & 2 & -6 & 1 & 1 & 20 & -5 & 0\\ 1 & 1 & 1 & -2 & 2 & 2 & 7 & 0 & 0 \end{matrix}$$

Подровняем:

$$\begin{pmatrix} 7 & 6 & 3 & -3\\ 9 & 20 & 0 & -4\\ 1 & 20 & -5 & 0\\ 2 & 7 & 0 & 0 \end{pmatrix}\rightarrow \begin{pmatrix} 7 & -9 & 3 & -3\\ 9 & 0 & 0 & -4\\ 1 & 20 & -5 & 0\\ 2 & 7 & 0 & 0 \end{pmatrix}\rightarrow \begin{pmatrix} 7 & 3 & 3 & -3\\ 9 & 0 & 0 & -4\\ 1 & 0 & -5 & 0\\ 2 & 7 & 0 & 0 \end{pmatrix} $$

Каждому единичному остатку в процессе вычисления $r_n$ соответствует вариант первого столбца матрицы решения. В данном примере это пятый и шестой столбцы от конца. Кажется всё.

ex-math, спасибо еще раз за поправку, тема в самом деле интересная. Наверное должен быть более экономный подход, где сама дробь записывается не в строку, а в таблицу из $k$ строк, но меня интересует главным образом возможность перехода к иррациональностям, а там нужны инструменты попроще. $x\sqrt{a}+y\sqrt{b}+z\sqrt{c}\approx 0$ например. Каким это может сопутствовать уравнениям?

Такие $ k$-этажные дроби