Наибольший общий делитель

Всякое целое число, которое делит как число a, так и число b, называется их общим делителем. Тут все просто. "Число c делит число a" означает, что число с делит число a на целые части. Общий делитель двух и более чисел a, b, c, ... означает, что общий делитель может делить любое из них на целые части. Совокупность общих делителей обозначим символом D с индексами, где индексы означают числа, для которых составлена совокупность общих делителей. То есть для чисел a,b запишем D_a,b. Совокупность общих делителей состоит из конечного числа чисел и можно выделить из них наибольшее, например, у чисел 21 и 42 общими делителями будут 1, 3, 7, 21. Число 21 здесь - наибольший общий делитель. Итак, наибольший общий делитель - это наибольшее из чисел совокупности D_a,b,c,..., являющихся общими делителями чисел a, b, c, ... То есть название точно отражает его суть. Обозначается наибольший общий делитель чисел a и b скобками (a, b). Вместо наибольший общий делитель будем писать сокращенно НОД. Если (a, b) = 1, то бишь если единица - НОД чисел a и b, то числа a и b называются взаимно простыми.

Чтобы найти НОД чисел a и b нужно составить совокупности D_a и D_b общих делителей каждого, отобрать общие, а из общих - наибольший.