On One Way to Solve Linear Equations Over a Euclidean Ring

Urusbi M. Pachev; Пачев Урусби Мухамедович; Azamat Kh. Kodzokov; Кодзоков Азамат Хасанович; Alena G. Ezaova; Езаова Алена Георгиевна; Al’bina A. Tokbaeva; Токбаева Альбина Аниуаровна; Zera H. Guchaeva; Гучаева Зера Хамидбиевна

doi:10.26117/2079-6641-2024-46-1-9-21

On One Way to Solve Linear Equations Over a Euclidean Ring

Authors: Pachev U.M.¹, Kodzokov A.K.¹, Ezaova A.G.¹, Tokbaeva A.A.¹, Guchaeva Z.H.¹
Affiliations:
1. Kabardino-Balkarian State University named after H.M. Berbekov
Issue: Vol 46, No 1 (2024)
Pages: 9-21
Section: Mathematics
URL: https://journals.rcsi.science/2079-6641/article/view/256133
DOI: https://doi.org/10.26117/2079-6641-2024-46-1-9-21
EDN: https://elibrary.ru/CZKZBA
ID: 256133

Cite item

Full Text

Abstract
Full Text
About the authors
References
Supplementary files
Statistics

Abstract

Linear equations, i.e. Equations of the first degree, as well as systems of such equations, receive much attention both in algebra and in number theory. Of greatest interest is the case of such equations with integer coefficients, and in this case they need to be solved in integers. Such equations with the specified conditions are called linear Diophantine equations. Euler also considered ways to solve linear Diophantine equations with two unknowns, and one of these methods was based on the use of the Euclid algorithm. Another method for solving such equations, based on continued fractions, was also used by Lagrange. Euler’s method turned out to be more convenient and promising than the method of continued fractions. In this paper, we consider one new method for solving linear equations over a Euclidean ring, based on comparisons over suitable moduli. The previously known matrix method for solving such equations with an increasing number of unknowns is quite cumbersome due to the fact that it is associated with finding the inverses of unimodular integer matrices. Essential in our method of solving linear equations over a Euclidean ring is the use of the Euclidean algorithm and the linear GCD representation of elements in the Euclidean ring. The theorem proved in the work is applied to finding a solution to a linear equation in three unknowns over a ring of Gaussian integers, which, as is known, is a Euclidean ring. In conclusion, comments are made on possible ways of further development of the presented research.

Keywords

linear equation, Euclidean ring, Euclidean norm, Gaussian integers, module congruences

Full Text

Введение

Отдельное самостоятельное изложение, посвященное теории алгебраических уравнений с двумя и тремя неизвестными впервые появилось в «Арифметике» греческого математика Диофанта (3век н.э.), где рассматривались способы решения алгебраических уравнений второй и третьей степени с двумя неизвестными, причем в качестве их возможных значений использовались только рациональные числа. Изложение методов Диофанта с современной точки зрения дается в [1]. Следующий этап в развитии теории алгебраических уравнений с несколькими неизвестными связан с работами Ферма и Виета, которые уже полностью пользовались буквенной записью уравнений (16 век), причем рассматривались решения уравнений уже в целых числах (см. [2], [3]). Вопросам о числе решений линейных диофантовых уравнений в целых числах посвящены [4]-[6]. В последнее время рассматривают также системы линейных диофантовых уравнений над кольцом целых чисел [7].

Линейное уравнение над евклидовым кольцом является обобщением линейного диофантова уравнения. Для более успешного решения вопросов, связанных с линейными уравнениями, мы рассматриваем из над евклидовым кольцом, учитывая при этом что в таком кольце существует наибольший общий делитель (НОД) элементов, а значит, имеется и линейное представление НОД коэффициентов (см. [8], [9]). Элементарное введение в теорию евклидовых колец вместе с приложениями к системам линейных уравнений над такими кольцами дается в [8], где рассматриваются матричный метод решения таких систем. В случае линейных диофантовых уравнений способ их решения с помощью сравнений по подходящим модулям был изложен в [10], [11]. Этот результат использован в [12] в задаче усреднения дифференциального уравнения в частных производных при исследовании предельных циклов обобщенной полиномиальной дифференциальной системы Куклеса, связанной с решением линейного диофантова уравнения специального вида $b_{1} + 2 b_{2} + \dots + l b_{l} = l$ , где $b_{1}, b_{2}, \dots, b_{l}$ – неизвестные в обозначениях указанной работы.

Сведения о евклидовых кольцах

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

[1] Кольцо целостности $E$ называется евклидовым, если на множестве $E / \{0\}$ можно определить функцию $h$ , значения которой являются целыми неотрицательными числами так, что выполняются условия

$E_{1} : если b | a, то h (a) \geq h (b),$

$E_{2} : для любых a, b, \in E, где b \neq 0 найдутся элементы q, r \in E,$

$такие что a = b q + r, где r = 0 или h (r) < h (b) .$

В этом определении функция h есть евклидова норма.

[2] Два элемента a и b евклидова кольца E называются сравнимыми по модулю $m \in E$ , если $m | (a - b)$ и записывают $a \equiv b (mod m)$ .

К вопросу о возможности решения линейного уравнения над евклидовым кольцом относятся следующие два утверждения (см. [8], [9]).

[1] Всякое конечное множество $A = \{a_{1}, a_{2}, \dots, a_{n}\}$ ненулевых элементов евклидова кольца R обладает наибольшим общим делителем и при этом НОД $(a_{1}, a_{2}, \dots, a_{n})$ определен с точностью до делителей единицы кольца R.

[2] (о линейном представлении НОД). Наибольший общий делитель элементов множества $A = \{a_{1}, a_{2}, \dots, a_{n}\}$ может быть представлен как линейная комбинация элементов с коэффициентами из евклидова кольца R.

Линейные уравнения с n неизвестными над евклидовым кольцом

Обобщим теперь метод решения диофантовых уравнений, полученный в [10], [11] на случай линейных уравнений над евклидовым кольцом.

Итак, рассматриваем линейное уравнение

$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b$ (1)

над евклидовым кольцом E, где $a_{k} \in E$ , $k = 1, \dots, n$ ; $b \in E$ с евклидовой нормой h.

В силу леммы 1 введем в евклидовом кольце обозначения

$Δ_{1} = НОД (a_{1}, a_{2}, \dots, a_{n}),$

$Δ_{2} = НОД (a_{2}, \dots, a_{n}),$

$\dots \dots \dots \dots \dots$

$Δ_{k} = НОД (a_{k}, a_{k + 1}, \dots, a_{n}),$

$Δ_{n} = НОД (a_{n}) = a_{n} .$

Уравнение (1) в случае $Δ_{1} ∤ b$ не имеет решений в евклидовом кольце E (по определению делимости в кольце главных идеалов).

Если же $Δ_{1} | b$ , то уравнение (1) будет разрешимым в евклидовом кольце E. Действительно, пусть для уравнения (1) выполняется указанная делимость. В силу леммы 2 о линейном представлении НОД имеем

$a_{1} y_{1} + a_{2} y_{2} + \dots + a_{n} y_{n} = Δ_{1},$ (2)

при некоторых $y_{1}, y_{2}, \dots, y_{n} \in E$ .

Обе части уравнения (2) умножим на элемент $\frac{b}{Δ_{1}}$ . Тогда уравнение (2) примет вид

$a_{1} (\frac{b}{Δ_{1}} y_{1}) + a_{2} (\frac{b}{Δ_{1}} y_{2}) + \dots + a_{n} (\frac{b}{Δ_{1}} y_{n}) = b,$

откуда получаем равенство

$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b,$

где $x_{k} = \frac{b}{Δ_{1}} y_{k} \in E$ , $(k = 1, \dots, n)$ .

Следовательно, уравнение (1) в случае $Δ_{1} | b$ будет разрешимым в евклидовом кольце E и тем самым условие разрешимости линейного диофантова уравнения, изложенное в [11] переносится на евклидовы кольца.

Считая, что $Δ_{1} | b$ , перепишем уравнение (1) в следующем виде

$a_{2} x_{2} + \dots + a_{n} x_{n} = b - a_{1} x_{1} .$

Тогда найдется $x_{1} = x_{1}^{(0)} \in E$ , что выполняется делимость $Δ_{2} | b - a_{1} x_{1}^{(0)}$ и значит, $a_{1} x_{1}^{(0)} \equiv b ({modΔ}_{2})$ , при этом в качестве $x_{1}$ можно взять любой элемент из класса вычетов $x_{1} \equiv x_{1}^{(0)} ({modΔ}_{2})$ .

Заменяем это сравнение равенством $a_{1} x_{1}^{(0)} + a_{2} v_{2} = b$ , где $x_{1}^{(0)}, v_{2} \in E$ , при этом для нахождения $x_{1}^{(0)}$ нужно применить алгоритм Евклида, справедливый и для кольца E вместе с леммой 2 о линейном представлении НОД.

Обозначим $b_{2} = b - a_{1} x_{1}^{(0)}$ и рассмотрим уравнение

$a_{2} x_{2} + \dots + a_{n} x_{n} = b_{2} .$

Как и в предыдущем случае перепишем опять это уравнение в следующем виде

$a_{3} x_{3} + \dots + a_{n} x_{n} = b_{2} - a_{2} x_{2} .$

В силу предыдущего рассуждения найдется значение $x_{2} = x_{2}^{(0)} \in E$ , что выполняется делимость

$a_{3} | b_{2} - a_{2} x_{2}^{(0)},$

т.е. $a_{2} x_{2}^{(0)} \equiv b_{2} ({modΔ}_{3})$ .

Тогда в качестве значения $x_{2}$ можно взять любой элемент из класса вычетов $x_{2} \equiv x_{2}^{(0)} ({modΔ}_{3})$ , при этом $x_{2}^{(0)}$ находим по алгоритму Евклида с применением линейного представления НОД.

Продолжая такой процесс, на предпоследнем шаге получим сравнение вида

$a_{n - 1} x_{n - 1}^{(0)} \equiv b_{n - 1} ({modΔ}_{n}) .$

Тогда в качестве значения неизвестного $x_{n - 1}$ можно взять любой элемент из класса вычетов $({modΔ}_{n})$ .

На последнем шаге получаем уравнение вида

$a_{n} x_{n} = b_{n - 1} - a_{n - 1} x_{n - 1}^{(0)},$

откуда

$x_{n} = \frac{b_{n}}{Δ_{n}},$

где $b_{n} = b_{n - 1} - a_{n - 1} x_{n - 1}^{(0)}$ .

Получившийся набор элементов $(x_{1}^{(0)}, x_{2}^{(0)}, \dots, x_{n}^{(0)}) \in E^{n}$ есть одно из решений линейного уравнения над евклидовым кольцом E.

Действительно, имеем

$x_{n}^{(0)} = \frac{b_{n}}{Δ_{n}} = \frac{b_{n}}{a_{n}} \Rightarrow a_{n} x_{n}^{(0)} = b_{n} \Rightarrow$

$\Rightarrow a_{n} x_{n}^{(0)} = b_{n - 1} - a_{n - 1} x_{n - 1}^{(0)} \Rightarrow$

$\Rightarrow a_{n} x_{n}^{(0)} + a_{n - 1} x_{n - 1}^{(0)} = b_{n - 1}$

и т.д.

В итоге получаем, что

$a_{1} x_{1}^{(0)} + a_{2} x_{2}^{(0)} + \dots + a_{n} x_{n}^{(0)} = b_{1} = b .$

Таким образом, нами доказана следующая

Теорема. Любое решение линейного уравнения

$a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n} = b$

над евклидовым кольцом E при НОД $(a_{1}, a_{2}, \dots, a_{n}) | b$ имеет вид

$(x_{1}^{(0)}, x_{2}^{(0)}, \dots, x_{n}^{(0)}) \in E^{n},$

где

$a_{k} x_{k}^{(0)} \equiv b_{k} ({modΔ}_{k + 1}), 1 \leq k \leq n - 1; x_{n}^{(0)} = \frac{b_{n}}{Δ_{n}};$

при этом элементы $b_{k}$ определяются рекуррентными соотношениями

$b_{k} = b_{k - 1} - a_{k - 1} x_{k - 1}^{(0)}; 2 \leq k \leq n; b_{1} = b;$

$Δ_{k} = НОД (a_{k}, a_{k + 1}, \dots, a_{n}) .$

Пример. Найти какое-нибудь решение линейного уравнения

$(5 + 5 i) x_{1} + (7 + 6 i) x_{2} + (11 + 7 i) x_{3} = 1$

над кольцом $ℤ [i]$ целых гауссовых чисел.

Решение. Ввиду того, что кольцо $ℤ [i]$ является евклидовым, можно применить доказанную теорему. Начнем с того, что евклидова норма в кольце $ℤ [i]$ определяется равенством $h (a + b i) = a^{2} + b^{2}$ , где $a, b \in ℤ$ . Следуя теореме, будем находить значения $Δ_{1}, Δ_{2}, Δ_{3}$ для заданного уравнения.

Имеем

$Δ_{1} = НОД (5 + 5 i,7 + 6 i,11 + 7 i) .$

Применяя алгоритм Евклида, сначала находим НОД $(5 + 5 i,7 + 6 i)$ первых двух коэффициентов заданного уравнения. Для этого рассматриваем частное

$\frac{5 + 5 i}{7 + 6 i} = \frac{(5 + 5 i) (7 - 6 i)}{85} = \frac{13}{17} + \frac{1}{17} i .$

Подбирая ближайшие целые к числам $\frac{13}{17}$ и $\frac{1}{17}$ , будем иметь

$\frac{5 + 5 i}{7 + 6 i} = 1 + 0 i + (- \frac{4}{17} + \frac{1}{17} i),$

откуда

$5 + 5 i = (7 + 6 i) (1 + 0 i) + (- 2 - i)$

при этом очевидно, что $h (- 2 - i) < h (7 + 6 i)$ .

Следуя алгоритму Евклида, делим теперь с остатком число $7 + 6 i$ на $- 2 - i$ в кольце $ℤ [i]$ . Имеем

$\frac{7 + 6 i}{- 2 - i} = \frac{(7 + 6 i) (- 2 + i)}{5} = - 4 - i,$

откуда

$7 + 6 i = (- 2 - i) \cdot (- 4 - i) .$

Значит, НОД $(5 + 5 i,7 + 6 i) = - 2 - i$ .

Тогда

$Δ_{1} = НОД (- 2 - i,11 + 7 i) = НОД (11 + 7 i, - 2 - i) .$

Опять разделив с остатком число $7 + 6 i$ на $- 2 - i$ , получим

$7 + 6 i = (- 2 - i) \cdot (- 6 - i),$

при этом $h (- i) < h (- 2 - i)$ .

Делим еще с остатком число $- 2 - i$ на $- i$ . Имеем

$- 2 - i = (- i) (1 - 2 i) .$

По алгоритму Евклида получаем

$НОД (11 + 7 i, - 2 - i) = - i .$

Значит, $Δ_{1} = - i$ .

Находим теперь

$Δ_{2} = НОД (a_{2}, a_{3}) = НОД (7 + 6 i,11 + 7 i) = НОД (11 + 7 i,7 + 7 i) .$

Применяя опять алгоритм Евклида, выполняем последовательные деления с остатками. Имеем

$11 + 7 i = (7 + 6 i) \cdot 1 + 4 + i,$

при этом $h (4 + i) < h (7 + 6 i)$ .

Далее делим $7 + 6 i$ на $4 + i$ . Имеем

$\frac{7 + 6 i}{4 + i} = 2 + i,$

откуда $7 + 6 i = (4 + i) (2 + i)$ .

Так как последний ненулевой остаток равен $4 + i$ , то $Δ_{2} = 4 + i$ .

Наконец, в силу теоремы автоматически получаем

$Δ_{3} = НОД (a_{3}) = a_{3} = 11 + 7 i .$

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

$a_{2} x_{2} + a_{3} x_{3} = b - a_{1} x_{1} .$

Тогда найдется $x_{1} = x_{1}^{(0)} \in ℤ [i]$ , что выполняется делимость

$Δ_{2} | (1 - (5 + 5 i) x_{1}^{(0)}),$

т.е. $(5 + 5 i) x_{1}^{(0)} \equiv 1 (mod 4 + i)$ .

Заменим это сравнение равенством

$(5 + 5 i) u_{1} + (4 + i) v_{1} = 1,$ (3)

где $u_{1}, u_{2} \in ℤ [i]$ .

Значения для $u_{1}$ и $v_{1}$ найдем, применяя алгоритм Евклида к числам $5 + 5 i$ и $4 + i$ , при этом значения для $v_{1}$ на самом деле не нужно находить. Для этого рассматриваем отношение

$\frac{5 + 5 i}{4 + i} = \frac{25}{17} + \frac{15}{17} i = 1 + i + \frac{8}{17} - \frac{2}{17} i,$

откуда

$5 + 5 i = (4 + i) (1 + i) + 2$

при этом $h (2) < h (4 + i)$ .

Следующее деление с остатком дает

$4 + i = 2 \cdot 2 + i, h (i) < h (2)$

и последнее деление будет

$2 = i (- 2 i) .$

Итак, имеем следующую последовательность делений с остатками

$5 + 5 i = (4 + i) (1 + i) + 2,$

$4 + i = 2 \cdot 2 + i,$ (4)

$2 = i (- 2 i) .$

По алгоритму Евклида получаем

$НОД (5 + 5 i,4 + i) = i$

и значит,

$i = (5 + 5 i) u_{1} + (4 + i) v_{1}$

при некоторых $u_{1}, v_{1} \in ℤ [i]$ .

С другой стороны, поднимаясь снизу вверх по равенствам (??), получаем

$i = 4 + i - 2 \cdot 2 = 4 + i - 2 \cdot \{5 + 5 i - (4 + i) (1 + i)\} = (5 + 5 i) \cdot (- 2) + (4 + i) (3 + 2 i),$

откуда

$1 = (5 + 5 i) \cdot 2 i + (4 + i) (2 - 3 i) .$

Сравнивая это с (3), получаем

$u_{1} = 2 i, т . е . x_{1}^{(0)} = 2 i .$

Теперь по теореме находим $x_{2}^{(0)}$ из сравнения

$a_{2} x_{2}^{(0)} \equiv b_{2} ({modΔ}_{3}),$

т.е. $(7 + 6 i) x_{2}^{(0)} \equiv b_{1} - a_{1} x_{1}^{(0)} (mod a_{3}), где a_{3} = Δ_{3}$

откуда

$(7 + 6 i) x_{2}^{(0)} \equiv 1 - (5 + 5 i) \cdot (2 i) (mod a_{3}),$

$(7 + 6 i) x_{2}^{(0)} \equiv 11 - 10 i (mod 11 + 7 i) .$

Запишем это сравнение в виде равенства

$(7 + 6 i) x_{2}^{(0)} - (11 + 7 i) v_{1} = 11 - 10 i .$ (5)

Так как НОД $(7 + 6 i,11 + 7 i) = Δ_{2} = 4 + i$ , то из (5) получаем

$(2 + i) x_{2}^{(0)} - (3 + i) v_{2} = 2 - 3 i .$

Ясно, что

$НОД (2 + i,3 + i) = 1.$ (6)

Находим НОД $(2 + i,3 + i)$ по алгоритму Евклида

$2 + i = (3 + i) \cdot 1 + (- 1),$

$3 + i = (- 1) \cdot (- 3 - i) .$

Значит, $- 1 = (2 + i) \cdot 1 - (3 + i) \cdot 1$ , т.е.

$1 = (2 + i) (- 1) + (3 + i) \cdot 1.$ (7)

Из (6) и (7) следует, что

$x_{2}^{(0)} = - 1, v_{2} = 1.$

Теперь получаем по теореме

$a_{3} x_{3}^{(0)} = b_{2} - a_{2} x_{2}^{(0)},$

т.е.

$(11 + 7 i) x_{3}^{(0)} = b - a_{1} x_{1}^{(0)} - a_{2} x_{2}^{(0)} = 1 - (5 + 5 i) 2 i - (7 + 6 i) (- 1) = 18 - 4 i,$

откуда по теореме

$x_{3}^{(0)} = \frac{b_{3}}{Δ_{3}} = \frac{18 - 4 i}{11 + 7 i} = 1 - i .$

Итак, $x_{1} = 2 i$ , $x_{2} = - 1$ , $x_{3} = 1 - i$ есть одно из решений заданного линейного уравнения.

Заключение

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

2. Полученный результат можно распространить на все евклидовы квадратичные поля (см. [13]).

3. Интересно перенести изложенный метод на линейные уравнения над евклидовыми кольцами многочленов и матриц.

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

About the authors

Urusbi M. Pachev

Kabardino-Balkarian State University named after H.M. Berbekov

Author for correspondence.
Email: [email protected]
ORCID iD: 0009-0002-8362-6174

D. Sci. (Phys. & Math.), Professor, Department of Algebra and Differential Equations, Institute of Physics and Mathematics