ЭМАлгебра
Если одно из натуральных чисел делится без остатка на другое, то первое число называется кратным второго, а второе — делителем первого.
Например,
; — кратное числа , а — делитель числа ;
; — кратное числа , а — делитель числа .
А число ни на какое другое не делится!
Не совсем так. Каждое натуральное число (кроме ) имеет, по крайней мере, два различных делителя.
Похоже я уже догадался: это само число и единица. Правильно?
Число, которое имеет только два делителя, называется простым.
Так числа , , , , , , , , , и т.д. простые. Их бесконечное множество.
Подождите, подождите! Но ведь и число делится только на себя и на единицу!
Совершенно верно. Молодец, что заметил это. Действительно, — тоже простое число.
Понятно! А как все-таки называются числа, которые нельзя отнести к простым?
Число, имеющее более двух делителей, называется составным.
Например, число имеет делители , , , , , , , .
Получается, что и составных чисел также бесконечное множество?
Правильно. Ты делаешь заметные успехи. Молодец.
Стараюсь. В связи с этим, мне кажется , что еще что-то осталось недосказанным про .
Да, я совсем упустил из виду . Число имеет только один делитель и не является ни простым, ни составным.
Оглавление
- 1. Понятие натурального числа
- 2. Арифметические действия над натуральными числами
- 3. Запись натуральных чисел
- 4. Делитель и кратное.Простые и составные числа.
- 4.1. Решение задач
- 4.2. Задачи повышенной сложности
- 4.3. Дополнительная теория
- 6.1. Дополнительная теория
Платформа для разработки и использования образовательных онлайн-ресурсов БГУ
на базе LMS MOODLE 3.6.2.© Белорусский государственный университет. Адрес: пр. Независимости, 4, 220030, г. Минск, Республика Беларусь
ГУО “Институт повышения квалификации и переподготовки в области технологий информатизации и управления” БГУ принимает оплату онлайн за подготовительные курсы для школьников
УНП 100336910, юр. адрес: Республика Беларусь, 220004 г. Минск, адрес: Ул. Кальварийская, 9, 826.
Нахождение всех делителей числа, число делителей числа
В данной статье мы поговорим о том, как найти все делители числа. Начнем с доказательства теоремы, с помощью которой можно задать вид всех делителей определенного числа. Далее возьмем примеры нахождения всех нужных делителей и покажем, как именно определить, сколько делителей имеет конкретное число. В последнем пункте подробно рассмотрим примеры задач на нахождение общих делителей нескольких чисел.
Как найти все делители числа
Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 0 .
Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1 , — 1 , a , — a . Возьмем простое число 7 : у него есть делители 7 , — 7 , 1 и — 1 , и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1 , — 1 , 367 и — 367 .
Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.
Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a = p 1 s 1 · p 2 s 2 · … · p n s n . Тогда натуральными делителями числа a будут следующие числа: d = p 1 t 2 · p 2 t 2 · … · p n t n , где t 1 = 0 , 1 , … , s 1 , t 2 = 0 , 1 , … , s 2 , … , t n = 0 , 1 , … , s n .
Доказательство 1
Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что a можно разделить на d , если есть такое число q , что делает верным равенство a = d · q , т.е. q = p 1 ( s 1 − t 1 ) · p 2 ( s 2 — t 2 ) · … · p n ( s n — t n ) .
Любое число, делящее a , будет иметь именно такой вид, поскольку, согласно свойствам делимости, других простых множителей, кроме p 1 , p 2 , … , p n , оно иметь не может, а их показатели в данном случае не превысят s 1 , s 2 , … , s n .
Учитывая доказательство этой теоремы, мы можем сформировать схему нахождения всех положительных делителей данного числа.
Для этого нужно выполнить следующие действия:
- Выполнить каноническое разложение на простые множители и получить выражение вида a = p 1 s 1 · p 2 s 2 · … · p n s n .
- Найти все значения d = p 1 t 2 · p 2 t 2 · … · p n t n , где числа t 1 , t 2 , … , t n будут принимать независимо друг от друга каждое из значений t 1 = 0 , 1 , … , s 1 , t 2 = 0 , 1 , … , s 2 , … , t n = 0 , 1 , … , s n .
Самым трудным в таком расчете является именно перебор всех комбинаций указанных значений. Разберем подробно решения нескольких задач, чтобы наглядно показать применение данной схемы на практике.
Условие: найти все делители 8 .
Решение
Разложим восьмерку на простые множители и получим 8 = 2 · 2 · 2 . Переведем разложение в каноническую форму и получим 8 = 2 3 . Следовательно, a = 8 , p 1 = 2 , s 1 = 3 .
Поскольку все делители восьмерки будут значениями p 1 t 1 = 2 t 1 , то t 1 может принять значения нуля, единицы, двойки, тройки. 3 будет последним значением, ведь s 1 = 3 . Таким образом, если t 1 = 0 , то 2 t 1 = 2 0 = 1 , если 1 , то 2 t 1 = 2 1 = 2 , если 2 , то 2 t 1 = 2 2 = 4 , а если 3 , то 2 t 1 = 2 3 = 8 .
Для нахождения делителей удобно все полученные значения оформлять в виде таблицы:
t 1 2 t 1 0 2 0 = 1 1 2 1 = 2 2 2 2 = 4 3 2 3 = 8 Значит, положительными делителями восьмерки будут числа 1 , 2 , 4 и 8 , а отрицательными − 1 , − 2 , − 4 и − 8 .
Ответ: делителями данного числа будут ± 1 , ± 2 , ± 4 , ± 8 .
Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.
Условие: найдите все делители числа 567 , являющиеся натуральными числами.
Решение
Начнем с разложения данного числа на простые множители.
567 189 63 21 7 1 3 3 3 3 7
Приведем разложение к каноническому виду и получим 567 = 3 4 · 7 . Затем перейдем к вычислению всех натуральных множителей. Для этого будем присваивать t 1 и t 2 значения 0 , 1 , 2 , 3 , 4 и 0 , 1 , вычисляя при этом значения 3 t 1 · 7 t 2 . Результаты будем вносить в таблицу:
t 1 t 2 3 t 1 · 7 t 2 0 0 3 0 · 7 0 = 1 0 1 3 0 · 7 1 = 7 1 0 3 1 · 7 0 = 3 1 1 3 1 · 7 1 = 21 2 0 3 2 · 7 0 = 9 2 1 3 2 · 7 1 = 63 3 0 3 3 · 7 0 = 27 3 1 3 3 · 7 1 = 189 4 0 3 4 · 7 0 = 81 4 1 3 4 · 7 1 = 567 Ответ: натуральными делителями 567 будут числа 27 , 63 , 81 , 189 , 1 , 3 , 7 , 9 , 21 и 567 .
Продолжим усложнять наши примеры – возьмем четырехзначное число.
Условие: найти все делители 3 900 , которые будут больше 0 .
Решение
Проводим разложение данного числа на простые множители. В каноническом виде оно будет выглядеть как 3 900 = 22 · 3 · 52 · 13 . Теперь приступаем к нахождению положительных делителей, подставляя в выражение 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 значения t 1 , равные 0 , 1 и 2 , t 2 = 0 , 1 , t 3 = 0 , 1 , 2 , t 4 = 0 , 1 . Результаты представляем в табличном виде:
t 1 t 2 t 3 t 4 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 0 0 0 0 2 0 · 3 0 · 5 0 · 13 0 = 1 0 0 0 1 2 0 · 3 0 · 5 0 · 13 1 = 13 0 0 1 0 2 0 · 3 0 · 5 1 · 13 0 = 5 0 0 1 1 2 0 · 3 0 · 5 1 · 13 1 = 65 0 0 2 0 2 0 · 3 0 · 5 2 · 13 0 = 25 0 0 2 1 2 0 · 3 0 · 5 2 · 13 1 = 325 0 1 0 0 2 0 · 3 1 · 5 0 · 13 0 = 3 0 1 0 1 2 0 · 3 1 · 5 0 · 13 1 = 39 0 1 1 0 2 0 · 3 1 · 5 1 · 13 0 = 15 0 1 1 1 2 0 · 3 1 · 5 1 · 13 1 = 195 0 1 2 0 2 0 · 3 1 · 5 2 · 13 0 = 75 0 1 2 1 2 0 · 3 1 · 5 2 · 13 1 = 975 t 1 t 2 t 3 t 4 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 1 0 0 0 2 1 · 3 0 · 5 0 · 13 0 = 2 1 0 0 1 2 1 · 3 0 · 5 0 · 13 1 = 26 1 0 1 0 2 1 · 3 0 · 5 1 · 13 0 = 10 1 0 1 1 2 1 · 3 0 · 5 1 · 13 1 = 130 1 0 2 0 2 1 · 3 0 · 5 2 · 13 0 = 50 1 0 2 1 2 1 · 3 0 · 5 2 · 13 1 = 650 1 1 0 0 2 1 · 3 1 · 5 0 · 13 0 = 6 1 1 0 1 2 1 · 3 1 · 5 0 · 13 1 = 78 1 1 1 0 2 1 · 3 1 · 5 1 · 13 0 = 30 1 1 1 1 2 1 · 3 1 · 5 1 · 13 1 = 390 1 1 2 0 2 1 · 3 1 · 5 2 · 13 0 = 150 1 1 2 1 2 1 · 3 1 · 5 2 · 13 1 = 1950 t 1 t 2 t 3 t 4 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 2 0 0 0 2 2 · 3 0 · 5 0 · 13 0 = 4 2 0 0 1 2 2 · 3 0 · 5 0 · 13 1 = 52 2 0 1 0 2 2 · 3 0 · 5 1 · 13 0 = 20 2 0 1 1 2 2 · 3 0 · 5 1 · 13 1 = 260 2 0 2 0 2 2 · 3 0 · 5 2 · 13 0 = 100 2 1 0 1 2 2 · 3 0 · 5 2 · 13 1 = 1300 2 1 0 0 2 2 · 3 1 · 5 0 · 13 0 = 12 2 1 0 1 2 2 · 3 1 · 5 0 · 13 1 = 156 2 1 1 0 2 2 · 3 1 · 5 1 · 13 0 = 60 2 1 1 1 2 2 · 3 1 · 5 1 · 13 1 = 780 2 1 2 0 2 2 · 3 1 · 5 2 · 13 0 = 300 2 1 2 1 2 2 · 3 1 · 5 2 · 13 1 = 3900 Ответ: делителями числа 3 900 будут: 195 , 260 , 300 , 325 , 390 , 650 , 780 , 975 , 75 , 78 , 100 , 130 , 150 , 156 , 13 , 15 , 20 , 25 , 26 , 30 , 39 , 50 , 52 , 60 , 65 , 1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 1 300 , 1 950 , 3 900
Как определить количество делителей конкретного числа
Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a = p 1 s 1 · p 2 s 2 · … · p n s n , нужно найти значение выражения ( s 1 + 1 ) · ( s 2 + 1 ) · … · ( s n + 1 ) . О количестве наборов переменных t 1 , t 2 , … , t n мы можем судить по величине записанного выражения.
Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900 , которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900 = 2 2 · 3 · 5 2 · 13 . Значит, s 1 = 2 , s 2 = 1 , s 3 = 2 , s 4 = 1 . Теперь подставим значения s 1 , s 2 , s 3 и s 4 в выражение ( s 1 + 1 ) · ( s 2 + 1 ) · ( s 3 + 1 ) · ( s 4 + 1 ) и вычислим его значение. Имеем ( 2 + 1 ) · ( 1 + 1 ) · ( 2 + 1 ) · ( 1 + 1 ) = 3 · 2 · 3 · 2 = 36 . Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.
Условие: определите, сколько делителей имеет 84 .
Решение
Раскладываем число на множители.
84 42 21 7 1 2 2 3 7
Записываем каноническое разложение: 84 = 2 2 · 3 · 7 . Определяем, сколько у нас получится положительных делителей: ( 2 + 1 ) · ( 1 + 1 ) · ( 1 + 1 ) = 12 . Для учета отрицательных нужно умножить это число на 2 : 2 · 12 = 24 .
Ответ: всего у 84 будет 24 делителя – 12 положительных и 12 отрицательных.
Как вычислить общие делители нескольких чисел
Зная свойства наибольшего общего делителя, можно утверждать, что количество делителей некоторого набора целых чисел будет совпадать с количеством делителей НОД тех же чисел. Это будет справедливо не только для двух чисел, но и для большего их количества. Следовательно, чтобы вычислить все общие делители нескольких чисел, надо определить их наибольший общий множитель и найти все его делители.
Разберем пару таких задач.
Условие: сколько будет натуральных общих делителей у чисел 140 и 50 ? Вычислите их все.
Решение
Начнем с вычисления НОД ( 140 , 50 ) .
Для этого нам потребуется алгоритм Евклида:
140 = 50 · 2 + 40 , 50 = 40 · 1 + 10 , 40 = 10 · 4 , значит, НОД ( 50 , 140 ) = 10 .
Далее выясним, сколько положительных делителей есть у десяти. Разложим его на простые множители и получим 2 0 · 5 0 = 1 , 2 0 · 5 1 = 5 , 2 1 · 5 0 = 2 и 2 1 · 5 1 = 1 0 . Значит, все натуральные общие делители исходного числа – это 1 , 2 , 5 и 10 , а всего их четыре.
Ответ: данные числа имеют четыре натуральных делителя, равные 10 , 5 , 2 и 1 .
Условие: выясните, сколько общих положительных делителей есть у чисел 585 , 315 , 90 и 45 .
Решение
Вычислим их наибольший общий делитель, разложив число на простые множители. Поскольку 90 = 2 · 3 · 3 · 5 , 45 = 3 · 3 · 5 , 315 = 3 · 3 · 5 · 7 и 585 = 3 · 3 · 5 · 13 , то таким делителем будет 5 : НОД ( 90 , 45 , 315 , 585 ) = 3 · 3 · 5 = 3 2 · 5 .
Чтобы узнать количество этих чисел, нужно выяснить, сколько положительных делителей имеет НОД.
НОД ( 90 , 45 , 315 , 585 ) = 3 2 · 5 : ( 2 + 1 ) · ( 1 + 1 ) = 6 .
Ответ: у данных чисел шесть общих делителей.
Сколько делителей имеет составное число?
да нет же, с каких пор кратность учитывается, количество делителей это количество таких a для b, что для каждого a найдется c: a*c=b, по крайней мере то как вы представили мне кажется неверно ведь если учитывать кратность, то какой смысл от делителя 4, ведь 4 это и есть 2 в степени 2
больше двух
минимум -само это число и единица.
значит. у единицы один делитель..грач 73Мудрец (10675) 1 год назад
в вопросе же про составные числа и написано
Naumenko Высший разум (856829) грач 73, да. показалось про простое. составные могут иметь любое количество простых делителей.
Похожие вопросы
Простые и составные числа
Что представляют собой простые и составные числа. Делитель простого и составного числа
Все натуральные числа (исключение составляет лишь единица) относятся к простым или составным. При этом, основным различием между двумя большими группами чисел является количество делителей. Делители, также, подразделяются на составные и простые. Чтобы само определение составных чисел было более понятным, можно предварительно просмотреть понятия делителей и кратных.
Простыми числам являются натуральные числа больше единицы, имеющие два положительных делителя – себя и 1. Например, делителем чисел 7, 11, 19, 131 выступает только единица и само число.
Составными числами являются натуральные числа больше единицы, но в отличие от простого, они имеет больше положительных делителей — оно делится на единицу, на само себя и, как минимум, на одно натуральное число. Например, разложение составных чисел на делители можно представить следующим образом — число 14 делиться на 1, 2, 7, 14, а число 24 делиться на 1,2, 3, 8, 12, 6, 4.
Так, число 2 является единственным первым наименьшим четным простым числом. Все остальные простые числа принадлежат к нечетной группе. А в числовом ряду составных чисел наименьшим первым числом выступает 4. В числовом ряду можно выделить первые составные и простые числа, но определить последние числовые значения невозможно.
Следует обратить внимание на число 1 – оно занимает особое место, поскольку не относится ни к составным, ни к простым числам. Наличие единственного простого делителя – единицы, является главным отличием от остальных натуральных чисел.
Любое натуральное число n больше единицы представляет простые или составные числа. Учитывая свойства делимости, можно подытожить, что единица и в всегда будут являться делителями любого числа в. То есть, любое число, кроме 1, будет иметь минимум два делителя — единицу и самого себя.
Учитывая все вышесказанное, можно дать следующие определения. Простыми являются числа, натуральное числовое значение, которое обладает только двумя положительными делителями. Составными являются числа – это натуральное числовое значение, которое обладает минимально тремя положительными делителями.
Так, любое число, которое не будет причислено к составным, можно отнести к простым числам. Исключение составляет лишь единица.
Таблица простых чисел
Часто, при выполнении различных заданий, оптимальным решением станет использование таблицы простых чисел. Так как простых чисел множество, таблицы обычно ограничиваются числовым значением 100, 1000 или 10 000. Так, на Рис.1 представлена Таблица простых чисел до 1000.
Представить таблицу для всех существующих простых чисел не является возможным. Поэтому, когда числовой ряд достигает 10000 или 1000000000, следует использовать решето Эратосфена.
Самое время будет рассмотреть Теорему 1 и Теорему 2, которые объяснят последнее утверждение.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Для данной теоремы можно привести следующее доказательство. Допустим, что в – это отличный от единицы наименьший делитель для числа с. Необходимо привести доказательство, используя методику противного, что является простым числом.
Допустим, что является натуральным составным числом. Отсюда следует, что для натурального числа в есть простой делитель составного числа, который отличен как от в, так и от единицы. Данный делитель можно обозначить в1. Далее, требуется, чтобы выполнялось условие 1 < в1 < в.
Из условия следует, что с делится на в, а в делится на в1. Понятие делимости можно выразить следующим образом с = в ⋅ q и в = в 1 ⋅ q 1 , откуда с = в 1 ⋅ ( q 1 ⋅ q), где q и q1 – это целые числа. Учитывая правило умножения целых чисел следует, что их произведение – это целое число с равенством с = в 1 ⋅ (q 1 ⋅ q). Из равенства видно, что в 1 выступает делителем для числа с. Следовательно, получаем несоответствие неравенства 1 , поскольку в – это положительный наименьший и отличный от 1 делитель с.
Простых чисел бесконечно много.
В качестве доказательства можно взять предположительное конечное количество натурального числа m, обозначив, как m1, m2,……. mn. Далее, необходимо рассмотреть вариант нахождения простого числа, которое будет отлично от указанных.
На рассмотрение можно взять число m, которое равно m1, m2,………, mn + 1. Оно не будет равно любому из чисел, которые соответствуют простым натуральным числам m1, m2,……, mn. Число m – простое. Так, можно считать, что теорема доказана. Если число m будет относиться к натуральным составным числам, тогда обозначение должно принять вид mn+1 и должно быть показано несовпадение делителя с m1, m2,……, mn.
Если бы утверждение не соответствовало этому, то с учетом свойств делимости произведения m1, m2,……, mn, получалось бы, что оно делится на mn+1. Так, второе слагаемое данной суммы, равное 1, требовалось бы делить на выражение mn+1, что является невозможным.
Среди любого заданного количества простых чисел может быть найдено любое простое число. Из данного утверждения следует вывод, что простых чисел представлено бесконечное множество.
Математика Эратосфена. Простые и составные числа
Решето Эратосфена — это специальный алгоритм, который позволяет определять все простые числа до целого заданного натурального числа N. Само название методики содержит основной принцип ее функционирования. «Решето» представляет собой «фильтр», пропускающий все ненужные числа, кроме простых.
Так, при составлении «решета» – таблицы, необходимо учитывать, что для выполнения задачи важна проверка чисел в последовательном порядке – начиная с двух и до 100, 1000 и т.д. Если у числа невозможно разложить на простые множители и делители отсутствуют – оно фиксируется в таблице, а если оно является натуральным составным числом, значит необходимо его исключить.
Составляя таблицу простых чисел в привычном порядке приходится поэтапно рассматривать каждую цифру. Необходимо начать с 2 – у нее можно выделить два делителя (1 и 2), поэтому оно является простым числом и может быть занесено в таблицу. Число 2, также, заносим в таблицу. Число 4 можно разложить на простые множители 2 и 2, а значит, в таблице его быть не должно, поскольку оно является составным. А 5 имеет всего два делителя, соответственно, оно фиксируется в таблице. Так, поочередно рассматривается каждое число, вплоть до 100, 1000, 10000 и т, д.
Данная методика является понятной, но весьма долгой и неудобной. Именно решето Эратосфена принято считать оптимальным алгоритмом. Далее, на примере приведенных таблиц будет рассмотрен сам алгоритм.
Найдем все простые натуральные числа от 2 до 50. Для начала, в таблицу заносятся все числа, которые располагаются в указанном числовом ряду
Затем, необходимо поочередно вычеркнуть все числа, кратные 3 (Рис. 4).
Также, необходимо поступить с числами, которые кратны 5 (Рис. 5).
На последнем этапе зачеркиваются числа, кратные 7 и 11 (Рис. 6). В итоге будет получена окончательная таблица натуральных простых чисел от 2 до 50.
Далее стоит остановиться на формулировке Теоремы 3 и ее доказательстве.
Наименьший положительный и отличный от 1 делитель основного числа a
не превосходит √a, где √a арифметическим корнем заданного числа.Доказательство 3
Необходимо обозначить b наименьший делитель составного числа a. Существует такое целое число q, где a=b·q, причем имеем, что b≤q. Недопустимо неравенство вида b>q, так как происходит нарушение условия. Обе части неравенства b≤q следует умножить на любое положительное число b, не равное 1. Получаем, что b·b≤b·q, где b 2 ≤a и b≤√a
Доказанная теорема показывает, что при поочередном вычеркивании чисел из таблицы, необходимо начинать с числа, которое будет равно b² и должно соответствовать неравенству b² ≤ a. Если вычеркивание начнется с чисел, кратных 2, то в первую очередь будет вычеркнуто число 4, а если с кратных 3, то – число 9.
Используя методику Эратосфена при составлении простой числовой таблицы, можно обнаружить, что в процессе вычеркивания натуральных составных чисел, останутся лишь те простые числа, которые не будут превосходить значение квадратного корня из n.
Нет времени решать самому?