Обобщённый алгоритм Евклида

Дискретная математика для ФРТ

Введение

В пособии рассматриваются следующие задачи:

Основы теории целых чисел,

комбинаторика,

понятие о графах (дополнительный материал),

булевы функции.

Основы теории целых чисел

1. Деление с остатком

Определение

a, b Î Z, b > 0.

Поделить a на b с остатком – значит найти такие числа p и q, что a = bq + r, при этом 0≤r<b.

Примеры:

1. (Показать на доске) 25 = 4×6 + 1

2. (Решить самостоятельно) -25 = -5×6 + 5

Докажем единственность деления с остатком.

В самом деле, если

Тогда

Если левая часть не равна 0, то её модуль не меньше b, поскольку умножаем b на ненулевое целое число. С другой стороны, оба остатка меньше b, поэтому модуль разности в правой части меньше b.

Противоречие!

Поэтому левая часть равна 0, и два представления совпали.

Пример.

Найдутся два целых числа, составленных из одних единиц, которые дают одинаковый остаток при делении на 37.

Решение

Возьмём 38 чисел, составленных из одних единиц. Поскольку остатков от деления на 37 всего 37, то хотя бы у двух чисел совпадут остатки.

Задачи.

1. Найти остаток от деления 2²⁰⁰⁰ на 3.

Решение

Раскрыв скобки, получим много слагаемых, кратных 3, и одно слагаемое, равное 1. Поэтому остаток равен 1.

Ответ: 1.

2. а) доказать, что найдутся два числа, составленные из единиц, разность которых кратна 5007.

б) доказать, что найдётся одно число, составленное из единиц и кратное 5007.

Решение.

а) Возьмём 5008 чисел, составленных из одних единиц. Поскольку остатков от деления на 5007 всего 5007, то хотя бы у двух чисел совпадут остатки, следовательно, их разность будет кратна 5007.

б) Рассмотрим эту разность. В начале её некоторое количество единиц, затем одни нули.

Поскольку нули означают умножение на степень числа 10, а это число взаимно просто с 5007, то нули не помогают для делимости на 5007, их можно отбросить.

Поэтому число из единиц делится на 5007.

Делимость

Говорят, что (a делится на b) или b | a (b делит a), если существует q такое, что a = bq.

Свойства делимости

1. a | b и b | c Þ a | c.

2. a | b и a | c Þ a | (b ± c).

3. a | b и a | c Þ a | (b ± kc), k Î Z.

Наибольший общий делитель и наименьшее общее кратное

Определение.

d = НОД (a₁, … a_n), если d – наибольшее целое число, на которое делятся все a₁, … a_n.

m = НОК (a₁, … a_n), если m – наименьшее целое число, которое делится на все a₁, … a_n.

Алгоритм Евклида

Пример. НОД (72, 96) = НОД (72, 96 - 72) = НОД (72, 24) = 24.

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

Приведём более строгое описание работы алгоритма.

Теорема

Множество общих делителей не меняется при элементарных преобразованиях набора (a₁, … a_n), то есть при замене a_i числом a_i - q× a_k.

В самом деле, если некоторое число d было общим делителем набора (a₁, … a_n), то все линейные комбинации этих чисел, в том числе a_i - q× a_k, делятся на d.

Аналогично, если число d₁ является общим делителем для набора, в котором провели замену, то оно является делителем q× a_k, а, следовательно, является делителем a_i. Следовательно, является делителем исходного набора.

Пример

276 = 84 × 3 + 24

84 = 24 × 3 + 12

24 = 12 × 2

НОД (276, 84) = НОД (84, 24) = НОД (12, 24) = НОД (12, 0) = 12

Общая формула алгоритма для двух чисел.

a = bq₁ + r₁

b = r₁q₂ + r₂

r₁ = r₂q₃ + r₃

r₂ = r₃q₄ + r₄

…

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

r_k-1 = r_kq_k+1 + r_k+1

r_k = r_k+1q_k+2

Тогда НОД (a, b) = r_k+1 (то есть наибольший общий делитель равен последнему ненулевому остатку).

Алгоритм Евклида относится к так называемым «быстрым» алгоритмам, поскольку на каждом шаге остаток уменьшается, по крайней мере, в 2 раза, поэтому за сравнительно небольшое количество шагов алгоритм заканчивает работу.

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

НОД (65, 182, 130) = НОД (65, 182, 0) = НОД (65, 52, 0) = НОД (13, 0, 0) = 13.

Упражнения.

1. Найти НОД (111 111, 1111)

Решение:

Таким образом, НОД (111111, 1111) = 11.

2. Найти НОД (98, 147, 112)

Решение.

НОД (98, 147, 112) = НОД (98, 147, 14) = НОД (0, 147, 14) = НОД (0, 7, 14) = НОД (0, 7, 0) = 7

Обобщённый алгоритм Евклида

(Линейное представление наибольшего общего делителя).

Если d = НОД (a, b), то существуют такие целые числа x и y, что d = ax + by.

Пример.

1 = 7 x + 11 y

1 = 11 × 2 – 7 × 3

Теперь выведем общий метод вычисления линейного представления наибольшего общего делителя набора из произвольного количества чисел.

Определение

Линейным представлением числа d через набор чисел a₁, a₂, … , a_n называется выражение d = x₁a₁ + …. + x_na_n.

Теорема

d = НОД (a₁, … , a_n) Þ $ x₁, …. , x_n: d = x₁a₁ + …. + x_na_n.

Лемма

Элементарное преобразование a_i’ = a_i – ka_j не меняет линейную оболочку набора.

(Линейной оболочкой набора (a₁, … , a_n) называют множество всех выражений вида x₁a₁ + …. + x_na_n)

Доказательство леммы

Каждое число из линейной оболочки (a₁’, … , a_n’) входит в линейную оболочку (a₁, … , a_n), и наоборот.

На самом деле, если число представлено в виде t₁a₁’ + … + t_na_n’, то представив число a_i’ в виде a_i – ka_j, выразим все a₁’, … , a_n’ через (a₁, … , a_n) и получим коэффициенты разложения для системы (a₁, … , a_n).

Аналогично находим представление по системе (a₁’, … , a_n’), если известно разложение по системе (a₁, … , a_n).

Доказательство теоремы

Линейная оболочка набора (a₁, … , a_n) совпадает с линейной оболочкой (0, 0, …, d) (это следует из применения алгоритма Евклида).

Примеры.

276 = 84 × 3 + 24

84 = 24 × 3 + 12

24 = 12 × 2

Раскручивая последовательность вычислений в обратную сторону, получим:

24 = 276 – 84 × 3

12 = 84 – 24 × 3 = 84 – (276 – 84 × 3) × 3 = 84 × 10 – 276 × 3

Итак, 12 = 84 × 10 – 276 × 3

Общая формула:

a = bq₁ + r₁

b = r₁q₂ + r₂

r₁ = r₂q₃ + r₃

r₂ = r₃q₄ + r₄

…

r_k-2 = r_k-1q_k + r_k

r_k-1 = r_kq_k+1 + r_k+1

r_k = r_k+1q_k+2

Отсюда получаем:

r_k+1 = r_k-1 – r_kq_k+1

То есть мы выразили r_k+1 = НОД (a, b) через два предыдущих остатка: r_k и r_k-1.

Далее, воспользовавшись тем, что

r_k = r_k-2 – r_k-1q_k,

выразим r_k+1 в виде r_k+1 = r_k-1 – r_kq_k+1 = r_k-1 – (r_k-2 – r_k-1q_k)q_k+1. (1)

В этом случае получим линейное представление r_k+1 = НОД (a, b) через остатки r_k-1 и r_k-2.

Затем выразим r_k-1 через остатки r_k-2 и r_k-3, подставив полученное представление в формулу (1), получим представление НОД (a, b) через остатки r_k-2 и r_k-3. Продолжим процесс до тех пор, пока не получим линейное представление НОД (a, b) через a и b.

Свойства НОД

1. Если любое положительное число, то

.

Доказательство:

Обозначим . Имеем разложение:

.

Умножим это равенство на :

является делителем чисел и и является линейной комбинацией этих чисел. Следовательно, является наибольшим общим делителем этих чисел:

.

2. Если - любой делитель и , то

Согласно предыдущему:

.

Деля это равенство на , имеем:

.

В частности,

3. Если и взаимно просты и делится на , то делится на .

Действительно, так как и взаимно просты, то найдутся целые числа и , такие что

.

Умножим это равенство на и запишем так:

. (1)

Так как делится на , то левая часть равенства делится на . Поэтому и делится на .

4. Если и взаимно просты, то .

В силу равенства (1) всякий общий делитель и делит . Значит, делит . Но и делит . Поэтому .

Свойства НОК.

1.Всякое кратное чисел называется их общим кратным. Наименьшее из общих кратных называется наименьшим общим кратным чисел . Обозначается: .

2. Свойства кратного двух чисел.

Пусть .

Тогда .

Пусть - кратное и .

Тогда . Но кратно и . Поэтому

- целое число.

Но , поэтому .

Получаем формулу:

.

При любом целом будет кратным и .

При получаем наименьшее общее кратное:

.

Следовательно

Доказаны следующие теоремы.

1) Совокупность общих кратных двух чисел совпадает с совокупностью кратных наименьшего общего кратного этих чисел.

2) Это наименьшее кратное равно произведению чисел, поделенному на их наибольший общий делитель.

3. Наименьшее общее кратное трех и более чисел находится по следующему правилу.

.

Если числа и взаимно просты, то и .

И вообще, если - попарно просты, то

Не нашли, что искали? Воспользуйтесь поиском по сайту: