Решение
Пример
Решение
Пример
Решение
Пример
Дано a = 161 и b = 28, надо найти НОД (a, b) и значения s и t.
r = r1 – q × r2 s = s1 – qs2 t = t1 – q × t2
Для отображения алгоритма мы используем следующую таблицу:
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. Первое значение r2 соответствует условию завершения алгоритма. Мы получаем НОД (17, 0) = 17, s = 1 и t = 0. Это показывает, почему мы должны придавать начальные значения s1 — 1 и t1 — 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. Отсюда ясно, что мы должны инициализировать s2 равным 0, а t2 — равным 1. Ответ может быть проверен, как это показано ниже:
(0 × 0) + (1 × 45) = 45
Хотя очень важное приложение расширенного алгоритма Евклида будет рассмотрено далее, здесь мы остановимся на другом приложении — "нахождение решения линейных диофантовых уравнений двух переменных", а именно, уравнения ax + by = c. Мы должны найти значения целых чисел для x и y, которые удовлетворяют этому уравнению. Этот тип уравнения либо не имеет решений, либо имеет бесконечное число решений. Пусть d = НОД (a, b). Если d†c, то уравнение не имеет решения. Если d|c, то мы имеем бесконечное число решений. Одно из них называется частным, остальные — общими.