НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ двух
или нескольких натуральных чисел - наибольшее из чисел, на к-рые делится
каждое из данных чисел. Напр., H. о. д. 45 и 72 есть 9, H. о. д. 60, 84,
96 и 120 есть 12. H. о. д. пользуются при сокращении дробей: наибольшее
число, на к-рое могут быть сокращены числитель и знаменатель дроби,- их
H. о. д. Если известны разложения заданных чисел на простые множители,
то для получения H. о. д. этих чисел нужно составить произведение тех множителей,
к-рые входят одновременно во все разложения, взяв каждый наименьшее число
раз, какое он встречается. Так, 60 = 2²³*5, 72 = 2²²³³
и 252 = 2²³³*7; поэтому H. о. д. 60, 72 и 252 есть 2²³
= 12. Общим приёмом отыскания H. о. д. двух чисел является способ последовательного
деления, указанный ещё в 3 в. до н. э. Евклидом (Евклида алгоритм).
Он
заключается в том, что большее из двух данных чисел делят на меньшее, затем
меньшее - на остаток от первого деления, остаток от первого деления - на
остаток от второго деления и т. д., до тех пор, пока не дойдут до остатка,
равного нулю. Последний, отличный от нуля, остаток и будет H. о. д. данных
чисел. Напр., чтобы найти H. о. д. 3542 и 2464, выполняют последовательные
деления: 3542=2464*1 + 1078, 2464 = 1078² + 308, 1078 = 308³
+ 154, 308 = 154². В остатке при последнем делении - нуль; следовательно,
H. о. д. 3542 и 2464 равен предпоследнему остатку, то есть 154. Если H.
о. д. двух чисел равен единице, то эти числа наз. взаимно простыми. H.
о. д. d двух чисел а и b и наименьшее общее кратное
т этих чисел связаны соотношением dm = аb. Понятие H. о. д.
применимо не только к числам. Так, напр., H. о. д. двух или нескольких
многочленов есть многочлен наивысшей степени, на к-рый делится каждый из
данных. Для нахождения H. о. д. многочленов применяются приёмы, совершенно
аналогичные указанным выше для чисел (в частности, алгоритм Евклида).

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я