Какие числа называют простыми. Простые числа. Составные числа
простое число
натуральное число, большее, чем единица, и не имеющее других делителей, кроме самого себя и единицы: 2, 3, 5, 7, 11, 13... Число простых чисел бесконечно.
Простое число
целое положительное число, большее, чем единица, не имеющее других делителей, кроме самого себя и единицы: 2, 3, 5, 7, 11, 13,... Понятие П. ч. является основным при изучении делимости натуральных (целых положительных) чисел; именно, основная теорема теории делимости устанавливает, что всякое целое положительное число, кроме 1, единственным образом разлагается в произведении П. ч. (порядок сомножителей при этом не принимается во внимание). П. ч. бесконечно много (это предложение было известно ещё древнегреческим математикам, его доказательство имеется в 9-й книге «Начал» Евклида). Вопросы делимости натуральных чисел, а следовательно, вопросы, связанные с П. ч., имеют важное значение при изучении групп; в частности, строение группы с конечным числом элементов тесно связано с тем, каким образом это число элементов (порядок группы) разлагается на простые множители. В теории алгебраических чисел рассматриваются вопросы делимости целых алгебраических чисел; понятия П. ч. оказалось недостаточным для построения теории делимости ≈ это привело к созданию понятия идеала. П. Г. Л. Дирихле в 1837 установил, что в арифметической прогрессии а + bx при х = 1, 2,... с целыми взаимно простыми а и b содержится бесконечно много П. ч. Выяснение распределения П. ч. в натуральном ряде чисел является весьма трудной задачей чисел теории. Она ставится как изучение асимптотического поведения функции p(х), обозначающей число П. ч., не превосходящих положительного числа х. Первые результаты в этом направлении принадлежат П. Л. Чебышеву, который в 1850 доказал, что имеются такие две такие постоянные а и А, что ═< p(x) < ═при любых x ³ 2 [т. е., что p(х) растет, как функция ]. Хронологически следующим значительным результатом, уточняющим теорему Чебышева, является т. н. асимптотический закон распределения П. ч. (Ж. Адамар, 1896, Ш. Ла Валле Пуссен, 1896), заключающийся в том, что предел отношения p(х) к ═равен
В дальнейшем значительные усилия математиков направлялись на уточнение асимптотического закона распределения П. ч. Вопросы распределения П. ч. изучаются и элементарными методами, и методами математического анализа. Особенно плодотворным является метод, основанный на использовании тождества
(произведение распространяется на все П. ч. р = 2, 3,...), впервые указанного Л. Эйлером; это тождество справедливо при всех комплексных s с вещественной частью, большей единицы. На основании этого тождества вопросы распределения П. ч. приводятся к изучению специальной функции ≈ дзета-функции x(s), определяемой при Res > 1 рядом
Эта функция использовалась в вопросах распределения П. ч. при вещественных s Чебышевым; Б. Риман указал на важность изучения x(s) при комплексных значениях s. Риман высказал гипотезу о том, что все корни уравнения x(s) = 0, лежащие в правой полуплоскости, имеют вещественную часть, равную 1/
Эта гипотеза до настоящего времени (1975) не доказана; её доказательство дало бы весьма много в решении вопроса о распределении П. ч. Вопросы распределения П. ч. тесно связаны с Гольдбаха проблемой, с не решенной ещё проблемой «близнецов» и другими проблемами аналитической теории чисел. Проблема «близнецов» состоит в том, чтобы узнать, конечно или бесконечно число П. ч., разнящихся на 2 (таких, например, как 11 и 13). Таблицы П. ч., лежащих в пределах первых 11 млн. натуральных чисел, показывают наличие весьма больших «близнецов» (например, 10006427 и 10006429), однако это не является доказательством бесконечности их числа. За пределами составленных таблиц известны отдельные П. ч., допускающие простое арифметическое выражение [например, установлено (1965), что 211213 ≈1 есть П. ч.; в нём 3376 цифр].
Лит.: Виноградов И. М., Основы теории чисел, 8 изд., М., 1972; Хассе Г., Лекции по теории чисел, пер. с нем., М., 1953; Ингам А. Е., Распределение простых чисел, пер. с англ., М. ≈ Л., 1936; Прахар К., Распределение простых чисел, пер. с нем., М., 1967; Трост Э., Простые числа, пер, с нем., М., 1959.
Википедия
Простое число
Просто́е число́ - натуральное число, имеющее ровно два различных натуральных делителя - и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x . К примеру, 5 - простое число, а 6 является составным числом, так как, помимо 1 и 6, также делится на 2 и на 3.
Натуральные числа, которые больше единицы и не являются простыми, называются составными. Таким образом, все натуральные числа разбиваются на три класса: единицу. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.
Последовательность простых чисел начинается так:
2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 …
Определение 1. Простое число − это натуральное число больше единицы, которое делится только на себя и на 1.
Другими словами число является простым, если имеет только два различных натуральных делителя.
Определение 2. Любое натуральное число, которое кроме самого себя и единицы имеет и других делителей, называется составным числом.
Другими словами натуральные числа, не являющиеся простыми числами, называются составными. Из определения 1 следует, что составное число имеет больше двух натуральных делителей. Число 1 не является ни простым, ни составным т.к. имеет только один делитель 1 и, кроме этого многие теоремы относительно простых чисел не имеют места для единицы.
Из определений 1 и 2 следует, что каждое целое положительное число больше 1 является либо простым, либо составным числом.
Ниже представлена программа для отображения простых чисел до 5000. Заполните ячейки, нажмите на кнопку "Создать" и подождите несколько секунд.
Таблица простых чисел
Утверждение 1. Если p - простое число и a любое целое число, то либо a делится на p , либо p и a взаимно простые числа.
Действительно. Если p простое число, то оно делится только на себя и на 1, если a не делится на p , то наибольший общий делитель a и p равен 1. Тогда p и a взаимно простые числа.
Утверждение 2. Если произведение нескольких чисел чисел a 1 , a 2 , a 3 , ... делится на простое число p , то по крайней мере одно из чисел a 1 , a 2 , a 3 , ... делится на p .
Действительно. Если бы ни одно из чисел не делилось на p , то числа a 1 , a 2 , a 3 , ... были бы взаимно простые числа по отношению p . Но из следствия 3 () следует, что их произведение a 1 , a 2 , a 3 , ... также взаимно простое по отношению к p , что противоречит условию утверждения. Следовательно по крайней мере один из чисел делится на p .
Теорема 1. Любое составное число всегда может быть представлено и притом единственным способом в виде произведения конечного числа простых чисел.
Доказательство. Пусть k составное число, и пусть a 1 один из его делителей отличное от 1 и самого себя. Если a 1 составное, то имеет кроме 1 и a 1 и другой делитель a 2 . Если a 2 число составное, то имеет кроме 1 и a 2 и другой делитель a 3 . Рассуждая таким образом и учитывая, что числа a 1 , a 2 , a 3 , ... убывают и этот ряд содержит конечное число членов, мы дойдем какого-то простого числа p 1 . Тогда k можно представить в виде
Допустим существует два разложения числа k :
Так как k=p 1 p 2 p 3 ... делится на простое число q 1 , то по крайней мере один из множителей, например p 1 делится на q 1 . Но p 1 простое число и делится только на 1 и на себя. Следовательно p 1 =q 1 (т.к. q 1 ≠1)
Тогда из (2) можно исключить p 1 и q 1:
Таким образом убеждаемся, что всякое простое число входящее множителем в первое разложение один или несколько раз, входит и во второе разложение минимум столько же раз и наоборот, всякое простое число, которое входит множителем во второе разложение один или несколько раз входит и в первое разложение минимум столько же раз. Следовательно любое простое число входит множителем в оба разложения одинаковое число раз и, таким образом, эти два разложения одинаковы.■
Разложение составного числа k можно записать в следующем виде
| (3) |
где p 1 , p 2 , ... различные простые числа, α, β, γ ... целые положительные числа.
Разложение (3) называется каноническим разложением числа.
Простые числа в ряду натуральных чисел встречаются неравномерно. В одних частях ряда их больше, в других - меньше. Чем дальше мы продвигаемся по числовому ряду, тем реже встречаются простые числа. Возникает вопрос, существует ли самое большое простое число? Древнегреческий математик Евклид доказал, что простых чисел бесконечно много. Ниже мы представим это доказательство.
Теорема 2. Количество простых чисел бесконечно много.
Доказательство. Предположим, что существует конечное число простых чисел, и пусть наибольшее простое число равно p . Рассмотрим все числа больше p . По предположению утверждения эти числа должны быть составными и должны делится по крайней мере на один из простых чисел. Выберем число, являющиеся произведением всех этих простых чисел плюс 1:
Число z больше p так как 2p уже больше p . p не делится ни на одно из этих простых чисел, т.к. при делении на каждое из них дает остаток 1. Таким образом мы приходим к противоречию. Следовательно существует бесчисленное множество простых чисел.
Данная теорема является частным случаем более общей теоремы:
Теорема 3. Пусть задана арифметическая прогрессия
Тогда любое простое число, входящее в n , должно входить и в m , поэтому в n не могут входить другие простые множители, которые не входят в m и притом эти простые множители в n входят не более число раз, чем в m .
Справедливо и обратное. Если каждый простой множитель числа n входит по крайней мере столько же раз в число m , то m делится на n .
Утверждение 3. Пусть a 1 ,a 2 ,a 3 ,... различные простые числа входящие в m так, что
где i =0,1,...α , j =0,1,...,β , k=0,1,...,γ . Заметим, что α i принимает α +1 значений, β j принимает β +1 значений, γ k принимает γ +1 значений, ... .
В этой статье мы изучим простые и составные числа . Сначала дадим определения простых и составных чисел, а также приведем примеры. После этого докажем, что простых чисел бесконечно много. Далее запишем таблицу простых чисел, и рассмотрим методы составления таблицы простых чисел, особо тщательно остановимся на способе, получившем название решето Эратосфена. В заключение осветим основные моменты, которые нужно учитывать при доказательстве того, что данное число является простым или составным.
Навигация по странице.
Простые и составные числа – определения и примеры
Понятия простые числа и составные числа относятся к , которые больше единицы. Такие целые числа, в зависимости от количества их положительных делителей, подразделяются на простые и составные числа. Таким образом, чтобы понять определения простых и составных чисел , нужно хорошо представлять себе, что такое делители и кратные .
Определение.
Простые числа – это целые числа, большие единицы, которые имеют только два положительных делителя, а именно самих себя и 1 .
Определение.
Составные числа – это целые числа, большие единицы, которое имеют, по крайней мере, три положительных делителя.
Отдельно заметим, что число 1 не относится ни к простым, ни к составным числам. Единица имеет только один положительный делитель, которым является само число 1 . Этим число 1 отличается от всех остальных целых положительных чисел, которые имеют не менее двух положительных делителей.
Учитывая, что целые положительные числа – это , и что единица имеет только один положительный делитель, можно привести другие формулировки озвученных определений простых и составных чисел.
Определение.
Простыми числами называют натуральные числа, которые имеют только два положительных делителя.
Определение.
Составными числами называют натуральные числа, имеющие более двух положительных делителей.
Отметим, что каждое целое положительное число, большее единицы, есть либо простое, либо составное число. Иными словами, не существует ни одного такого целого числа, которое не являлось бы ни простым, ни составным. Это следует из свойства делимости , которое гласит, что числа 1 и a всегда являются делителями любого целого числа a .
Исходя из информации предыдущего абзаца, можно дать следующее определение составных чисел.
Определение.
Натуральные числа, которые не являются простыми, называются составными .
Приведем примеры простых и составных чисел .
В качестве примеров составных чисел приведем 6 , 63 , 121 и 6 697 . Это утверждение тоже нуждается в пояснении. Число 6 имеет кроме положительных делителей 1 и 6 еще и делители 2 и 3 , так как 6=2·3 , поэтому 6 – действительно составное число. Положительными делителями 63 являются числа 1 , 3 , 7 , 9 , 21 и 63 . Число 121 равно произведению 11·11 , поэтому его положительными делителями являются 1 , 11 и 121 . А число 6 697 составное, так как его положительными делителями кроме 1 и 6 697 являются еще и числа 37 и 181 .
В заключение этого пункта хочется еще обратить внимание на то, что простые числа и взаимно простые числа – это далеко ни одно и то же.
Таблица простых чисел
Простые числа, для удобства их дальнейшего использования, записывают в таблицу, которую называют таблицей простых чисел. Ниже представлена таблица простых чисел до 1 000 .
Возникает логичный вопрос: «Почему мы заполнили таблицу простых чисел только до 1 000 , разве нельзя составить таблицу всех существующих простых чисел»?
Ответим сначала на первую часть этого вопроса. Для большинства задач, при решении которых придется использовать простые числа, нам будет вполне достаточно простых чисел в пределах тысячи. В остальных случаях, скорее всего, придется прибегать к каким-либо специальным приемам решения. Хотя, несомненно, мы можем составить таблицу простых чисел до сколь угодно большого конечного целого положительного числа, будь то 10 000 или 1 000 000 000 , в следующем пункте мы поговорим о методах составления таблиц простых чисел, в частности, разберем способ, получивший название .
Теперь разберемся с возможностью (а точнее с невозможностью) составления таблицы всех существующих простых чисел. Мы не можем составить таблицу всех простых чисел, потому что простых чисел бесконечно много. Последнее утверждение представляет собой теорему, которую мы докажем после следующей вспомогательной теоремы.
Теорема.
Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.
Доказательство.
Пусть a – натуральное число, большее единицы, и b – наименьший положительный и отличный от единицы делитель числа a . Докажем, что b – простое число методом от противного.
Предположим, что b – составное число. Тогда существует делитель числа b (обозначим его b 1 ), который отличен как от 1 , так и от b . Если также учесть, что абсолютная величина делителя не превосходит абсолютной величины делимого (это мы знаем из свойств делимости), то должно выполняться условие 1
Так как число a делится на b по условию, и мы сказали, что b делится на b 1 , то понятие делимости позволяет говорить о существовании таких целых чисел q и q 1 , что a=b·q и b=b 1 ·q 1 , откуда a= b 1 ·(q 1 ·q) . Из следует, что произведение двух целых чисел есть целое число, тогда равенство a=b 1 ·(q 1 ·q) указывает на то, что b 1 является делителем числа a . Учитывая полученные выше неравенства 1
Теперь мы можем доказать, что простых чисел бесконечно много.
Теорема.
Простых чисел бесконечно много.
Доказательство.
Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p 1 , p 2 , …, p n . Покажем, что мы всегда можем найти простое число, отличное от указанных.
Рассмотрим число, p равное p 1 ·p 2 ·…·p n +1 . Понятно, что это число отлично от каждого из простых чисел p 1 , p 2 , …, p n . Если число p - простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его p n+1 ). Покажем, что этот делитель не совпадает ни с одним из чисел p 1 , p 2 , …, p n .
Если бы это было не так, то по свойствам делимости произведение p 1 ·p 2 ·…·p n делилось бы на p n+1 . Но на p n+1 делится и число p , равное сумме p 1 ·p 2 ·…·p n +1 . Отсюда следует, что на p n+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.
Так доказано, что всегда может быть найдено новое простое число, не заключающееся среди любого количества наперед заданных простых чисел. Следовательно, простых чисел бесконечно много.
Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.
Решето Эратосфена
Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .
Самым очевидным методом решения этой задачи является последовательная проверка целых положительных чисел, начиная с 2 , и заканчивая 100 , на наличие положительного делителя, который больше 1 и меньше проверяемого числа (из свойств делимости мы знаем, что абсолютная величина делителя не превосходит абсолютной величины делимого, отличного от нуля). Если такой делитель не найден, то проверяемое число является простым, и оно заносится в таблицу простых чисел. Если же такой делитель найден, то проверяемое число является составным, оно НЕ заносится в таблицу простых чисел. После этого происходит переход к следующему числу, которое аналогично проверяется на наличие делителя.
Опишем несколько первых шагов.
Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .
Такой подход к составлению таблицы простых чисел является далеко не идеальным. Так или иначе, он имеет право на существование. Отметим, что при этом способе построения таблицы целых чисел можно использовать признаки делимости , которые немного ускорят процесс поиска делителей.
Существует более удобный способ для составления таблицы простых чисел, называемый . Присутствующее в названии слово «решето» не случайно, так как действия этого метода помогают как бы «просеять» сквозь решето Эратосфена целые числа, большие единицы, чтобы отделить простые от составных.
Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .
Сначала записываем по порядку числа 2, 3, 4, …, 50 .
Первое записанное число 2 является простым. Теперь от числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти числа, пока не доберемся до конца составляемой таблицы чисел. Так будут вычеркнуты все числа, кратные двум.
Первым следующим за 2 невычеркнутым числом является 3 . Это число простое. Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные трем.
Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.
Дальше вычеркиваем числа, кратные 7 , затем, кратные 11 и так далее. Процесс заканчивается, когда не останется чисел для вычеркивания. Ниже показана законченная таблица простых чисел до 50 , полученная с помощью решета Эратосфена. Все незачеркнутые числа являются простыми, а все зачеркнутые числа – составными.
Давайте еще сформулируем и докажем теорему, которая позволит ускорить процесс составления таблицы простых чисел при помощи решета Эратосфена.
Теорема.
Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где - из a .
Доказательство.
Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать ), получаем , откуда и .
Что же нам дает доказанная теорема, касательно решета Эратосфена?
Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.
Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .
Данное число простое или составное?
Некоторые задания требуют выяснения, является ли данное число простым или составным. В общем случае эта задача далеко не проста, особенно для чисел, запись которых состоит из значительного количества знаков. В большинстве случаев приходится искать какой-либо специфический способ ее решения. Однако мы попробуем дать направление ходу мыслей для несложных случаев.
Несомненно, можно попробовать воспользоваться признаками делимости для доказательства того, что данное число является составным. Если, к примеру, некоторый признак делимости показывает, что данное число делится на некоторое целое положительное число большее единицы, то исходное число является составным.
Пример.
Докажите, что число 898 989 898 989 898 989 составное.
Решение.
Сумма цифр данного числа равна 9·8+9·9=9·17 . Так как число, равное 9·17 делится на 9 , то по признаку делимости на 9 можно утверждать, что исходное число также делится на 9 . Следовательно, оно составное.
Существенный недостаток такого подхода заключается в том, что признаки делимости не позволяют доказать простоту числа. Поэтому при проверке числа на то, является ли оно простым или составным, нужно действовать иначе.
Самый логичный подход состоит в переборе всех возможных делителей данного числа. Если ни один из возможных делителей не будет истинным делителем данного числа, то это число будет простым, в противном случае – составным. Из теорем, доказанных в предыдущем пункте, следует, что делители данного числа a нужно искать среди простых чисел, не превосходящих . Таким образом, данное число a можно последовательно делить на простые числа (которые удобно брать из таблицы простых чисел), пытаясь найти делитель числа a . Если будет найден делитель, то число a – составное. Если же среди простых чисел, не превосходящих , не окажется делителя числа a , то число a – простое.
Пример.
Число 11 723 простое или составное?
Решение.
Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .
Достаточно очевидно, что 
, так как 200 2 =40 000
, а 11 723<40 000
(при необходимости смотрите статью сравнение чисел
). Таким образом, возможные простые делители числа 11 723
меньше числа 200
. Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200
, а вплоть до числа 11 723
.
При желании можно оценить более точно. Так как 108 2 =11 664
, а 109 2 =11 881
, то 108 2 <11 723<109 2
, следовательно, 
. Таким образом, любое из простых чисел, меньших 109
, потенциально является простым делителем данного числа 11 723
.
Теперь мы будем последовательно делить число 11 723 на простые числа 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.
Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723
Все остальные натуральные числа называются составными . Натуральное число 1 не является ни простым, ни составным.
Пример
Задание. Какие из записанных ниже натуральных чисел являются простыми:
Ответ.
Разложение числа на множители
Представление натурального числа в виде произведения натуральных чисел называется разложением на множители . Если в разложении на множители натурального числа все множители простые числа, то такое разложение называется разложением на простые множители .
Теорема
(Основная теорема арифметики)
Каждое натуральное число, отличное от 1, может быть разложено на простые множители, и притом единственным образом (если отождествлять разложения и , где и - простые числа).
Объединяя в разложении числа одинаковые простые сомножители, получаем так называемое каноническое разложение числа :
где , - различные простые числа, а - натуральные числа.
Пример
Задание. Найти каноническое разложение чисел:
Решение. Для нахождения канонического разложения чисел нужно сначала разложить их на простые множители, а затем объединить одинаковые множители и записать их произведение в виде степени с натуральным показателем:
Ответ.
Историческая справка
Как определить, какое число простое, а какое нет? Наиболее распространенным методом позволяющим найти все простые числа в любом числовом отрезке, предложил в III в. до н. э. Эратосфен (метод называется "решето Эратосфена"). Предположим, что нам нужно установить, какие из чисел являются простыми. Выпишем их в ряд и вычеркнем каждое второе число из следующих за числом 2 - все они составные, так как кратны числу 2. Первое из оставшихся невычеркнутых чисел - 3 - является простым. Вычеркнем каждое третье число из следующих за числом 3; следующее из невычеркнутых чисел - 5 - также будет простым. По тому же принципу вычеркнем каждое пятое число из следующих за числом 5 и вообще каждое -е из следующих за числом . Все оставшиеся невычеркнутыми числа будут простыми.
С увеличением простые числа постепенно встречаются все реже и реже. Однако уже древним был хорошо известен тот факт, что их бесконечно много. Его доказательство приводится в "Началах" Евклида.
