Решение линейных уравнений в целых числах

 1. Применение теории делимости к решению неопределенных уравнений в целых числах (работа ученика Кузенкова Александра).

   Неопределенные уравнения – уравнения, содержащие более одного неизвестного. Под одним решением неопределенного уравнения понимается совокупность значений неизвестных, которая обращает данное уравнение в верное равенство.

      Для решения в целых числах уравнения вида ах + by = c, где а, b, c – целые числа, отличные от нуля, приведем ряд теоретических положений, которые позволят установить правило решения. Эти положения основаны также на уже известных фактах теории делимости.

   Теорема 1. Если НОД(а, b) = d, то существуют такие целые числа х и у, что имеет место равенство ах +  bу = d.

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

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

Пример.

Найти линейное представление наибольшего общего делителя чисел 1232 и 1672.

Решение.

1. Составим равенства алгоритма Евклида:

1672 = 1232 ∙1 + 440,

1232 = 440 ∙ 2 + 352,

440 = 352 ∙ 1 + 88,

352 = 88 ∙ 4, т.е. (1672,352) = 88.

2) Выразим 88 последовательно через неполные частные и остатки, используя полученные выше равенства, начиная с конца:

88 = 440 - 352∙1 = (1672 - 1232) - (1232 - 1672∙2 + 1232∙2) = 1672∙3 - 1232∙4, т.е. 88 = 1672∙3 + 1232∙(-4).

Теорема 2. Если уравнение ах +  bу = 1, если НОД(а, b) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и b.

   Справедливость этой теоремы следует из теоремы 1. Таким образом, чтобы найти одно целое решение уравнения ах + bу = 1, если НОД (а, в) = 1, достаточно представить число 1 в виде линейной комбинации чисел а и в.

Пример.

Найти целое решение уравнения 15х + 37у = 1.

Решение.

1. 37 = 15 ∙ 2 + 7,

   15 = 7 ∙ 2 + 1.

2. 1 = 15 - 7∙2 = 15 - (37 - 15∙2) ∙2 = 15∙5 + 37∙(-2),

т.е. х0= 5, у0= -2 - решение данного уравнения.

Теорема 3. Если в уравнении ах + bу = с  НОД(а, b) = d>1 и с не делится на d, то уравнение целых решений не имеет.

   Для доказательства теоремы достаточно предположить противное.

Пример.

Найти целое решение уравнения 16х - 34у = 7.

Решение.

(16,34)=2; 7 не делится на 2, уравнение целых решений не имеет.

Теорема 4. Если в уравнении ах +  bу = с  НОД(а, b) = d>1 и с/d, то оно равносильно уравнению а0х + b0у = с0, в котором НОД(а0, b0) = 1.

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

Теорема 5. Если в уравнении ах + bу = с  НОД(а, b) = 1, то все целые решения этого уравнения заключены в формулах:

х = х0с + bt, у = y0c-at, где х0, y0 - целое решение уравнения  ах + bу = 1,

t – любое целое число.

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

   Приведенные теоремы позволяют установить следующее правило решения в целых числах уравнения ах+ bу = с  НОД(а, b) = 1:

1)                Находится целое решение уравнения ах + bу = 1 путем представления 1 как линейной комбинации чисел а и b (существуют и другие способы отыскания целых решений этого уравнения, например при использовании цепных дробей);

2)                Составляется общая формула целых решений данного уравнения х = х0с + bt,  у = y0c - at, где х0, y0 - целое решение уравнения  ах +  bу = 1, t – любое целое число.

  Придавая t определенные целые значения, можно получить частные решения данного уравнения: наименьшие по абсолютной величине, наименьшие положительные (если можно) и т.д.

Пример.

Найти целые решения уравнения 407х - 2816у = 33.

Решение.

1. Упрощаем данное уравнение, приводя его к виду 37х - 256у = 3.

2.Решаем уравнение 37х - 256у = 1.

256 = 37∙ 6 + 34,

37 = 34 ∙1 + 3,

34 = 3 ∙11 + 1.

1 = 34 - 3∙11 = 256 - 37∙6 - 11 (37 – 256 + 37∙6) = 256∙12 - 37∙83 =

= 37∙(-83) - 256∙(-12),

т.е. х0= -83, y0= -12.

3. Общий вид всех целых решений данного уравнения:

х = -83∙3 - 256t = -249 - 256t,

у = -12∙3 - 37 t = -36 - 37 t.

Положив t = -1, получим х0= 7, у0= 1 и общие формулы решений примут вид:    x = 7 - 256t, у = 1-37t.

2. Заполните таблицу:

3. Изучите Алгоритм решения:

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