Наибольший общий делитель нескольких чисел

§ 97. Что такое наибольший общий делитель. Наибольшим общим делителем нескольких чисел называется самое большое число, на которое делятся все эти числа.

Например, наибольший общий делитель трех чисел: 18, 30 и 24 есть 6, потому что 6 есть самое большое число, на которое делятся все эти числа.

Два числа, для которых наибольший общий делитель есть единица, называются взаимно простыми (или относительно простыми). Таковы, например, числа 14 и 15.

Укажем два способа нахождения наибольшего общего делителя нескольких чисел.

§ 98. Способ первый: посредством разложения на простые множители. Пусть требуется найти наибольший общий делитель двух чисел 180 и 126. Для этого предварительно разложим эти числа на простые множители:

180 = 2 · 2 · 3 · 3 · 5,      126 = 2 · 3 · 3 · 7.

Сравнивая между собой множители этих чисел, замечаем, что между ними есть общие, а именно: 2, 3, 3. Каждый из этих общих множителей будет и общим делителем 180 и 126. Чтобы получить составные общие делители, надо перемножить общие множители по два и по три. Наибольший общий делитель, очевидно, получится, если перемножим все общие множители

2 · 3 · 3 = 18.

Пусть еще требуется найти наибольший общий делитель трех чисел: 210, 1260 и 245. Разложим эти числа на простые множители:

Разложение чисел на простые множители

Теперь видим, что наибольший общий делитель этих чисел равен произведению общих множителей 5 и 7, т.е. равен 35.

Подобным образом можно находить наибольший общий делитель четырех. пяти и более данных чисел.

Правило. Чтобы найти наибольший общий делитель нескольких чисел, достаточно, разложить их на простые множители, перемножить между собой те из этих множителей, которые общие всем числам.

Примечание. При этом надо помнить, что если какой-нибудь простой множитель в разложение всех чисел входит несколько раз, то столько же раз он должен войти и в наибольший общий делитель.

Пользуясь введенным в § 92 обозначением степени, мы можем в первом из рассмотренных примеров разложение данных чисел на простые множители записать так:

180 = 22 · 32 · 5,      126 = 2 · 32 · 7;

в наибольший общий делитель данных чисел множители 5 и 7 совсем не войдут, так как 5 не входит во второе число, а 7 не входит в первое число. Множитель 2 войдет 1 раз, так как в разложение второго числа он входит только 1 раз. Множитель же 3 войдет в наибольший общий делитель 2 раза (т. е. во второй степени), так как в оба данных числа он входит во второй степени; таким образом, наибольший общий делитель данных чисел есть

2 · 32 =18.

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

Пример: наибольший общий делитель чисел

9000 = 23 · 32 · 53 и 1350 = 2 · 33 · 52

равен 2 · З2 · 52 = 450.

§ 99. Способ второй: посредством последовательного деления. Сначала мы разъясним этот способ в применении только к двум данным числам, а потом в применении к трем, четырем и более числам.

Способ этот основан на следующих двух предложениях:

I. Если большее из двух данных чисел делится на меньшее, то меньшее есть их наибольший общий делитель.

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

II. Если большее из данных чисел не делится на меньшее, то их наибольший общий делитель равен наибольшему общему делителю двух других чисел, а именно меньшего из данных чисел и остатка от деления большего из них на меньшее.

Пусть, например, даны два числа: 85 и 30, из которых большее не делится на меньшее. Разделив первое на второе, получим; 85 : 30 = 2 (остаток 25); тогда наибольший общий делитель чисел 85 и 30 должен быть также наибольшим общим делителем других двух чисел, а именно: 30 и 25 (это есть 5).

Действительно, из деления мы находим:

85 = 30 · 2 + 25; откуда 25 = 85 – 30 · 2.

Из этих равенств на основании известных нам свойств суммы и разности (§ 82) можно вывести такие два заключения:

1) всякий общий делитель чисел 30 и 25 должен быть также и делителем числа 85;

2) всякий общий делитель чисел 85 и 30 должен быть также и делителем остатка 25.

Оказывается, таким образом, что 2 пары чисел:


должны иметь одни и те же общие делители; значит, и наибольший общий делитель у них должен быть один и тот же.

Посмотрим теперь, как можно пользоваться этими правилами для нахождения наибольшего общего делителя двух чисел.

Пусть требуется найти наибольший общий делитель чисел 391 и 299.

Поиск наибольшего общего делителя

Разделим 391 на 299, чтобы узнать, нс будет ли 299 наибольшим общим делителем (на основании предложения 1). Видим, что 391 не делится на 299 (получается остаток 92), поэтому 299 не есть наибольший общий делитель. На основании предложения II утверждаем, что наибольший общий делитель чисел 391 и 299 есть также наибольший общий делитель чисел меньших, а именно: 299 и 92. Станем искать наибольший общий делитель этих чисел. Для этого делим 299 на 92, чтобы узнать, не будет ли 92 наибольшим общим делителем (предложение I). Видим, что 92 не есть наибольший общий делитель (получается остаток 23).

Теперь опять, на основании предложения II, утверждаем, что наибольший общий делитель чисел 299 и 92 есть также наибольший общий делитель чисел меньших, а именно 92 и 23. Станем искать этот делитель. Для этого делим 92 на 23. Видим, что 23 есть напбольший общий делитель пары чисел 92 и 23, следовательно, и пары чисел 299 и 92, следовательно, и пары данных чисел 391 и 299.

Правило. Чтобы найти наибольший общий делитель двух чисел, делят большее из них на меньшее, потом меньшее на первый остаток, затем первый остаток на второй, второй на третий и т.д. до тех пор, пока не получится в остатке нуль; тогда последний делитель будет наибольшим общим делителем данных чисел.

§ 100. Применение второго способа к трем и более числам. Положим теперь, что требуется найти наибольший общий делитель трех чисел 78, 130 и 195. Для этого найдем сначала наибольший общий делитель каких-нибудь двух из них, например 78 и 130:

Наибольший общий делитель этих чисел оказывается равным 26.

Теперь отыщем наибольший общий делитель числа 26 и третьего данного числа 195:

Полученное таким образом число 13 и есть наибольший общий делитель всех трех данных чисел.

Для объяснения, почему так должно быть, вообразим, что данные числа разложены на простые множители и что мы ищем наибольший общий делитель по первому способу. Тогда число 26, будучи наибольшим общим делителем 130 и 78, должно содержать в себе все простые множители, общие этим числам; число 13, будучи наибольшим общим делителем 26 и 195, должно содержать в себе все простые множители, общие этим числам. Следовательно, число 13 содержит в себе все простые множители, общие всем трем числам: 130, 78 и 195; значит, 13 есть наибольший общий делитель этих чисел.

Если бы, кроме указанных трех чисел, имелось еще четвертое данное число, то надо было бы таким же путем найти наибольший общий делитель 13 и этого четвертого числа и т. д.

Правило. Чтобы найти способом последовательного деления наибольший общий делитель трех и более чисел, находят сначала наибольший общий делитель каких-нибудь двух из них, затем – наибольший общий делитель найденного делителя и какого-нибудь третьего данного числа, далее – наибольший общий делитель последнего делителя и четвертого данного числа и т. д.