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

Решение

Пример

Решение

Пример

Решение

Пример

Дано a = 161 и b = 28, надо найти НОД (a, b) и значения s и t.

r = r₁ – q × r₂ s = s₁ – qs₂ t = t₁ – q × t₂

Для отображения алгоритма мы используем следующую таблицу:

q	r1	r2	R	s1	s2	s	t1	t2	t
									-5
						-1		-5
					-1		-5		-23
				-1				-23

 

Мы получаем НОД (161, 28) = 7, s = –1 и t = 6. Ответы могут быть проверены, как это показано ниже.

(–1) × 161 + 6 × 28 = 7

 

Дано a = 17 и b = 0, найти НОД (a, b) и значения s и t.

Для отображения алгоритма мы используем таблицу.

 

q	r1	r2	R	s1	s2	s	t1	t2	t

 

Обратите внимание, что нам не надо вычислять q, r и s. Первое значение r₂ соответствует условию завершения алгоритма. Мы получаем НОД (17, 0) = 17, s = 1 и t = 0. Это показывает, почему мы должны придавать начальные значения s₁ — 1 и t₁ — 0. Ответы могут быть проверены так, как это показано ниже:

(1 × 17) + (0 × 0) = 17

Даны a = 0 и b = 45, найти НОД (a, b) и значения s и t.

Для отображения алгоритма мы используем следующую таблицу:

 

q	r1	r2	R	s1	s2	s	t1	t2	t

 

Мы получаем НОД (0,45) = 45, s = 0 и t = 1. Отсюда ясно, что мы должны инициализировать s₂ равным 0, а t₂ — равным 1. Ответ может быть проверен, как это показано ниже:

(0 × 0) + (1 × 45) = 45

 

Хотя очень важное приложение расширенного алгоритма Евклида будет рассмотрено далее, здесь мы остановимся на другом приложении — "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c. Мы должны найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d†c, то уравнение не имеет решения. Если d|c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.