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

Наибольшее натуральное число, на которое делится каждое из данных целых чисел, называется наибольшим общим делителем этих чисел. Для чисел а₁, а₂, ..., а_n он обозначается

(а₁, а₂, ..., а_n).

Например: (28, 21) = 7, (60, 27, 42) = 3.

Для того чтобы найти наибольший общий делитель двух целых чисел, можно воспользоваться алгоритмом Евклида (см. Евклида алгоритм). Если же каждое из данных чисел разложено на простые множители, то его можно отыскать иначе. Для этого нужно выписать простые числа, входящие в каждое из данных разложений, причем если простой множитель входит в разложение одного из чисел k раз, а в разложение другого - l раз и k < l, то этот простой множитель следует выписать k раз. Произведение всех выписанных простых чисел и даст наибольший общий делитель заданных чисел.

Пример: Найдем (100, 150):

100 = 2•2•5•5

150 = 2•3•5•5

―――――――――――

(100, 150) = 2•5•5 = 50

или

150 | 100

100 | 1

―――

50;

100 | 50

100 | 2

―――

0

Нахождение наибольшего общего делителя двух чисел оказывается полезным при сокращении дробей: после сокращения на наибольший общий делитель числителя и знаменателя полученная дробь будет уже несократимой.