Свойства
Следующие несколько свойств теории делимости.
Свойство 1: если a|1, то a=±1.
Свойство 2: если a|b и b|a, то a=±b
Свойство 3: если a|b и b|c, то a|c
Свойство 4: если a|b и a|c, то a|(m × b + n × c), где m и n — произвольные целые числа.
Пример 2.6
а. Если 3|15 и 15|45 то, согласно третьему свойству, 3|45.
б. Если 3|15 и 3|9, то, согласно четвертому
свойству,
,
что означает 3|66.
Все делители
Положительное целое число может иметь больше чем один делитель. Например, целое число 32 имеет шесть делителей: 1, 2, 4, 8, 16 и 32. Мы можем упомянуть два интересных свойства делителей положительных целых чисел.
Свойство 1: целое число 1 имеет только один делитель — само себя.
Свойство 2: любое положительное целое число имеет по крайней мере два делителя — 1 и само себя (но может иметь больше).
Наибольший общий делитель
Два положительных целых числа могут иметь много общих делителей, но только один наибольший общий делитель. Например, общие делители чисел 12 и 140 есть 1, 2 и 4. Однако наибольший общий делитель — 4
Рис. 2.6. Общие делители двух целых чисел
Наибольший общий делитель двух положительных целых чисел — наибольшее целое число, которое делит оба целых числа.
Алгоритм Евклида
Нахождение наибольшего общего делителя (НОД) двух положительных целых чисел путем составления списка всех общих делителей непригодно для достаточно больших чисел.
К счастью, больше чем 2000 лет назад математик по имени Эвклид разработал алгоритм, который может найти наибольший общий делитель двух положительных целых чисел. Алгоритм Евклида основан на следующих двух фактах:
Факт 1: НОД (a, 0) = a
Факт 2: НОД (a, b) = НОД (b, r), где r — остаток от деления a на b
Первый факт говорит, что если второе целое число — 0, то наибольший общий делитель равен первому числу. Второй факт позволяет нам изменять значение a на b, пока b не станет 0. Например, вычисляя НОД (36, 10), мы можем использовать второй факт несколько раз и один раз первый факт, как показано ниже.
НОД(36,10) = НОД(10,6) = НОД(6,4) = НОД(4,2) = НОД(2,0)
Другими словами, НОД (36, 10) = 2, НОД (10, 6) = 2, и так далее. Это означает, что вместо вычисления НОД (36, 10) мы можем найти НОД (2, 0). показывает, как мы используем вышеупомянутые два факта, чтобы вычислить НОД (a, b).
Рис. 2.7. Алгоритм Евклида
Для определения НОД мы используем две переменные, r1 и r2, чтобы запоминать изменяющиеся значения в течение всего процесса. Они имеют начальное значение a и b. На каждом шаге мы вычисляем остаток от деления r1 на r2 и храним результат в виде переменной r. Потом заменяем r1, на r2 и r2 на r и продолжаем шаги, пока r не станет равным 0. В этот момент процесс останавливается и НОД (a, b) равен r1.
Пример 2.7
Нужно найти наибольший общий делитель 2740 и 1760.
Решение
Применим вышеупомянутую процедуру, используя таблицу. Мы присваиваем начальное значение r1 2740 и r2 значение 1760. В таблице также показаны значения q на каждом шаге. Мы имеем НОД (2740, 1760) = 20.
q |
r1 |
r2 |
r |
1 |
2740 |
1760 |
980 |
1 |
1760 |
980 |
780 |
1 |
980 |
780 |
200 |
3 |
780 |
200 |
180 |
1 |
200 |
180 |
20 |
9 |
180 |
20 |
0 |
|
20 |
0 |
|
Пример 2.8
Найти наибольший общий делитель 25 и 60.
Решение
Мы выбрали этот конкретный пример, чтобы показать, что для алгоритма Евклида безразлично, если первое число меньше, чем второе. Все равно мы получаем правильный ответ НОД (25, 60) = 5.
q |
r1 |
r2 |
R |
0 |
25 |
60 |
25 |
2 |
60 |
25 |
10 |
2 |
25 |
10 |
5 |
2 |
10 |
5 |
0 |
|
5 |
0 |
|