Наибольший общий делитель
-
Определение наибольшего общего делителя
- Наибольший общий делитель (НОД) — это наибольший положительный делитель двух чисел.
- НОД обозначается gcd(a, b) и является коммутативной функцией.
- НОД связан с наименьшим общим кратным (НОК) и может быть вычислен с помощью алгоритма Евклида.
-
Свойства НОД
- НОД является мультипликативной функцией, что означает, что НОД(a1⋅a2, b) = НОД(a1, b)⋅НОД(a2, b).
- НОД тесно связан с LCM, и для простых разложений a и b, НОД равен их минимальным степеням.
- Для неотрицательных целых чисел НОД(na − 1, nb − 1) = НОД(a, b) − 1.
-
Вероятность и ожидаемое значение
- Вероятность того, что k чисел, выбранных из {1, …, n}, будут взаимно простыми, равна 1/θ(k) при n стремящемся к бесконечности.
- Ожидаемое значение функции НОД существует для k ≥ 3 и равно приблизительно 1,3684 для k = 3 и 1,1106 для k = 4.
-
В коммутативных кольцах
- В коммутативных кольцах определение НОД обобщается на элементы произвольного кольца.
- В случае интегральных областей и доменов GCD, любые два элемента имеют ассоциированный НОД.
- В евклидовых областях НОД может быть вычислен с использованием алгоритма Евклида.
-
Идеал (a, b)
- В коммутативных кольцах, идеал (a, b) порождается a и b и может быть полезен для определения НОД, даже если у a и b его нет.
-
Рекомендации и дальнейшее чтение
- Ссылки на книги, которые содержат подробное описание алгоритма Евклида и других связанных тем.
Полный текст статьи: