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

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

Пример №1:

(28,21)=7, (60,27,42)=3.

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

Пример №2:

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

100 = 2 * 2 * 5 * 5

150 = 2 * 3 * 5 * 5

(100, 150) = 2 * 5 * 5

или

150	100			100	50
100	1			100	2
50				0

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