Наибольший общий делитель (НОД) двух или более целых чисел — это наибольшее натуральное число, которое делит каждое из этих чисел без остатка. НОД является важным понятием в арифметике и теории чисел и широко используется при упрощении дробей, решении диофантовых уравнений и нахождении наименьшего общего кратного.
Если наибольший общий делитель двух чисел равен 1, такие числа называют взаимно простыми. Это означает, что у них нет других общих делителей, кроме единицы. Понятие взаимной простоты играет важную роль в ряде математических теорий и алгоритмов, в том числе в криптографии.
Существует несколько способов вычисления НОД. Один из них — метод разложения чисел на простые множители: после разложения выбираются все общие множители с наименьшими степенями, и их произведение даёт наибольший общий делитель. Однако на практике чаще применяется алгоритм Евклида. Он заключается в последовательном делении большего числа на меньшее и замене чисел: если a > b, то НОД(a, b) = НОД(b, a mod b). Процесс повторяется до тех пор, пока остаток не станет равен нулю; последнее ненулевое значение и есть наибольший общий делитель.
НОД связан с наименьшим общим кратным (НОК) через формулу: НОД(a, b) × НОК(a, b) = a × b. Это соотношение позволяет легко находить одно значение, зная другое. НОД можно также обобщить на несколько чисел: например, НОД(a, b, c) = НОД(НОД(a, b), c).
Понятие наибольшего общего делителя широко применяется в различных разделах математики и информатики. Оно лежит в основе алгоритмов шифрования, численных методов, анализа периодичности и многих других задач.