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

n = 2^y •...

где х, у — неотрицательные целые числа (отсутствие простого мно­жителя 2 в разложении озна­чает, что соответствующий показатель степени равен нулю).

Тогда равенство (5) примет вид:

2^{3 y + 1} •... = 2^3х •...

В силу единственности разложения натурального числа на про­стые множители

Зу + 1 = 3x3(х - у) = 1.

Последнее уравнение является линейным диофантовым уравнени­ем вида ах + Ьу = с, причем коэффи­циенты а = 3, b = -3 делятся на 3, в то время как свободный член с = 1 — нет. Значит, это уравнение не имеет целочисленных решений, что означает ложность исходного предположения о рациональности числа.

.Будем теперь рассматривать только такие уравнения вида ах + by = с, в которых свободный член с делится на d = НОД(а; b ). После деления обеих частей уравнения на d мы получим уравнение того же вида, но уже со взаимно простыми коэффициентами при неизвестных. Только такие уравнения мы будем рассматривать ниже в этом разделе.

В этом случае со стороны теоремы 2 нет препятствий к тому, что­бы уравнение имело целочислен­ные решения. Но отсюда, конечно, не следует, что решения обязаны быть.

На самом деле ответ на этот вопрос положительный.

Теорема 3 . Любое уравнение ах + by = с, где НОД(а; b ) = 1, имеет хотя бы одно решение в целых числах.

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

Прежде всего отметим, что множество М содержит бесконечно мно­го чисел, например, 0= f (0; 0), а = f (1; 0), -а = f (-1; 0), а + b = f (1; 1) и т.д. Поскольку f (- x ; -у) = - f ( x ; у), это множество имеет вид:

{..., -и₂ , -п_1, 0, n ₁ , n ₂ , ...},

где n ₁ < n ₂ < ... — натуральные числа.

Рассмотрим наименьшее положительное число из М, то есть n ₁ и докажем, что оно равно 1. Для этого разделим число |а| на n ₁ с остатком, то есть найдем такие целые числа q (неполное частное) и r (остаток), что |а| = n ₁ q + r, причем 0 rп . Поскольку число n ₁ принадлежит множеству М, для некоторых целых х₀ и у₀ верно равенство n _] = ах₀ + b у₀ . Кроме того,

| а | = sgn (a) • а,

где sgn(а) = +1, если а > О, и sgn(а) = -1, если а < 0.

Тогда

г = | а | - n₁ g = sgn (а) •а - (ах₀ + by ₀ ) - q = ax + by ,

где x: = sgn(а) - x ₀ q , у = -y₀ q — некоторые целые числа. Поэтому неотрицательное целое число г также принадлежит множеству М. Если бы число г было положительным, то условие 0 < r < n , кото­рому удовлетворяет г как остаток от деления на л,, означало бы, что в множестве М есть положительное число, меньшее, чем n ₁ чего быть не может. Значит, r = 0, то есть | а| (а вместе с ним и а) делится без остатка на n₁ .

Аналогичные рассуждения показывают, что и b делится без остатка на n ₁ . Следовательно, n ₁ — общий делитель чисел а и b , a поскольку эти числа взаимно простые, число n ₁ равно 1.

Функция f ( x ; y ) = ax + by обладает свойством: f ( kx ; ky ) = k • f ( x ; у). Поэтому если некоторое число с М, то и число kc M . Как мы установили, 1 М. Значит, и любое целое число k входит в М, то есть М = Z . Это и означает справедливость нашей теоремы.

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

Теорема 4. Если числа а и b — целые, то множество значений функции f ( x ; y ) = ax + by от двух целочис­ленных аргументов х и у совпадает с множеством чисел, кратных d = НОД(а; b ), то есть с множеством {..., —2d, — d , 0, d , 2 d , ...}.

Доказательство. Так как d = НОД(а; b ), числа а и b можно запи­сать в виде: а = da ', b = db ', причем числа а', b ' — взаимно простые. Тогда f ( x ; у) = d •(а'х + b у). В силу теоремы 3, любое целое число n можно представить в виде а'х + b 'у. Поэтому множество чисел, которые могут быть записаны в виде ах + by , есть {..., -2d, - d , 0, d , 2 d , ...}.

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

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

-..., -2а, -а, О, а, 2а, ... и -..., -2 b , - b , О, b , 2 b , ...