Об одном способе решения линейных уравнений над евклидовым кольцом

Полный текст

Введение

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

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

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

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

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

$E_1:\text{если} b|a, \text{то} h\left(a\right)\ge h\left(b\right),$

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

$\text{такие что} a=bq+r, \text{где} r=0 \text{или} h\left(r\right)<h\left(b\right).$        

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

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

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

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

[2] (о линейном представлении НОД). Наибольший общий делитель элементов множества $A=\left\{a_1,a_2,\dots ,a_n\right\}$ может быть представлен как линейная комбинация элементов с коэффициентами из евклидова кольца 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=\mathrm{1,}\dots ,n$; $b\in E$ с евклидовой нормой h.

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

${\text{Δ}}_1=\text{НОД}\left(a_1,a_2,\dots ,a_n\right),$            

${\text{Δ}}_2=\text{НОД}\left(a_2,\dots ,a_n\right),$

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

${\text{Δ}}_k=\text{НОД}\left(a_k,a_{k+1},\dots ,a_n\right),$

${\text{Δ}}_n=\text{НОД}\left(a_n\right)=a_n.$

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

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

$a_1{y}_1+a_2{y}_2+\dots +a_n{y}_n={\text{Δ}}_1,$ (2)

при некоторых $y_1,y_2,\dots ,y_n\in E$.

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

$a_1\left(\frac{b}{{\text{Δ}}_1}{y}_1\right)+a_2\left(\frac{b}{{\text{Δ}}_1}{y}_2\right)+\dots +a_n\left(\frac{b}{{\text{Δ}}_1}{y}_n\right)=b,$                             

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

$a_1{x}_1+a_2{x}_2+\dots +a_n{x}_n=b,$                                          

где $x_k=\frac{b}{{\text{Δ}}_1}{y}_k\in E$, $\left(k=\mathrm{1,}\dots ,n\right)$.

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

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

$a_2{x}_2+\dots +a_n{x}_n=b-a_1{x}_1.$                                          

Тогда найдется $x_1=x_1^{\left(0\right)}\in E$, что выполняется делимость ${\text{Δ}}_2|b-a_1{x}_1^{\left(0\right)}$ и значит, $a_1{x}_1^{\left(0\right)}\equiv b\left({\text{modΔ}}_2\right)$, при этом в качестве $x_1$ можно взять любой элемент из класса вычетов $x_1\equiv x_1^{\left(0\right)}\left({\text{modΔ}}_2\right)$.

Заменяем это сравнение равенством $a_1{x}_1^{\left(0\right)}+a_2{v}_2=b$, где $x_1^{\left(0\right)},v_2\in E$, при этом для нахождения $x_1^{\left(0\right)}$ нужно применить алгоритм Евклида, справедливый и для кольца E вместе с леммой 2 о линейном представлении НОД.

Обозначим $b_2=b-a_1{x}_1^{\left(0\right)}$ и рассмотрим уравнение

$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^{\left(0\right)}\in E$, что выполняется делимость

$a_3|b_2-a_2{x}_2^{\left(0\right)},$                                                       

т.е. $a_2{x}_2^{\left(0\right)}\equiv b_2\left({\text{modΔ}}_3\right)$.

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

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

$a_{n-1}{x}_{n-1}^{\left(0\right)}\equiv b_{n-1}\left({\text{modΔ}}_n\right).$                                             

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

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

$a_n{x}_n=b_{n-1}-a_{n-1}{x}_{n-1}^{\left(0\right)},$                                              

откуда

$x_n=\frac{b_n}{{\text{Δ}}_n},$                                                            

где $b_n=b_{n-1}-a_{n-1}{x}_{n-1}^{\left(0\right)}$.

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

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

$x_n^{\left(0\right)}=\frac{b_n}{{\text{Δ}}_n}=\frac{b_n}{a_n}\Rightarrow a_n{x}_n^{\left(0\right)}=b_n\Rightarrow$

$\Rightarrow a_n{x}_n^{\left(0\right)}=b_{n-1}-a_{n-1}{x}_{n-1}^{\left(0\right)}\Rightarrow$ 

$\Rightarrow a_n{x}_n^{\left(0\right)}+a_{n-1}{x}_{n-1}^{\left(0\right)}=b_{n-1}$

и т.д.

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

$a_1{x}_1^{\left(0\right)}+a_2{x}_2^{\left(0\right)}+\dots +a_n{x}_n^{\left(0\right)}=b_1=b.$                      

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

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

$a_1{x}_1+a_2{x}_2+\dots +a_n{x}_n=b$

над евклидовым кольцом E при НОД$\left(a_1,a_2,\dots ,a_n\right)|b$ имеет вид

$\left(x_1^{\left(0\right)},x_2^{\left(0\right)},\dots ,x_n^{\left(0\right)}\right)\in E^n,$                                              

где

$a_k{x}_k^{\left(0\right)}\equiv b_k\left({\text{modΔ}}_{k+1}\right), 1\le k\le n-1; x_n^{\left(0\right)}=\frac{b_n}{{\text{Δ}}_n};$                        

при этом элементы $b_k$ определяются рекуррентными соотношениями

$b_k=b_{k-1}-a_{k-1}{x}_{k-1}^{\left(0\right)}; 2\le k\le n; b_1=b;$                              

${\text{Δ}}_k=\text{НОД}\left(a_k,a_{k+1},\dots ,a_n\right).$

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

$\left(5+5i\right)x_1+\left(7+6i\right)x_2+\left(11+7i\right)x_3=1$                               

над кольцом $\mathbb{Z}\left[i\right]$ целых гауссовых чисел.

Решение. Ввиду того, что кольцо $\mathbb{Z}\left[i\right]$ является евклидовым, можно применить доказанную теорему. Начнем с того, что евклидова норма в кольце $\mathbb{Z}\left[i\right]$ определяется равенством $h\left(a+bi\right)=a^2+b^2$, где $a,b\in \mathbb{Z}$. Следуя теореме, будем находить значения ${\text{Δ}}_1,{\text{Δ}}_2,{\text{Δ}}_3$ для заданного уравнения.

Имеем

${\text{Δ}}_1=\text{НОД}\left(5+5i\mathrm{,7}+6i\mathrm{,11}+7i\right).$                                      

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

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

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

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

откуда

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

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

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

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

откуда

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

Значит, НОД$\left(5+5i\mathrm{,7}+6i\right)=-2-i$.

Тогда

${\text{Δ}}_1=\text{НОД}\left(-2-i\mathrm{,11}+7i\right)=\text{НОД}\left(11+7i,-2-i\right).$                       

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

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

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

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

$-2-i=\left(-i\right)\left(1-2i\right).$                                                

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

$\text{НОД}\left(11+7i,-2-i\right)=-i.$                                            

Значит, ${\text{Δ}}_1=-i$.

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

${\text{Δ}}_2=\text{НОД}\left(a_2,a_3\right)=\text{НОД}\left(7+6i\mathrm{,11}+7i\right)=\text{НОД}\left(11+7i\mathrm{,7}+7i\right).$          

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

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

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

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

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

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

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

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

${\text{Δ}}_3=\text{НОД}\left(a_3\right)=a_3=11+7i.$                                         

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

$a_2{x}_2+a_3{x}_3=b-a_1{x}_1.$                                              

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

${\text{Δ}}_2|\left(1-\left(5+5i\right)x_1^{\left(0\right)}\right),$                                                

т.е. $\left(5+5i\right)x_1^{\left(0\right)}\equiv 1\left(\text{mod}4+i\right)$.

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

$\left(5+5i\right)u_1+\left(4+i\right)v_1=\mathrm{1,}$ (3)

где $u_1,u_2\in \mathbb{Z}\left[i\right]$.

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

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

откуда

$5+5i=\left(4+i\right)\left(1+i\right)+2$                                            

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

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

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

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

$2=i\left(-2i\right).$                                                         

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

$5+5i=\left(4+i\right)\left(1+i\right)+\mathrm{2,}$            

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

$2=i\left(-2i\right).$           

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

$\text{НОД}\left(5+5i\mathrm{,4}+i\right)=i$                                                

и значит,

$i=\left(5+5i\right)u_1+\left(4+i\right)v_1$                                             

при некоторых $u_1,v_1\in \mathbb{Z}\left[i\right]$.

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

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

откуда

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

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

$u_1=2i, \text{т}.\text{е}. x_1^{\left(0\right)}=2i.$                                               

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

$a_2{x}_2^{\left(0\right)}\equiv b_2\left({\text{modΔ}}_3\right),$                                                 

т.е. $\left(7+6i\right)x_2^{\left(0\right)}\equiv b_1-a_1{x}_1^{\left(0\right)}\left(\text{mod}{a}_3\right), \text{где} a_3={\text{Δ}}_3$ 

откуда

$\left(7+6i\right)x_2^{\left(0\right)}\equiv 1-\left(5+5i\right)\cdot \left(2i\right)\left(\text{mod}{a}_3\right),$                               

$\left(7+6i\right)x_2^{\left(0\right)}\equiv 11-10i\left(\text{mod}11+7i\right).$

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

$\left(7+6i\right)x_2^{\left(0\right)}-\left(11+7i\right)v_1=11-10i.$ (5)

Так как НОД$\left(7+6i\mathrm{,11}+7i\right)={\text{Δ}}_2=4+i$, то из (5) получаем

$\left(2+i\right)x_2^{\left(0\right)}-\left(3+i\right)v_2=2-3i.$                                        

Ясно, что

$\text{НОД}\left(2+i\mathrm{,3}+i\right)=1.$ (6)

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

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

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

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

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

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

$x_2^{\left(0\right)}=-\mathrm{1,} v_2=1.$                                                   

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

$a_3{x}_3^{\left(0\right)}=b_2-a_2{x}_2^{\left(0\right)},$                                                 

т.е.

$\left(11+7i\right)x_3^{\left(0\right)}=b-a_1{x}_1^{\left(0\right)}-a_2{x}_2^{\left(0\right)}=1-\left(5+5i\right)2i-\left(7+6i\right)\left(-1\right)=18-4i,$

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

$x_3^{\left(0\right)}=\frac{b_3}{{\text{Δ}}_3}=\frac{18-4i}{11+7i}=1-i.$                                              

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

Заключение

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

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

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

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

Об авторах

Урусби Мухамедович Пачев

Кабардино-Балкарский государственный университет им. Х.М. Бербекова

Автор, ответственный за переписку.
Email: urusbi@rambler.ru
ORCID iD: 0009-0002-8362-6174

доктор физико-математических наук, профессор, старший научный сотрудник кафедры aлгебры и дифференциальных уравнений

Россия, 360004, Нальчик, ул. Чернышевского, 173

Азамат Хасанович Кодзоков

Кабардино-Балкарский государственный университет им. Х.М. Бербекова

Email: urusbi@rambler.ru
ORCID iD: 0009-0007-3431-1228

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

Россия, 360004, Нальчик, ул. Чернышевского, 173

Алена Георгиевна Езаова

Кабардино-Балкарский государственный университет им. Х.М. Бербекова

Email: urusbi@rambler.ru
ORCID iD: 0009-0004-8691-0706

кандидат физико-математических наук, доцент кафедры алгебры и дифференциальных уравнений

Россия, 360004, Нальчик, ул. Чернышевского, 173

Альбина Аниуаровна Токбаева

Кабардино-Балкарский государственный университет им. Х.М. Бербекова

Email: urusbi@rambler.ru
ORCID iD: 0009-0007-4926-4452

кандидат физико-математических наук, доцент кафедры алгебры и дифференциальных уравнений

Россия, 360004, Нальчик, ул. Чернышевского, 173

Зера Хамидбиевна Гучаева

Кабардино-Балкарский государственный университет им. Х.М. Бербекова

Email: urusbi@rambler.ru
ORCID iD: 0009-0000-9777-4018

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

Россия, 360004, Нальчик, ул. Чернышевского, 173

Список литературы

Дополнительные файлы