Рассмотрим множество целых чисел Z. Операция деления выполняется не для всех пар чисел из Z.
Дадим определение делимости целых чисел: Число а ∈ Z делится на число b ∈ Z (b ≠ 0), если существует такое число q ∈ Z, что a = bq (ab ).
Если а делится на b, то b называется делителем а, само а называется кратным числа b. Число q называется частным от деления а на b. Число 0 делится на любое b ≠ 0 .
Лемма 1. Если целое число а делится на целое число b и k – целое число, то ak делится на b.
Лемма 2. Если два целых числа a и b делятся на целое число с, то их сумма и разность тоже делятся на с.
Теорема 1. Всякое целое a единственным способом представляется через целое положительное b в форме a = bq + r, 0 £ r < b, где q – неполное частное, r – остаток от деления.
Определение. Общим делителем чисел a1 , а2 ,…, an ∈ Z называется число Z, являющееся делителем каждого из этих чисел. Общий делитель данных чисел называется их наибольшим общим делителем, если он делится на всякий общий делитель этих чисел.
Наибольший общий делитель обозначается следующим образом:
d = НОД (а1, а2, … , аn).
- Если НОД (а1, а2, … , аn) = 1 , то числа а1, а2, … , аn называются взаимно простыми.
Рассмотрим вопрос существования наибольшего общего делителя.
Пусть a = bq + r, 0 £ r < b, где q – неполное частное, r – остаток от деления. Полагаем с1 = а, с2 = b. Последовательное деление с остатком, запишем для удобства в виде цепочки равенств:
с1 = с2 q2 + r3 ,
с2 = с3 q3 + с4 ,
с3 = с4 q4 + с5 ,
………………
сn-2 = сn-1 qn-1 + сn ,
сn-1 = сn qn .
Построенная последовательность называется последовательностью Евклида для чисел а и b. Способ построения такой последовательности путем последовательного деления с остатком называется алгоритмом Евклида.
Пример: найти НОД (3360, 396).
3390 = 3968 + 192,
396 = 1922 + 12,
192 = 1216 .
Следовательно, НОД (3360, 3 96) = 12, cn = 12 .
Следствие. Для любых чисел а1, а2, … , аn ∈ Z существует их наибольший общий делитель.