Простые и составные числа, свойства простых чисел
Натуральное число $p$ называется простым числом, если у него только $2$ делителя: $1$ и оно само.
Делителем натурального числа $a$ называют натуральное число, на которое исходное число $a$ делится без остатка.
Найти делители числа $6$.
Решение: Нам надо найти все числа, на которые заданное число $6$ делится без остатка. Это будут числа: $1,2,3,6.$ Значит делителем числа $6$ будут числа $1,2,3,6.$
Ответ: $1,2,3,6$.
Значит, для того, чтобы найти делители числа надо найти все натуральные числа, на которые данное делится без остатка. Нетрудно заметить, что число $1$ будет являться делителем любого натурального числа.
На сколько равных кучек можно разделить $15$ орехов?
Решение. Нам необходимо разделить поровну нацело $15$ орехов, т.е. найти делители числа $15$.Найдем числа, на которые число $15$ делится без остатка.
Это числа:$1,3,5,15$. Значит $15$ орехов можно разделить на $1,3,5,15$ равных кучек.
Ответ: на $1,3,5,15$ кучек.
Составным называют число, у которого кроме единицы и самого себя есть другие делители.
Примером простого числа может являться число $13$, примером составного число $14$.
Число $1$ имеет только один делитель-само это число, поэтому его не относят ни к простым, ни к составным.
Взаимно простыми числами называются те, у которых НОД равен $1$.Значит для выяснения будут ли являться числа взаимно простыми необходимо найти их НОД.
Наибольший общий делитель
Наибольшее натуральное число, на которое делятся без остатка числа $a$ и $b$, называется наибольшим общим делителем и часто обозначается НОД.
Чтобы найти наибольший общий делитель двух чисел, необходимо:
- Разложить числа на простые множители
- Выбрать числа, которые входят в разложение этих чисел
- Найти произведение чисел, найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
Найти НОД чисел $63$ и $81$.
Решение: Найдём НОД чисел $63$ и $81$
Разложим числа на простые множители
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Выбираем числа, которые входят в разложение этих чисел
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Найдем произведение чисел, найденных на шаге 2.Полученное число и будет искомым наибольшим общим делителем.
Свойство составных и простых чисел
Любое составное число можно разложить на $2$ множителя, каждый из которых больше единицы. Простое число так представить нельзя.
Действительно, простое число $17$ можно представить в виде произведения множителей только так: $17=1\cdot 17$, а составное число $18=1\cdot 2\cdot 9$. У составного числа $18$ три множителя, два из которых больше единицы.
Всякое составное число можно разложить на простые множители и представить в виде произведения множителей, которые являются простыми числами.
Свойства простых чисел
Если простое число $p$ делится на простое число $q$, то эти числа равны $(p=q)$. Действительно, если $p$ — простое число, то оно по определению имеет только два делителя, а именно $1$ и $p$. Но т.к. по условию $р\vdots q$, значит $q$ равно либо $1$, либо $p$. Т. к $q≠1$, значит $p=q$.
Если $p$- простое число, то любое натуральное число либо делится на $p$, либо взаимно простое с $p$.
В самом деле, допустим, что $p$ и $n$- не взаимно простые. И либо опровергнем, либо убедимся в этом. Если указанные числа не взаимно простые, то у них должен быть хотя бы один общий делитель, отличный от $1$, обозначим его $d$. Но по условию $p$- простое число, значит имеет по определению, всего два делителя-$1$ и $p$.Поскольку $d≠1$, то $d=p$, и поэтому $n$ делится на $p$.
Произведение натуральных чисел $a$ и $b$ делится на простое число $p$ в том случае, когда хотя бы одно из этих чисел делится на $p$.
Данное утверждение верно для произведения нескольких множителей- если такое произведение делится на простое число $p$, то хотя бы один из множителей делится на $p$.
Любое натуральное число, отличное от $1$, является либо простым, либо произведением простых чисел
Если натуральное число m делится на простое число $p$, то в любом разложении этого числа на простые множители хотябы один из множителей равен $p$.
Действительно, пусть $m=p_<1\dots \dots .>p_k$-разложение на множители.Так как $m\vdots p$, то по утверждению,данному в п.3 хотя бы один из множителей делится на $p$.Пусть, например $р_1\vdots p$.Тогда по утверждению , данному в п.1 выполняется равенство $р_1=p$
Любые два разложения составного числа отличаются друг от друга только порядком множителей.
Из простых чисел с помощью умножения можно постоить все натуральные числа.
Свойства простых чисел
Среди простых чисел нет наибольшего
Если $n$-составное натуральное число, то среди его простых делителей есть хотя бы один делитель $p$, такой , что $р^2\le n$.
Второе свойство можно успешно использовать при разложении числа на множители или при проверке его на простоту. Достаточно ограничиться проверкой делимости числа $n$ на простые делители p,для которых будет выполняться $р^2\le n$.
Простые и составные числа — онлайн калькулятор
Простое число — число больше 1, которое делится без остатка на 1 и на самого себя.
Например числа 11, 19, 137.
Составное число — это натуральное число больше 1, которое имеет хотя бы 3 делителя. То есть делится на 1, на самого себя и еще хотя бы на одно натуральное число.
Например число 9 делится без остатка на 1, 3 и 9.
С помощью формы выше можно онлайн узнать, является ли число простым или составным. Найти все делители составного числа.
Нахождение всех делителей числа, число делителей числа
В данной статье мы поговорим о том, как найти все делители числа. Начнем с доказательства теоремы, с помощью которой можно задать вид всех делителей определенного числа. Далее возьмем примеры нахождения всех нужных делителей и покажем, как именно определить, сколько делителей имеет конкретное число. В последнем пункте подробно рассмотрим примеры задач на нахождение общих делителей нескольких чисел.
Как найти все делители числа
Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 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 .
Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что 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 .
Чтобы узнать количество этих чисел, нужно выяснить, сколько положительных делителей имеет НОД.
Простые числа, составные числа
ОПРЕДЕЛЕНИЕ 1 . Простым числом называется натуральное число, отличное от 1 и такое, которое делится только на 1 и на самого себя.
Поскольку на 1 и на самого себя делится любое натуральное число, то из этого определения вытекает, что у простого числа других делителей нет.
ОПРЕДЕЛЕНИЕ 2 . Составным числом называется натуральное число, отличное от 1 и не являющееся простым.
Следовательно, у составного числа существует, по крайней мере, один делитель, отличный от 1 и самого числа.
ОПРЕДЕЛЕНИЕ 3 . Делители составного числа, отличные от 1 и самого числа, называют множителями.
Например, числа 2 , 3 , 5 , 7 , 11 , 13 , 17 и т.д. являются простыми. Числа 4 , 6 , 8 , 9 , 10 , 12 и т.д. являются составными.
ЗАДАЧА . Доказать, что полусумма двух последовательных простых чисел, больших 2 , является составным числом.
РЕШЕНИЕ . Поскольку все простые числа большие 2 являются нечетными числами, то их сумма будет четным числом, а полусумма — натуральным числом.
Это натуральное число будет больше, чем меньшее из заданных последовательных простых чисел, и меньше, чем большее из них.
Так как заданные простые числа являются последовательными простыми числами, то между ними не может быть других простых чисел, а, значит, их полусумма является составным числом.
ЗАМЕЧАНИЕ . Чтобы выяснить, является ли данное число a простым или составным, достаточно проверить, делится ли это число на простые числа, не превосходящие числа .
Разложение натуральных чисел на множители (каноническое разложение натуральных чисел)
ТЕОРЕМА . Любое натуральное число, отличное от 1 , можно представить в виде произведения множителей, являющихся простыми числами, причем единственным образом.
Иногда эту теорему формулируют так: любое натуральное число, отличное от 1 , можно единственным образом разложить на простые множители.
ПРИМЕР . Разложить на множители число 816 .
и есть единственное разложение числа 816 на простые множители. Простыми множителями в данном примере являются числа 2 , 3 и 17 .
Бесконечность множества простых чисел
ТЕОРЕМА . Множество простых чисел бесконечно.
ДОКАЗАТЕЛЬСТВО . Будем доказывать эту теорему от противного, предположив, что множество простых чисел конечно.
Тогда рассмотрим число, равное произведению всех простых чисел плюс 1 . Это число не делится ни на одно из простых чисел, поэтому его разложение на простые множители с одной стороны должно существовать, а с другой стороны не может содержать ни одного из множителей, являющихся простым числом.
Полученное противоречие доказывает, множество простых чисел должно быть бесконечным.
ЗАМЕЧАНИЕ. В нашем справочнике приведена таблица простых чисел от 1 до 10000 .