Способы нахождения делителей числа

Нахождение всех делителей числа, число делителей числа.

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

Навигация по странице.

Все делители числа, их нахождение

Дальнейшее изложение подразумевает хорошее владение информацией статьи делители и кратные числа. Мы будем говорить лишь о поиске всех делителей целых положительных чисел (натуральных чисел). Этого вполне достаточно, так как одно из свойств делимости утверждает, что множество делителей целого отрицательного числа −a совпадает со множеством делителей противоположного числа a (которое будет положительным). Напомним также, что число 0 имеет бесконечно много делителей, и нахождение всех делителей нуля не представляет интереса.

положительными делителями простого числа a являются лишь единица и само это число. Следовательно, любое простое число a имеет четыре делителя, среди которых два положительных и два отрицательных: 1 , −1 , a и −a . Например, число 11 – простое, оно имеет всего четыре делителя 1 , −1 , 11 и −11 . Еще пример. Число 367 тоже простое, все его делители – это числа 1 , −1 , 367 и −367 .

Интереснее проходит поиск всех делителей составных чисел. Теоретическая основа этого процесса заключается в следующей теореме.

С одной стороны, по определению делимости число a делится на любое такое число d , так как существует такое целое число q=p₁ (s₁−t₁) ·p₂ (s₂−t₂) ·…·p_n (s_n−t_n) , что a=d·q .

С другой стороны, всякое число d , которое делит a , имеет указанный вид, так как в силу свойств делимости оно не может иметь других простых множителей, кроме p₁, p₂, …, p_n , а показатели этих множителей не могут превышать s₁, s₂, …, s_n соответственно.

Из рассмотренной теоремы следует алгоритм нахождения всех положительных делителей данного числа. Чтобы найти все делители числа a нужно:

• получить его каноническое разложение на простые множители вида a=p₁ s₁ ·p₂ s₂ ·…·p_n s_n ;
• вычислить все значения выражения p₁ t₁ ·p₂ t₂ ·…·p_n t_n , в которых числа t₁, t₂, …, t_n принимают независимо друг от друга каждое из значений t₁=0, 1, …, s₁ , t₂=0, 1, …, s₂ , …, t_n=0, 1, …, s_n .

Обычно наибольшую трудность представляет именно процесс перебора всех возможных комбинаций значений чисел t₁, t₂, …, t_n . Сейчас мы последовательно рассмотрим решения нескольких примеров нахождения всех делителей чисел, откуда будут понятны все тонкости этого процесса.

Найдите все делители числа 8 .

Получить разложение на простые множители числа 8 не составляет труда: 8=2·2·2 . В канонической форме это разложение выглядит так: 8=2 3 . То есть, в нашем случае a=8 , p₁=2 , s₁=3 .

Тогда все делители числа 8 представляют собой значения выражения p₁ t₁ =2 t₁ , в котором t₁ принимает значения 0 , 1 , 2 и 3 ( 3 – последнее значение, так как s₁=3 ). Итак, при t₁=0 имеем 2 t₁ =2 0 =1 , при t₁=1 имеем 2 t₁ =2 1 =2 , при t₁=2 имеем 2 t₁ =2 2 =4 , наконец, при t₁=3 имеем 2 t₁ =2 3 =8 .

Весь процесс нахождения делителей удобно проводить, заполняя таблицу следующего вида:

Таким образом, 1 , 2 , 4 и 8 – это все положительные делители числа 8 . Отрицательными делителями числа 8 являются −1 , −2 , −4 и −8 .

±1 , ±2 , ±4 , ±8 – все делители числа 8 .

Рассмотрим более сложный пример нахождения всех делителей числа a , в нем разложение числа уже будет содержать два простых множителя.

Перечислите все натуральные делители числа 567 .

Сначала разложим на простые множители число 567 :

Каноническое разложение числа 567 на простые множители имеет вид 567=3 4 ·7 . Теперь для нахождения всех натуральных делителей числа 567 заставим t₁ и t₂ пробегать независимо друг от друга значения 0 , 1 , 2 , 3 , 4 и 0 , 1 соответственно, при этом будем вычислять значения выражения 3 t₁ ·7 t₂ . Все эти действия удобно поводить, заполняя следующую таблицу:

1 , 3 , 7 , 9 , 21 , 27 , 63 , 81 , 189 и 567 – все натуральные делители числа 567 .

Еще немного усложним пример.

Найдите все положительные делители числа 3 900 .

Разложив число 3 900 на простые множители, получим его каноническое разложение 3 900=2 2 ·3·5 2 ·13 . Все положительные делители найдем, вычисляя значения выражения 2 t₁ ·3 t₂ ·5 t₃ ·13 t₄ при t₁=0, 1, 2 , t₂=0, 1 , t₃=0, 1, 2 , t₄=0, 1 .

1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 13 , 15 , 20 , 25 , 26 , 30 , 39 , 50 , 52 , 60 , 65 , 75 , 78 , 100 , 130 , 150 , 156 , 195 , 260 , 300 , 325 , 390 , 650 , 780 , 975 , 1 300 , 1 950 , 3 900 — все положительные делители числа 117 000 .

Число делителей числа

Число положительных делителей данного числа a , каноническое разложение которого имеет вид a=p₁ s₁ ·p₂ s₂ ·…·p_n s_n , равно значению выражения (s₁+1)·(s₂+1)·…·(s_n+1) . Величина записанного выражения дает количество всех возможных наборов переменных t₁, t₂, …, t_n , где t₁=0, 1, …, s₁ , t₂=0, 1, …, s₂ , …, t_n=0, 1, …, s_n .

Приведем пример. Вычислим число натуральных делителей числа 3 900 из последнего примера, рассмотренного в предыдущем пункте. Мы выяснили, что 3 900=2 2 ·3·5 2 ·13 , тогда s₁=2 , s₂=1 , s₃=2 , s₄=1 . Осталось вычислить значение выражения (s₁+1)·(s₂+1)·(s₃+1)·(s₄+1) при данных значениях s₁ , s₂ , s₃ и s₄ , которое и даст нам искомое число натуральных делителей. Получаем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36 . Следовательно, число 3 900 имеет 36 натуральных делителей. Если мы пересчитаем все делители числа 3 900 , полученные в предыдущем примере, то убедимся, что их количество действительно равно 36 . Число всех делителей (и положительных и отрицательных) числа 3 900 равно 36·2=72 , так как число 3 900 имеет 36 положительных делителей, и, следовательно, 36 отрицательных, противоположных каждому из положительных делителей.

Найдите число делителей числа 84 .

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

Таким образом, каноническое разложение имеет вид 84=2 2 ·3·7 . Тогда число положительных делителей равно (2+1)·(1+1)·(1+1)=12 . Следовательно, число всех делителей равно 2·12=24 .

число 84 имеет 24 делителя.

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

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

Рассмотрим решения примеров, в которых находятся все общие делители некоторых чисел.

Найдите все натуральные общие делители чисел 50 и 140 , а также их количество.

Сначала нам нужно найти наибольший общий делитель чисел 50 и 140 , для этого воспользуемся алгоритмом Евклида: 140=50·2+40 , 50=40·1+10 , 40=10·4 , то есть, НОД(50, 140)=10 .

Теперь определим все положительные делители числа 10 . Его разложение на простые множители имеет вид 10=2·5 . Тогда 2 0 ·5 0 =1 , 2 0 ·5 1 =5 , 2 1 ·5 0 =2 и 2 1 ·5 1 =10 – все делители числа 10 . Следовательно, числа 1 , 2 , 5 и 10 – это все положительные общие делители чисел 50 и 140 , количество этих делителей равно 4 .

1 , 2 , 5 и 10 – это все натуральные делители чисел 50 и 140 , их количество равно 4 .

Определите число всех положительных общих делителей четырех чисел 90 , 45 , 315 и 585 .

Сначала найдем НОД с помощью разложения чисел на простые множители. Так как 90=2·3·3·5 , 45=3·3·5 , 315=3·3·5·7 и 585=3·3·5·13 , то НОД(90, 45, 315, 585)=3·3·5=3 2 ·5 . Количество всех искомых положительных общих делителей исходных четырех чисел равно количеству всех положительных делителей НОД этих чисел. Вычислим количество делителей НОД(90, 45, 315, 585)=3 2 ·5 , оно равно (2+1)·(1+1)=6 .

Источник

Нахождение всех делителей числа

Все делители числа

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

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

1. Сначала нужно разложить данное число на простые множители.
2. Выписываем каждый полученный простой множитель (без повторов, если какой-то множитель повторяется).
3. Далее, находим всевозможные произведения всех полученных простых множителей между собой и добавляем их к выписанным простым множителям.
4. В конце добавляем в качестве делителя единицу.

Например, найдём все делители числа 40. Раскладываем число 40 на простые множители:

40 20 10 5 1

2 2 2 5

Выписываем (без повторов) каждый полученный простой множитель — это 2 и 5.

Далее находим всевозможные произведения всех полученных простых множителей между собой:

2 · 2 = 4,

2 · 2 · 2 = 8,

2 · 5 = 10,

2 · 2 · 5 = 20,

2 · 2 · 2 · 5 = 40.

Добавляем в качестве делителя 1. В итоге получаем все делители, на которые число 40 делится без остатка:

1, 2, 4, 5, 8, 10, 20, 40.

Других делителей у числа 40 нет.

Калькулятор нахождения всех делителей

Данный калькулятор поможет вам получить все делители числа. Просто введите число и нажмите кнопку «Вычислить».

Источник

Наибольший общий делитель (НОД), свойства и формулы

О чем эта статья:

5 класс, 6 класс

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

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

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

Общий делитель нескольких целых чисел — это такое число, которое может быть делителем каждого числа из указанного множества. Например, у чисел 12 и 8 общим делителем будет четверка. Чтобы это проверить, напишем верные равенства: 8 = 4 * 2 и 12 = 3 * 4. Но у этой пары чисел есть и другие общие делители: 1, -1 и -4.

Любое число можно разделить на 1, -1 и на само себя. Значит у любого набора целых чисел будет как минимум три общих делителя. Если общий делитель больше 0 — противоположное ему значение со знаком минус также является общим делителем.

Если b — делитель целого числа a, которое не равно нулю, то модуль числа b не может быть больше модуля числа a. Значит любое число, не равное 0, имеет конечное число делителей.

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

Например, для 4 и -16 НОД будет 4. Как мы к этому пришли:

Проверить результаты вычислений можно с помощью онлайн-калькулятора НОД и НОК.

1. Зафиксируем все делители четырех: ±4, ±2, ±1.
2. А теперь все делители шестнадцати: ±16, ±8, ±4, ±3 и ±1.
3. Выбираем общие: это -4, -2, -1, 1, 2 и 4. Самое большое общее число: 4. Вот и ответ.

Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.

Найдем наибольший общий делитель нескольких целых чисел: 10, 6, 44, -18. Он будет равен трем. Ответ можно записать так: НОД (12, 6, 42, -18) = 3. А чтобы проверить правильность ответа, нужно записать все делители и выбрать из них самые большие.

Взаимно простые числа — это натуральные числа, у которых только один общий делитель — единица. Их НОД равен 1.

Помимо НОД есть еще и НОК, что расшифровывается, как наименьшее общее кратное и означает наименьшее число, которое делится на каждое из исходных чисел без остатка.

Еще один пример. Рассчитаем НОД для 28 и 64.

Распишем простые множители для каждого числа и подчеркнем одинаковые

Д (64) = 2 * 2 * 2 * 2 * 2 * 2

Найдем произведение одинаковых простых множителей и запишем ответ

НОД (28; 64) = 2 * 2 = 4

Ответ: НОД (28; 64) = 4

Оформить поиск НОД можно в строчку, как мы сделали выше или в столбик, как на картинке.

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

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

Важно! Все свойства НОД будем формулировать для положительных целых чисел, при этом будем рассматривать делители только больше нуля.

Свойство 1. Наибольший общий делитель чисел а и b равен наибольшему общему делителю чисел b и а, то есть НОД (a, b) = НОД (b, a). Перемена мест чисел не влияет на конечный результат.

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

Свойство 2. Если а делится на b, то множество общих делителей чисел а и b совпадает со множеством делителей числа b, поэтому НОД (a, b) = b.

Доказательство

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

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

В частности, если a = b, то НОД (a, b) = НОД (a, a) = НОД (b, b) = a = b.

• Например, НОД (25, 25) = 25.

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

• Например, НОД (4, 40) = 4, так как 40 кратно 4.

Свойство 3. Если a = bq + c, где а, b, с и q — целые числа, то множество общих делителей чисел а и b совпадает со множеством общих делителей чисел b и с. Равенство НОД (a, b) = НОД (b, c) справедливо.

Доказательство

Существует равенство a = bq + c, значит всякий общий делитель чисел а и b делит также и с, исходя из свойств делимости. По этой же причине, всякий общий делитель чисел b и с делит а. Поэтому совокупность общих делителей чисел а и b совпадает с совокупностью общих делителей чисел b и c.

Поэтому должны совпадать и наибольшие из этих общих делителей, и равенство НОД (a, b) = НОД (b, c) можно считать справедливым.

Свойство 4. Если m — любое натуральное число, то НОД (mа, mb) = m * НОД(а, b).

Доказательство

Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД (mа, mb)= mr, где r — это НОД (а, b). На этом свойстве наибольшего общего делителя основан поиск НОД с помощью разложения на простые множители.

Свойство 5. Пусть р — любой общий делитель чисел а и b, тогда НОД (а : p, b : p) = НОД (а, b) : p. А именно, если p = НОД (a, b) имеем НОД (a : НОД (a, b), b: НОД (a, b)) = 1, то есть, числа a : НОД (a, b) и b : НОД (a, b) — взаимно простые.

Так как a = p(a : p) и b = p(b : p), и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД (a, b) = НОД (p(a : p), p(b : p)) = p * НОД (a : p, b : p), откуда и следует доказываемое равенство.

Способы нахождения наибольшего общего делителя

Найти наибольший общий делитель можно двумя способами. Рассмотрим оба, чтобы при решении задач выбирать самую оптимальную последовательность действий.

1. Разложение на множители

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

Пример 1. Найти НОД (84, 90).

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

Подчеркнем все общие множители и перемножим их между собой:

Ответ: НОД (84, 90) = 6.

Пример 2. Найти НОД (15, 28).

Разложим 15 и 28 на простые множители:

Числа 15 и 28 являются взаимно простыми, так как их наибольший общий делитель — единица.

Ответ: НОД (15, 28) = 1.

Пример 3. Найти НОД для 24 и 18.

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

Найдем общие множители чисел 24 и 18: 2 и 3. Для удобства общие множители можно подчеркнуть.

Перемножим общие множители:

НОД (24, 18) =2 * 3 = 6

Ответ: НОД (24, 18) = 6

2. Алгоритм Евклида

Способ Евклида помогает найти НОД через последовательное деление. Сначала посмотрим, как работает этот способ с двумя числами, а затем применим его к трем и более.

Алгоритм Евклида заключается в следующем: если большее из двух чисел делится на меньшее — наименьшее число и будет их наибольшим общим делителем. Использовать метод Евклида можно легко по формуле нахождения наибольшего общего делителя.

Формула НОД: НОД (a, b) = НОД (b, с), где с — остаток от деления a на b.

Пример 1. Найти НОД для 24 и 8.

Так как 24 делится на 8 и 8 тоже делится на 8, значит, 8 — общий делитель этих чисел. Этот делитель является наибольшим, потому что 8 не может делиться ни на какое число, большее его самого. Поэтому: НОД (24, 8) = 8.

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

1. Большее число поделить на меньшее.
2. Меньшее число поделить на остаток, который получается после деления.
3. Первый остаток поделить на второй остаток.
4. Второй остаток поделить на третий и т. д.
5. Деление продолжается до тех пор, пока в остатке не получится нуль. Последний делитель и есть наибольший общий делитель.

Пример 2. Найти наибольший общий делитель чисел 140 и 96:

1. 140 : 96 = 1 (остаток 44)
2. 96 : 44 = 2 (остаток 8)
3. 44 : 8 = 5 (остаток 4)
4. 8 : 4 = 2

Последний делитель равен 4 — это значит: НОД (140, 96) = 4.

Ответ: НОД (140, 96) = 4

Пошаговое деление можно записать столбиком:

Чтобы найти наибольший общий делитель трех и более чисел, делаем в такой последовательности:

1. Найти наибольший общий делитель любых двух чисел из данных.
2. Найти НОД найденного делителя и третьего числа.
3. Найти НОД последнего найденного делителя и четвёртого числа и т. д.

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

Источник