Линейные диофантовы уравнения

Линейное уравнение a₁x₁+a₂x₂+...+a_nx_n=b (I),

в котором a₁, a₂, ..., a_n,bZ и для которого ищутся целочисленные решения, называется линейным диофантовым уравнением относительно неизвестных x₁,x₂,...,x_n .

Критерий разрешимости диофантова уравнения. Диофантово уравнение (I) разрешимо тогда и только тогда, когда (a₁, a₂, ..., a_n)|b.

Пусть уравнение (I) разрешимо. При решении этого уравнения будем рассматривать два случая.

Первый случай. Все коэффициенты уравнения (I) делятся на один из них, например, на a₁. В силу разрешимости (I) a₁|b. А тогда, сокращая обе части на a₁, получим уравнение

x₁+q₂x₂+...+q_nx_n=b₁ (2)

где a_i=a₁q_i, i= , b=a₁b₁.

Ясно, что множество решений (I) и (2) совпадают. Будем решать уравнение (2). Придадим неизвестным x₂,...,x_n произвольные целые значения k₂,...,k_n соответственно. Тогда x₁=b₁-q₂k₂-...-q_nk_n и упорядоченная совокупность

(b₁-q₂k₂-...-q_nk_n,k₂,...,k_n) является решением уравнения (2). Этим способом получаются все решения (2).

Второй случай. Не существует коэффициента a_i делящего все остальные коэффициенты уравнения (1). Этот случай сводится к первому.

Пусть a₁ – наименьший по модулю среди отличных от нуля коэффициентов уравнения (I). Разделим все остальные коэффициенты на a₁ с остатком:

a_i=a₁q_i+r_i,i= ,0r<|a₁|.

Тогда (I) можно записать так:

a₁x₁+(a₁q₂+r₂)x₂+...+(a₁q_n+r_n)x_n=b, или

a₁(x₁+q₂x₂+...+q_nx_n)+r₂x₂+...+r_nx_n=b.

Введем неизвестное y₁,

y₁=x₁+q₂x₂+...+q_nx_n (3)

Относительно неизвестных y_1, x₂,...,x_n будем иметь уравнение

a₁y₁+r₂x₂+...+r_nx_n=b (4)

Легко показать, что уравнение (4) разрешимо. С другой стороны, зная решение уравнения (4) (m₁,m₂,...,m_n), мы найдем решение уравнения (I)

(m₁-q₂m₂-...-m_nq_n,m₂,...,m_n). Любое решение уравнения (I) может быть получено таким способом из соответствующего решения уравнения (4).

В уравнении (4) наименьший из модулей отличных от нуля коэффициентов меньше |a₁|. Если оно не относится к первому случаю, то с ним поступаем аналогично, как с (I) и т.д. После конечного числа шагов мы придем к первому случаю.

Если n>1, то разрешимое уравнение (I) имеет бесконечно много решений.

Пример. Решить линейное диофантово уравнение:

13x₁+7x₂+26x₃-11x₄=5 (5)

Решение. Это уравнение разрешимо,т.к. коэффициенты взаимно просты и 1|5. Наименьший коэффициент равен 7, поэтому делим на него все коэффициенты.

13 =7·1+6,

7 =7·1,

26 =7·3+5 (6)

-11=7·(-2)+3

Составим равенство

x₁+x₂+3x₃-2x₄=y₁, (7)

где коэффициенты – неполные частные из (6). Теперь (7) умножим на 7 и вычтем из (5). Получаем

6x₁+5x₃+3x₄=5-7y₁,

или 6x₁+5x₃+3x₄+7y₁=5 (8)

С этим уравнением поступаем аналогично. Наименьший коэффициент равен 3, поэтому делим на него все коэффициенты и составляем равенство

2x₁+x₃+x₄+2y₁=y₂ (9)

Теперь это равенство умножим на 3 и вычтем из (8). Получим

2x₃+y₁=5-3y₂

или 2x₃+y₁+3y₂=5 (10)

Получим уравнение, относящееся к первому случаю. Полагая x₃=a,y₂=b, где

a и b – произвольные целые числа, получим

y₁=5-2a-3b

Подставим в (9) значения x₃,y₂,y₁ и полагая x₁=c получим

x₄=-2x₁-a-2(5-2a-3b)+b=-2c+3a+7b-10.

Подставляя в равенство (7) значения x₁,x₃,y₁,x₄ получим

x₂=y₁-x₁-3x₃+2x₄=(5-2a-3b)-c-3a+2(-2c+3a+7b-10)=a+11b-5c-15.

Таким образом, {(c,a+11b-5c-15,a,-2c+3a+7b-10)|a,b,cZ} – множество всех решений исходного уравнения.

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

В самом деле, частное решение (x₀,y₀) уравнения

ax+by=c, где d|c (11)

можно найти следующим образом. Представим d=(a,b) в виде

au+bv=d (12)

Если c=c₁d, то умножим равенство (12) на c₁.

a(uc₁)+b(vc₁)=c.

Отсюда следует, что x₀=uc₁,y₀=vc₁ – есть решение уравнения (12).

Теперь можно получить все решения, используя теорему:

Пусть d=(a,b) делит c,a≠0,b≠0 и (x₀,y₀) некоторое решение уравнения (11). Тогда множество решений уравнения (11) Совпадает со множеством

{(x',y')| x'=x₀- t, y'=y₀+ t, t – любое целое число}.

Доказательство смотрите в [2].