Как найти множество общих делителей чисел

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

Как найти все делители числа

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

Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1, -1, a, -a. Возьмем простое число 7: у него есть делители 7, -7, 1 и -1, и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1, -1, 367 и -367.

Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.

Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a=p1s1·p2s2·…·pnsn. Тогда натуральными делителями числа a будут следующие числа: d=p1t2·p2t2·…·pntn, где t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

Учитывая доказательство этой теоремы, мы можем сформировать схему нахождения всех положительных делителей данного числа.

Для этого нужно выполнить следующие действия:

1. Выполнить каноническое разложение на простые множители и получить выражение вида a=p1s1·p2s2·…·pnsn.
2. Найти все значения d=p1t2·p2t2·…·pntn, где числа t1, t2, …, tn будут принимать независимо друг от друга каждое из значений t1=0, 1, …, s1, t2=0, 1, …, s2, …, tn=0, 1, …, sn.

Самым трудным в таком расчете является именно перебор всех комбинаций указанных значений. Разберем подробно решения нескольких задач, чтобы наглядно показать применение данной схемы на практике.

Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.

Продолжим усложнять наши примеры – возьмем четырехзначное число.

Как определить количество делителей конкретного числа

Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a=p1s1·p2s2·…·pnsn, нужно найти значение выражения (s1+1) ·(s2+1) ·…·(sn+1). О количестве наборов переменных t1, t2, …, tn мы можем судить по величине записанного выражения.

Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900, которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900=22·3·52·13. Значит, s1=2, s2=1, s3=2, s4=1. Теперь подставим значения s1, s2, s3 и s4 в выражение (s1+1) ·(s2+1) ·(s3+1) ·(s4+1) и вычислим его значение. Имеем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36. Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.

Как вычислить общие делители нескольких чисел

Зная свойства наибольшего общего делителя, можно утверждать, что количество делителей некоторого набора целых чисел будет совпадать с количеством делителей НОД тех же чисел. Это будет справедливо не только для двух чисел, но и для большего их количества. Следовательно, чтобы вычислить все общие делители нескольких чисел, надо определить их наибольший общий множитель и найти все его делители.

Разберем пару таких задач.

Онлайн калькулятор НОД и НОК двух чисел

Наибольший общий делитель (НОД)

Если натуральное число a делится на натуральное число bb, то bb называют делителем числа aa, а число aa называют кратным числа bb. aa и bb являются натуральными числами. Число gg называют общим делителем и для aa и для bb. Множество общих делителей чисел aa и bb конечно, так как ни один из этих делителей не может быть больше, чем aa. Значит, среди этих делителей есть наибольший, который называют наибольшим общим делителем чисел aa и bb и для его обозначения используют записи: НОД (a;b)(a;b) или D(a;b)(a;b)

Пример
Наибольший общий делитель (НОД) чисел 1818 и 2424 — это 66.

Как найти наибольший общий делитель (НОД)

Существует несколько способов нахождения наибольшего общего делителя (НОД) двух или более целых чисел:

• Алгоритм Евклида: НОД(a,b)=(a, b) = НОД (b,a(b, a mod b)b), где «mod» – это операция взятия остатка от деления большего числа на меньшее. Этот алгоритм можно продолжать до тех пор, пока одно из чисел не станет равно нулю. В этом случае НОД равен ненулевому числу.

Пример
НОД(18,24)=НОД(24,18)=НОД(18,6)=НОД(6,0)=6НОД(18, 24) = НОД(24, 18) = НОД(18, 6) = НОД(6, 0) = 6

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

Пример
НОД(60,84)=22⋅31=12(60, 84) = 2^{2} cdot 3^{1} = 12, так как общие простые множители −2- 2 и 33, их минимальные степени −2- 2 и 11 соответственно.

• Таблица делителей: Составить таблицы всех делителей каждого числа и найти наибольшее общее число, которое является делителем обоих чисел. Этот метод не рекомендуется для больших чисел, так как он требует много времени и усилий.

Наименьшее общее кратное (НОК)

Общими кратными чисел называются числа которые делятся на исходные без остатка. Например для чисел 2525 и 5050 общими кратными будут числа 50,100,150,20050,100,150,200 и т.д Наименьшее из общих кратных будет называться НОК и обозначается НОК(a;b)(a;b) или K(a;b).(a;b).

Пример
Наименьшее общее кратное чисел 88 и 1212 – это 2424. Т.е. НОК (8,12)=24(8, 12) = 24.

Как найти наименьшее общее кратное (НОК)

Чтобы найти НОК двух чисел, необходимо:

1. Разложить числа на простые множители;
2. Выписать множители, входящие в состав первого числа и добавить к ним множители, которые входят в состав второго и не ходят в состав первого;
3. Найти произведение чисел, найденных на шаге 2. Полученное число и будет искомым наименьшим общим кратным.

Пример
Рассмотрим два числа: 88 и 1212. Найдем их НОКНОК:

• Разложим 88 и 1212 на простые множители: 8=23,12=22⋅38 = 2^3, 12 = 2^2 cdot 3.
• Выпишем все простые множители: 23⋅32^3 cdot 3.
• Для каждого простого множителя выберем наибольшую кратность: 232^3 и 33.
• Умножим выбранные простые множители между собой: 23⋅3=242^3 cdot 3 = 24.

Таким образом, НОК чисел 88 и 1212 равен 2424.

Свойства НОД и НОК

• Любое общее кратное чисел aa и bb делится на K(a;b)(a;b);
• Если a⋮bavdots b , то К(a;b)=a(a;b)=a;
• Если К(a;b)=k(a;b)=k и mm-натуральное число, то К(am;bm)=km(am;bm)=km. Если dd-общий делитель для aa и bb,то К(ad;bdfrac{a}{d};frac{b}{d})= kd frac{k}{d}
• Если a⋮cavdots c и b⋮cbvdots c ,то abcfrac{ab}{c} – общее кратное чисел aa и bb;
• Для любых натуральных чисел aa и bb выполняется равенство D(a;b)⋅К(a;b)=abD(a;b)cdot К(a;b)=ab;
• Любой общий делитель чисел aa и bb является делителем числа D(a;b)D(a;b).

Given two integer numbers, the task is to find count of all common divisors of given numbers?

Examples : 

Input : a = 12, b = 24
Output: 6
// all common divisors are 1, 2, 3, 
// 4, 6 and 12

Input : a = 3, b = 17
Output: 1
// all common divisors are 1

Input : a = 20, b = 36
Output: 3
// all common divisors are 1, 2, 4

It is recommended to refer all divisors of a given number as a prerequisite of this article. 

Naive Solution 
A simple solution is to first find all divisors of first number and store them in an array or hash. Then find common divisors of second number and store them. Finally print common elements of two stored arrays or hash. The key is that the magnitude of powers of prime factors of a divisor should be equal to the minimum power of two prime factors of a and b.

• Find the prime factors of a using prime factorization.
• Find the count of each prime factor of a and store it in a Hashmap.
• Prime factorize b using distinct prime factors of a.
• Then the total number of divisors would be equal to the product of (count + 1) 
  of each factor.
• count is the minimum of counts of each prime factors of a and b.
• This gives the count of all divisors of a and b.

Output: 

6

Time Complexity: O(√n log n) 
Auxiliary Space: O(n)

Efficient Solution – 
A better solution is to calculate the greatest common divisor (gcd) of given two numbers, and then count divisors of that gcd. 

Output :  

6

Time complexity: O(n^1/2) where n is the gcd of two numbers.
Auxiliary Space: O(1)

This article is contributed by Aarti_Rathi and Shashank Mishra ( Gullu ). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Another Approach:

1. Define a function “gcd” that takes two integers “a” and “b” and returns their greatest common divisor (GCD) using the Euclidean algorithm.
2. Define a function “count_common_divisors” that takes two integers “a” and “b” and counts the number of common divisors of “a” and “b” using their GCD.
3. Calculate the GCD of “a” and “b” using the “gcd” function.
4. Initialize a counter “count” to 0.
5. Loop through all possible divisors of the GCD of “a” and “b” from 1 to the square root of the GCD.
6. If the current divisor divides the GCD evenly, increment the counter by 2 (because both “a” and “b” are divisible by the divisor).
7. If the square of the current divisor equals the GCD, decrement the counter by 1 (because we’ve already counted this divisor once).
8. Return the final count of common divisors.
9. In the main function, define two integers “a” and “b” and call the “count_common_divisors” function with these integers.
10. Print the number of common divisors of “a” and “b” using the printf function.

The number of common divisors of 12 and 18 is 4.

The time complexity of the gcd() function is O(log(min(a, b))), as it uses Euclid’s algorithm which takes logarithmic time with respect to the smaller of the two numbers.

The time complexity of the count_common_divisors() function is O(sqrt(gcd(a, b))), as it iterates up to the square root of the gcd of the two numbers.

The space complexity of both functions is O(1), as they only use a constant amount of memory regardless of the input size.

Last Updated :
13 Apr, 2023

Like Article

Save Article

Была ли эта статья полезной?

1. Наибольший общий
   делитель и алгоритм Евклида.

2. Свойства наибольшего
   общего делителя.

3. Взаимно простые
   числа.

4. Наименьшее общее
   кратное.

Содержание

1.
Если каждое из целых неотрицательных
чисел а
и
b
делится
на число с,
то число с
называют
общим
делителем чисел.
Чтобы найти общие делители чисел а
и b,
достаточно
найти пересечение двух множеств:
множества делителей числа а
и
множества делителей числа b.
Это пересечение состоит из натуральных
чисел, которые не могут превосходить
меньшего из чисел а
и
b,
а
значит, в нем имеется наибольшее число.
Это число называют наибольшим общим
делителем чисел а
и b.

Определение
3.
Наибольшим
общим делителем (НОД)
чисел а
и
b
называется
самое большое натуральное число d,
являющееся
делителем для каждого из чисел а
и
b.

Наибольший
общий
делитель чисел а
и
b
будем обозначать одним из символов –
НОД(а;b)
или
(а;
b).

Непосредственно
из определения следует, что если хотя
бы одно из чисел а
и
b
отлично
от нуля, то НОД(а;b)
существует и является единственным.
Возникает вопрос: как практически
находить НОД?

Один
из способов нахождения НОД вытекает
непосредственно из определения 3.
Действительно, можно было бы сначала
найти все делители числа а,
затем – числа b.
После
этого отобрать общие делители и выбрать
из них наибольший. Такой путь, однако,
был бы весьма нерациональным, особенно
для больших чисел.

Другой,
наиболее рациональный, способ нахождения
НОД был предложен Евклидом (III
в. до н.э.).

Теорема
6.
Алгоритм
Евклида. Если
а
разделить с остатком на b
≠ 0,
затем разделить с остатком b
на
полученный остаток, затем разделить с
остатком первый остаток на второй и
т.д., то последний, отличный от нуля,
остаток равен (а;b).

Доказательство.
Проводя
последовательно деления с остатком,
указанные в формулировке теоремы,
получим:

(3)

Поскольку
последовательность остатков является
убывающей последовательностью целых
неотрицательных чисел, то через конечное
число шагов очередной остаток (например,
r_п+1)
окажется равным нулю. Пусть r_п
– последний,
отличный от нуля, остаток. Покажем, что
r_п
= (а;b).

Прежде
всего, докажем, что если а
= bq
+ r,
то
(а;b)
= (b;r).

Действительно,
если

и
,
то
по
теореме 2 о делимости разности. С другой
стороны, если
и,
то
по
теореме 1 о делимости суммы.

Таким
образом, множества общих делителей
чисел а
и
b
равны,
а значит, равны и их наибольшие общие
делители, то есть (а;b)
= (b;r).

Применяя
доказанный факт к первому из равенств
3, получим

(а;b)
= (b;r₁).
(4)

Аналогично,
из второго равенства последовательности
(3)

(b;r₁)
= (r₁;r₂).
(5)

Продолжая
аналогичные
рассуждения,
получим равенства:

;
(6)

.
(7)

Исходя
из равенств (4) – (7), можем записать: (а;b)
= (b;r₁)
= (r₁;r₂)
= … = (r_n–2;r_n–1)
= (r_n–1;r_n)
= (r_n;0)
= r_n.
Итак, (а;b)
= r_n.
Теорема
доказана.

Пример.
Найти
НОД(481; 703).

Мы
определили и показали способ нахождения
НОД двух чисел. Аналогично определяется
НОД любого конечного множества целых
неотрицательных чисел.

НОД
чисел
обозначается одним из символов – НОД()
или ().
Если,
то ()
=d_n.

Пример.
Найти
НОД чисел 840, 720, 640 и 160.

1) НОД(840; 720) = 120;

2) НОД(120; 640) = 40;

3) НОД (40; 160) = 40.

Следовательно,
НОД(840; 720; 640; 160) = 40.

2.
Рассмотрим
основные свойства НОД, выраженные
следующими теоремами.

Теорема
7.
НОД двух данных чисел делится на любой
другой общий делитель этих чисел:

.

Доказательство
теоремы вытекает из алгоритма Евклида.
Действительно, из первого равенства
последовательности (3) следует, что если
и,
то.
Во втором равенствеи,
а значит, и.
Рассуждая аналогично, мы можем установить,
что в правой части каждого из следующих
равенств алгоритма вторые слагаемые
должны делиться нас,
то есть
.
Ноr_n
= (а;b).
Следовательно,
и теорема доказана.

Теорема
8. Любой
делитель НОД двух данных чисел является
общим делителем этих чисел:

.

Доказательство.
Очевидно, что теорема 8 является обратной
для теоремы 7. Пусть
.
Докажем, чтои.

По
определениям делимости и НОД можем
записать равенства:

,
где
.
(8)

Кроме
того, по условию теоремы,
,
где
.
Заменив
в равенствах (8) НОД(а;b)
произведением

,
получим равенства
и,
которые
можно записать в виде
,.
Это означает, чтои.
Таким
образом, теорема доказана.

Теорема
9. Если
каждое из двух данных чисел умножить
на натуральное число, то НОД этих чисел
умножится на то же число:

.

Доказательство.
Пользуясь свойством монотонности
умножения, умножим обе части каждого
из равенств (3) на одно и то же число k.
В
полученных равенствах вместо натуральных
чисел

будут,
соответственно, стоять новые числа:

.

Значит,
(ak;
bk)
= r_nk,
или
(ak;
bk)
=
dk,
что
и требовалось доказать.

Теорема
10. Если
каждое из двух данных чисел разделить
на натуральное число, то НОД этих чисел
разделится на то же число:

.

Доказательство.
Поскольку
данная теорема является обратной теореме
9, то для ее доказательства достаточно
к последовательности равенств (3)
алгоритма Евклида применить преобразования
обратные тем, что были проведены в
теореме 9.

3.
Во многих вопросах теории делимости
используются числа, не имеющие общих
делителей, кроме единицы. Рассмотрим
такие числа более подробно.

Определение
4.
Если НОД чисел равен единице, то числа
называются взаимно
простыми.

–взаимно
просты
.

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

Пример.
Так,
(35; 55; 77) = 1, но (35; 55) = 5, (55; 77) = 11, (35; 77) = 7.

Теорема
11.
Если данные числа разделить на их НОД,
то полученные частные будут числами
взаимно простыми:

.

Следует
заметить, что символы
издесь представляют натуральные числа.

Справедливость
теоремы 11 вытекает из теоремы 10.
Действительно, если каждое из чисел а
и b
разделить на натуральное число d,
то и НОД этих чисел разделится на d,
а
значит, будет равен 1.

Теорема
12.
Если произведение двух чисел делится
на число, взаимно простое с одним из
множителей, то другой множитель делится
на это число:

Доказательство.
По
условию теоремы, (а;
с)
= 1.
Пользуясь
теоремой 9, умножим каждое из чисел а
и с
на число b.
Тогда
НОД этих чисел также умножится на b,
то есть (аb;
сb)
= b.
По
условию теоремы,
.
Кроме
того, очевидно, что
.
Следовательно,
с
является общим делителем чисел ab
и
сb
. Но
тогда, по теореме 7, НОД этих чисел также
делится на с,
то есть
.

Теорема
13.
(Признак
делимости на составное число.) Если
числа а
и
b
взаимно
просты, то число с
делится
на их произведение ab
тогда
и только тогда, когда с
делится
на а
и на b:

.

Доказательство.
Необходимость вытекает
из транзитивности отношения делимости.
Так как
,
то.
Аналогично,
из условия
b
следует,
что
.

Достаточность.
Пусть
и,
причем (а;b)
= 1. Докажем, что
.
Так как,
то
с
= aq₁,
где
.
Зная,
что
,
имеем,
где (а;b)
= 1.
По
теореме 12 это означает, что
,
то естьq_l
= bq₂,
где
.
Итак,
с
= aq₁
= a(bq₂)
= (ab)q₂,
то
есть
.
Теорема
полностью доказана.

Из
этой теоремы вытекает ряд признаков
делимости на числа, каждое из которых
является произведением двух взаимно
простых чисел. Например:

1.
Число х
делится
на 6 тогда и только тогда, когда оно
делится на 2 и 3.

2.
Число х
делится
на 36 тогда и только тогда, когда оно
делится на 4 и 9.

Аналогично
формулируются признаки делимости на
числа 12, 15, 18, 24, 45 и др.

4.
Пусть
а
и
b
– произвольные натуральные числа.
Натуральное число m
называется общим
кратным этих
чисел, если m
делится на каждое из чисел а
и
b.
Если
m
– общее кратное чисел а
и
b,
то,
по транзитивности отношения делимости,
каждое из чисел 2m,
3m,
4m,
… также является общим кратным чисел
а
и
b.
Среди
натуральных общих кратных, по принципу
наименьшего числа, существует наименьшее
общее кратное.

Определение
5.
Наименьшим
общим кратным (НОК)
чисел а
и
b
называется
наименьшее натуральное число т,
являющееся
общим кратным этих чисел.

Наименьшее
общее кратное
чисел а
и
b
будем
обозначать
одним
из
символов – НОК(а;b)
или
[а;
b].

Примечание.
Нуль,
как известно, является общим кратным
для любых натуральных чисел, но, по
определению, НОК(а;b)
> 0.

Теорема
14.
Любое общее кратное двух чисел делится
на их наименьшее общее кратное.

Доказательство
теоремы
проведем методом от противного. Пусть
с
– произвольное
общее кратное чисел а
и
b,
т = [а;
b].
Предположим, что с
не
делится нацело на m.
Тогда, разделив
с
на
m
с
остатком, получим с
= mq
+ r,
0 ≤ r
< m.
Поскольку
с
кратно а
и
b,
mq
кратно
а
и
b,
то, по теореме 2 о делимости разности, r
кратно
а
и
b.
Но
это противоречит тому, что m
является НОК, ибо r
< m.
Полученное противоречие доказывает
теорему.

Докажем
теперь теорему, устанавливающую связь
НОД и HОК
двух чисел. Эта теорема дает практический
способ нахождения НОК двух чисел.

Теорема
15.
НОК и НОД двух натуральных чисел а
и
b
связаны
соотношением

аb
= (а;b)
· [а;
b].

Доказательство.
По
определению НОД можем записать равенства
а
= (а;
b)
а₁,
b
=
(а;
b)b₁.
Тогда

и
.

Из
последних равенств следует, что число


является общим кратным чисел а
и
b,
а значит, по теореме 14, оно делится на
[а;
b].

Следовательно,
можем записать:

.
(9)

Докажем
теперь, что последнее равенство возможно
только при q
= 1.

По
определению НОК можем записать: [а;
b]
= aq₁
и
[а;
b]
= bq₂.
Подставляя
новые
выражения НОК в равенство (9), получим

и

.

Из последних
равенств, в свою очередь, имеем

и

.

Отсюда
и.Таким
образом, выражение (а;b)q
является
общим делителем чисел а
и
b.
Но это возможно только
при q
= 1.

Итак, равенство
(9) можем переписать в виде

,
или
ab
= (а;b)
[а;
b]

Теорема доказана.

Следствие.
НОК двух взаимно простых чисел равно
их произведению.

Пример.
Найти НОК чисел 315 и 126.

НОК(315;
126) =
.

Мы
рассмотрели определение и способ
нахождения НОК двух чисел. Аналогично
определяется НОК любого конечного
множества чисел. НОК чисел
обозначают[]
и находят по следующему правилу: сначала
находят
[а₁;а₂]
= m₂,
затем – [m₂;a₃]
= m₃,
[m₃;a₄]
= m₄,
…, [m_n–1;a_n]
= m_n.
Тогда [a₁;a₂;
…;a_n]
=m_n.

Пример.
Найти
НОК чисел 30, 120, 72 и 64.

1) НОК(30; 120) = 120;

2)
НОК(120; 72) =
;

3)
НОК(360;64) =
.

Следовательно,
НОК(30; 120; 72; 64) = 2880.