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

Материал из Юнциклопедии
Перейти к: навигация, поиск

Более 400 каналов всего за 1$ в месяц! Качество, как со спутника, выгодная замена кабельному. Просмотр на смартфоне (Perfect Player), компьютере (IP-TV Player), Smart TV или через IPTV-приставку на любом телевизоре. Россия, Украина, Грузия, США и многое другое в одном пакете.

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

1, а2, ..., а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

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