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

Уравнение вида

ах + by = О, где а и b целые, называется линейным однородным диофантовым уравнением с двумя переменными.

Выражая неизвестное х через неизвестное у, приходим к

Так как х должен быть целым числом, то у = at, где t- произвольное целое число. Значит х = —bt.

Таким образом, решениями ЛОДУ ах + by = О являются пары вида (-bt, at), где t є z. Множество всех таких пар называется общим решением ЛОДУ, любая же конкретная пара из этого множества называется частным решением.

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

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

ах + Ьу = с,гдр a,b,c^Z и (а,Ь,с} = 1. (2.205)

Решением уравнения ах + by = с, где а,Ь,с є Zh (a,b,c) = 1, называется пара целых чисел, при подстановке которых в уравнение ах + by = с,

получается верное равенство.

Теорема 2.51

Пусть ах + by =с,причем a, b, с є N,n (а, b)=l. Тогда если с = ab, то уравнение ах + by =с не имеет решений в натуральных числах х, у.

Доказательство. В противном случае было бы

ах + by = ab, ax = b(a-y). (2.206)

Так как числа а и b взаимно простые, то отсюда следовало бы, что х делится на b и, значит х > Ь.

Откуда

ах + by > ах >аЬ (2.207),

получили противоречие, так как ах + by = ab.

Ч.т.д.

Теорема 2.52

Уравнение ах + by = с разрешимо в натуральных числах х, у для каждого натурального с > ab.

Доказательство. Допустим, что а и b - натуральные взаимно простые числа и пусть с - натуральное число большее ab. Как было уже доказано

выше, существуют натуральные числа unv такие, что au-bv = с >ab,

• (2.208)
• (2.209)
• (2.210)
• (2.211)

. (2.212) Ч.т.д.

откуда и поэтому существует такое целое число t, что

Пусть

V U а^<,<Ь

х = u - bt, у = at - v;

эти числа целые, причем х >0, у >0.

Следовательно, х и у - натуральные числа. А значит,

ах + by = a (u -bt) + b(at-v) - au-bv - с

Теорема 2.53

Пусть ах + by =с, причем а, Ь, с є N, и (a, b)= d. Тогда если с кратно d , то уравнение

х + by =с (2.213)

имеет решений в натуральных числах х, у.

Теорема 2.54

Общее решение ЛДУ ax + by = c, (a,b) = 1, задается формулами х = х₀ + bt y = y_Q-at'

(2.214)

где (х₀,у₀) - его частное решение, а множество(~bt,at) - общее решение соответствующего линейного однородного диофантова уравнения (г eZ).

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ах + by = с имеет именно такой вид, какой указан в формулировке предложения.

Пусть (х*, у*) - какое-нибудь решение уравнения

ах + by — с.

Тогда

ах *+Ьу* = с, (2.215)

но ведь и

OX₀+fry₀ ^{= С}-

• (2.216)
• (2.217)

Вычтем из первого равенства второе и получим: a(x*-x₀) + 6(y*-y₀) = O

- однородное уравнение. Его общее решение:

Таким образом, для нахождения общего решения необходимо найти общее решение ЛОДУ, частное решение ЛДУ и их сложить.

Особенно этот способ удобен, когда с кратно а или с кратно b . Если, например, с кратно а, то с = aq, тогда (

решением уравнения ах + by - с.

Встает вопрос о нахождении частного решения уравнения ах + by = с. В зависимости от подходов нахождения частного решения, рассмотрим несколько методов решения диофантова уравнения вида ах: + by = с

Методы решения ЛДУ с двумя неизвестными

Метод Евклида

Методом Евклида назовем метод решения линейного диофантового уравнения, основанный на применении алгоритма Евклида.

Пусть задано линейное диофантово уравнением с двумя неизвестными вида ах + by = с, где а, Ь, с є Z.

Алгоритм его решения методом, основанным на применении алгоритма Евклида заключается в следующем:

• 1) с помощью алгоритма Евклида найти наибольший общий делитель целых аи Ь;
• 2) ответить на вопрос о наличии корней уравнения (если НОД (а,Ь) является делителем с, то уравнение

ах + by = с

имеет решение в целых числах, в противном случае, не имеет);

3) используя алгоритм Евклида, представить найденный НОД(я,Ь) линейным разложением и записать частное решение уравнения ах + by = с (в соответствии с теоремой о линейном разложении НОД, найдутся такие и и v из множества целых чисел, что

au+bv = (2.220)

Умножая теперь равенство

аи + bv = 1

на с, получим:

а(ис) + b(vc) = с, (2.221)

То есть х₀ = ис, у₀ = гс; (2.222)

4) записать общее решение заданного уравнения.

Например, решим уравнение Зх + 7у = 2.

Решение. Так как (3,7) = 1 , уравнение имеет решения.

Найдем частное решение.

Используем алгоритм Евклида: 7 = 3 • 2+1; 3 = 1*3.

Получаем линейное разложение НОД:

1 = —3-2+1-7, То есть

и = —2, v = 1.

x_Q = ис = -2 • 2 = -4, у₀ = vc = l-2 = 2.

Получаем общее решение:

|'х = -4 + 7?₁

b = 2-X >^rae('^sZ-

Ответ: общее решение

fx = -4 + 7f,

Ь = 2-Зг, •'^є2-

Метод цепных дробей

Теорема 2.56

Всякое рациональное число у- можно однозначно представить в виде цепной дроби [^й₍ ] будут являться

конечной цепной дроби, причем элементы

неполными частными из алгоритма Евклида для чисел а и b .

Опишем применение цепных дробей к решению диофантовых уравнений. Рассмотрим уравнение

ах + by - с.

Пусть

(a,b,c) = 1

и

M=i.

Следовательно, существуют такие целые значения х, у, являющиеся а

решениями данного диофантова уравнения. Представим ~ цепной дробью:

у = [a₀;«₁,«₂,...,a„], b

(2.223)

так как тогда по свойству подходящих дробей справедливо:

Р_п A,-i ₌ а А,_. _ (-О'"¹ <1п Я n-l QnQn-X ’ ^Ь Qn- ^bcl„-

aq^-bp^ =(-l)"-1.

Умножим обе части равенства нас : ^a^Q_n^-b(cp__}) = c(-l)ⁿ~^l.

Затем, умножим все на (^_ 1) :

«((- О"'1 сс1п-)- ^((- О"’’ Ф«-і) = с

Таким образом, получаем, что

+> = ((-1Г^1)

У о =

есть частные решения заданного уравнения.

• (2.225)
• (2.226)
• (2.227)

Ч.т.д

Например, с помощью цепных дробей найдем все целые решения уравнения 23х +- 49у = 53.

Решение. (23, 49) = 1, следовательно, уравнение имеет решение в целых числах.

Разложим — в цепную дробь получим:

• 23
• — =(0, 2, 7,1,2).

Составим все подходящие дроби:

Д_0. _ 20 + 1 _ 1 . Р₃ _ 7-1 + 0 _ 7 .

Q, ~ 1 ’ 2, “ 2 -1 + 0 “ 2’ 2₃ “ 7-2 + 1 15 ’

Р₄ _ 1-7 + 1 _ 8 . _ 2-8 + 7 _ 23

Q₄ ~ 1-15 + 2 “ 17 ’ 2₅ “ 2-17 + 15 “ 49 ’

На основании свойства подходящих дробей

P_kQ_k__x-P_k_Q_k:=(-D⁴

получим

17 - 23-8-49 = (-1)⁵

или 23-17+ 49-(-8) =-1.

Умножим обе части равенства на (-53):

23-(-901)+ 49-424 = 53,

то есть частное решение:

х₀ =-901, у₀ =424

Все решения могут быть найдены по формулам л = -901+ 49?

у = 424-23?

ИЛИ

f х = 30 + 49?

?і , ? є Z.

[у = -13-23?

fx = -901 + 49?

Ответ: 5 ,teZ.

[ у = 424 - 23?

Метод сравнений

Опишем метод решения диофантова уравнения вида ах + Ьу=с, основанный на использовании теории сравнений.

Пусть (a,b,с) = 1, (a,b) = .

Следовательно, существуют х, у є Z - решения ах + by — с.

Из уравнения (1) получаем:

с - ах

При целом х необходимо, чтобы и у было целым, что, очевидно, возможно тогда и только тогда, когда справедливо сравнение:

ах = c(modm).

( с- ах₀

А значит, решение: I ^хо + W» ^at I

ах + by = с,

где

с -ах_(}

—л =^'

b

Далее, при найденных х₀ и у₀ , записываем общее решение:

f х = х₀ + bt

V = У о ~^at'

где t є Z.

Метод кратных

Методом кратных мы назвали метод решения линейного диофантова уравнения вида ах + by = с, основанный на использовании теоремы о множестве значений функции f(x; у) = ах + by.

Теорема 2.57

Если числа ли b— целые, то множество значений функции

f(x; у) = ах + by

от двух целочисленных аргументов х и у совпадает с множеством чисел, кратных

d = (а; Ь), то есть с множеством {..., -2d, -d, 0, d, 2d, ...}.

Доказательство. Так как d = НОД(а; Ь), то, очевидно, числа а и b можно записать в виде:

а = da', b = db', (2.229)

причем числа а' и Ь' — взаимно простые. Но, поскольку любое целое число п можно представить в виде

а'х + Ь'у, (2.230)

то множество значений функции

f(x; у) = d -(а'х+ Ь'у) (2.231)

есть множество чисел, которые могут быть записаны в виде

ах + by, (2.232) то есть множество

{..., -2d, -d, 0,d, 2d,...}. (2.233)

Ч.т.д

Приведенное доказательство теоремы дает удобный метод нахождения частного решения уравнений вида ах + by = с (если а и b взаимно простые целые числа).

Алгоритм нахождения частного решения уравнений вида ах + by = с

заключается в следующем:

1) нужно образовать две последовательности чисел:

{..., -2а, -а, 0, а, 2а, ...}

и

{..., -2Ь, -Ь, 0, Ь, 2Ь, ...}

(обычно достаточно выписать по несколько членов в обе стороны),

и расположить их друг под другом так, чтобы положительные члены одной стояли под отрицательными членами другой;

2) затем, рассмотрев всевозможные суммы пар членов этих последовательностей, находим пару, дающую в сумме с.

Например, решим методом кратных линейное диофантово уравнение

Из этой таблицы ясно, что второе число из первой строки (то есть -4), которое соответствует X = -2, и третье число из второй строки (то есть 5), которое соответствует у = -1, и дают в сумме 1.

Таким образом, уравнение 2х - 5у = 1 имеет частное решение х₀= -2,у₀= -1.

В ряде случаев приходится выписывать довольно много (несколько десятков) членов последовательностей ах и by. Тогда, конечно, описанный прием не очень удобен, так как требует больших затрат времени. В этой ситуации следует использовать другие, описанные выше методы.

В заключении параграфа о линейном диофантовом уравнении и методах его решения рассмотрим еще одну задачу:

Остаток от деления некоторого натурального числа п на 6 равен 4, остаток от деления п на 15 равен 7. Чему равен остаток от деления п на 30?

Решение. По теореме о делении с остатком в кольце Z целых чисел, существуют неотрицательные целые х, у, такие, что

п = 6х + 4

и

п = 5у + 7.

Исключая из этих равенств число п, для х и у получим уравнение

бх - 15у = 3

или

2х - 5у = 1.

Найдем какое-нибудь частное решение в целых числах. В качестве такого частного решения можно взять, например, х₀ = -2, у₀ = -1, так что верно равенство 2- (-2)-5-(-1)=1.

Вычитая из уравнения данное равенство, получим:

2(х + 2) = 5(у + 7).

Таким образом, общее решение этого уравнения в целых числах имеет вид:

х + 2 = 5к, у + 1 = 2к,

где к — произвольное целое число.

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

Теперь для числа п имеем:

п = 6х + 4 = 6(5к - 2) + 4 = ЗОк - 8 = 30(к - 1) + 22.

Поскольку целое число (к - 7) неотрицательно, это равенство означает, что остаток от деления и на 30 равен 22.

Ответ: остаток от деления и на 30 равен 22.