Наибольший общий делитель
Наибо́льший о́бщий дели́тель, наибольший из общих делителей целых, в частности натуральных, чисел . Если данные числа не все равны нулю, то такой делитель существует. Наибольший общий делитель чисел обычно обозначают символом .
Свойства наибольшего общего делителя:
1) Наибольший общий делитель чисел , делится на любой общий делитель этих чисел;
2) ;
3) если целые числа представлены в виде
где – различные простые, , , и , то
Наибольший общий делитель двух натуральных чисел можно найти при помощи алгоритма Евклида. Число шагов, необходимых для отыскания наибольшего общего делителя двух чисел, превосходит не более чем в пять раз число цифр наименьшего из них, записанного в десятичной системе счисления.
Наибольшим общим делителем элементов области целостности называется тот из общих делителей данных элементов, который делится на любой из их общих делителей. Так, наибольший общий делитель двух многочленов над данным полем – тот их общий делитель, который делится на любой из их общих делителей. Если наибольший общий делитель двух элементов области целостности существует, то он единствен с точностью до обратимого множителя. Наибольший общий делитель идеалов и данного кольца называется идеал , порождённый объединением множеств и (см. Факториальное кольцо).