Число которое не делится на само себя. Как проверить, является ли число простым. Основная теорема арифметики

Лекция1.

Вероятность

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

Элементарным событием (элементарным исходом) называется любое событие - исход опыта, которое нельзя представить в виде объединения других событий. Так как исход опыта случаен, то и любое элементарное событие случайно, далее будем говорить просто о событиях, не подчеркивая их случайность.

Пространством элементарных событий W (исходов) называется множество всех элементарных событий (исходов). {w 1 , …w n … }, если в результате опыта обязательно наступает какой-либо из элементарных исходов и только один (один исход исключает любой другой). Пространство элементарных событий может содержать конечное, счетное и даже бесконечное множество элементарных событий.

Случайным событием (событием) называется подмножество пространства элементарных событий. Любое множество – это совокупность элементов. Элементами события являются элементарные события, образующие это событие.

Пример . Бросается одна монета, она может упасть гербом (w 1 =Г) или решкой (w 1 =Р). W=(Г,Р).

Пример. Бросаются две монеты W = {(Г, Г), (Г,Р), (Р,Г), (Р,Р)}

Пример . Капля дождя падает на прямоугольную площадку.

W= {(x,y), a

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

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

Действия над событиями.

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

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

Пусть выбираются карты из колоды карт. Событие А – выбор червонной карты, событие В – выбор десятки

Суммой двух событий А и В называется событие

С = А + В (или С = А В ), состоящее из элементарных событий, принадлежащих либо А , либо В .

Пример .

С = А + В – выбор любой червонной карты или любой десятки

Произведением двух событий А и В называется событие D = AB (или D = A B ), состоящее из элементарных событий, принадлежащих и А и В .

Пример . АВ – выбор десятки червей

Разностью двух событий А и В называется событие

АВ , состоящее из элементарных событий, принадлежащих А и не принадлежащих В .

Пример . АВ –выбор любой червонной карты, кроме десятки

Классификация событий

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

Пример. А –выбор червонной карты;

–выбор любой карты другой масти.. = W А

Два события А и В будем называть совместными , если каждое из них содержит хотя бы одно общее элементарное событие, т.е если АВ Ø.

Пример . А – выбор червонной карты и

В – выбор десятки – совместные события, так как

АВ = выбор червонной десяткиØ

Если общих элементарных событий у событий А и В нет, то их будем называть несовместными событиями

(АВ = Ø).

Пример . А – выпадение четного числа очков А = {2, 4, 6}.

В – выпадение нечетного числа очков В = {1, 3, 5}

Очевидно, что А и В несовместны.

Полная группа событий – это совокупность n событий А 1 , А 2 , …, А n , одно из которых обязательно произойдет, т.е.

Свойства операций над событиями

1. = Ø 6. А = А

2. А + А = А 7. А Ø = Ø Коротко . Если А В , то

3. А А = А 8 = АА + В = В

4. А + = 9. А В = А

5. А + Ø = А 10. = Ø

Коммутативность операций

А + В = В + А; А В = В А

Ассоциативность операций

А + (В + С) = (А + В) + С = А + В + С А(В С) = (А В) С = А В С

Дистрибутивность операции сложения относительно умножения

А (В + С) = А В + А С

Дистрибутивность операции умножения относительно сложения

А + (В С) = (А + В)(А + С)

Пример. Вычислим (A+B)(A+C)=AA+BA+AC+BC=A+BC.

В самом деле, BAÌA, ACÌA, AA=A, тогда AA+BA=A, A+AC=A.

Правило двойственности (теорема де Моргана)

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

Пример .

Алгебра событий.

Пусть W - пространство элементарных событий. Алгеброй событий S называется такая система случайных событий S, что

1) SÉW, 2) " A, B Ì S Þ A+BÌS, ABÌS, ABÌS.

Следствие Æ= WW Ì S

Пусть W содержит конечное число элементов, W= {w 1 ,…w n }. Тогда алгебру S можно построить как множество всех подмножеств W.

S={Æ, {w 1 }, … {w n }, {w 1 ,w 2 }, …{w 1 ,w n }, …{w n -1 ,w n }, …{w 1, …, w n }}, в ней всего 2 n элементов

Аналогично стоится алгебра для счетного числа событий.

Если в результате опыта стало известно, произошли или нет события A, B, то можно заключить, произошли или нет события , A+B, AB, AB, поэтому события должны выбираться из определенного класса – алгебры событий.

Для бесконечного (не счетного) числа событий класс событий должен быть сужен. Вводится s- алгебра событий.

Сигма-алгеброй (s -алгеброй) событий B называется непустая система подмножеств пространства элементарных событий, такая что

2) A 1 , A 2 , …A n , …ÌBÞ(A 1 +A 2 + …+A n +, …)ÌB, …ÌB.

Любая сигма-алгебра событий является алгеброй событий, но не наоборот.

Вероятность.

Классическое определение вероятности события

В классическом определении вероятности исходят из того, что пространство элементарных событий Ω содержит конечное число элементарных исходов, причем все они равновозможные.

Случаями называются равновозможные, несовместные события, составляющие полную группу.

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

Пусть N – общее число случаев в Ω , а N А – число случаев, образующих событие А (или, как говорят, благоприятствующих событию А ).

Определение . Вероятностью события А называется отношение числаN A случаев, благоприятствующих событию А к общему числу N случаев, т.е. P (A ) = . Данное определение вероятности события принято называть классическим определением вероятности .

Примеры . 1. Бросание игральной кости. Ω = {w 1 , w 2 ,…, w 6 } N = 6.

А – количество очков кратно трем А = {w 3 , w 6 } N A = 2.

2. Бросание 2-х игральных костей. Ω = {w 11 , w 12 ,…, w 66 }; N =36.

w kl = (a k , b l ), k , l =

А – сумма цифр (очков) равна 5. А = {(1,4), (2,3), (3,2), (4,1)}; N A = 4

.

3. В урне а белых и b черных шаров. Опыт – вынимается один шар.

А – шар черный.

Исходя из классического определения вероятностей, легко доказать свойства вероятности:

1) Р(Ω ) = 1 (N A = N );

3) Если А В = Ø, то Р(А + В) = Р(А) + Р(В) ( N A + B = N A + N B )

и их следствия

4) Р (Ø) = 0 (N Ø) = 0;

5) Р() = 1- Р(А) ( = Ø, Р(А) + Р( ) = 1);

6) Если , то Р(А) Р(В) (N A N B ).

При практическом применении формулы классической вероятности наиболее сложным является определение общего числа равновозможных исходов и числа благоприятствующих исходов.

Здесь используется основной принцип комбинаторики: пусть некоторая операция Р представляет собой последовательность n операций P k (k=1, …n), каждая из которых может быть выполнена m r способами. Тогда операция Р может быть выполнена способами.

Пусть мы делаем выборку поочередно m элементов (например, шаров) из n элементов. Мы можем возвращать очередной шар (в число n шаров), тогда при каждом очередном выборе мы будем иметь все те же n шаров. Такая выборка называется выборкой с возвращением . А можем и не возвращать шар, тогда при каждом выборе мы будем выбирать из все меньшего числа шаров. Такая выборка называется выборкой без возвращения. С другой стороны, мы можем учитывать порядок появления шаров. Такая выборка называется упорядоченной или размещением из n шаров по m шаров. Если порядок шаров при выборе не учитывается, важно лишь, какие шары выбраны, но не важно, в каком порядке, то такая выборка называется неупорядоченной или сочетанием из n шаров по m шаров. Выясним, сколькими способами можнопроизвести ту или иную выборку

Сочетания

Размещения

Без возвращения

С возвращением

Формулы для размещений легко получаются из принципа комбинаторики. Для того, чтобы перейти от размещений (без возвращений) к сочетаниям (без возвращений), нужно упорядочить выборки, т.е. исключить те из них, которые отличаются только порядком элементов. Выборки, отличающиеся только порядком элементов, называются перестановками . Число перестановок из m элементов равно P m ==m!. Поэтому .

Формулу для сочетаний с возвращением примем без доказательства (ее доказательство приведено в вып. ХV1 на стр. 50 – 51).

Пример . Производится выборка двух шаров (m=2) из урны, в которой находится 3 шара (n=3). Приведем эти выборки.

1) Размещения с возвращением

(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) = 3 2 = 9.

2) Размещения (без возвращения) (1,2) (1,3) (2,1) (2,3) (3,1) (3,2) .

3) Сочетания с возвращением (1,1) (1,2) (1,3) (2,2) (2,3) (3,3)

4) Сочетания (без возвращения) (1,2) (1,3) (2,3) .

Пример . Задача о выборке бракованных деталей .

В партии из N одинаковых деталей M бракованных. Выбирается (не возвращая) n деталей. Какова вероятность того, что среди них окажется ровно m бракованных?

Общее количество случаев (сочетания из N деталей по n) равно . Мы выбираем m бракованных деталей среди M бракованных, но и одновременно выбираем (n-m) деталей без брака среди N-M деталей без брака. Тогда, по основному принципу комбинаторики, такому выбору благоприятствует случаев. Поэтому искомая вероятность равна .

Геометрическая вероятность

Формула классической вероятности применяется только в схеме случаев, что встречается довольно редко. Отношение Р(А)= N A / N представляет собой «долю» благоприятных исходов среди всех возможных исходов. Аналогичным образом подсчитывают вероятность события в некоторых более сложных случаях, когда имеется бесконечное число равновозможных исходов.

Событие А – волчок касается плоскости точкой из окрашенного сектора.

Множество точек на ободе в окрашенном секторе имеет мощность континуума. Делим всю окружность на N маленьких одинаковых дуг. Число дуг на окружности, принадлежащих окрашенному сектору, пусть равно N A .

.

В общем случае имеется мера mes соответствующая (в нашем случае mes = 2) и мера mes А, соответствующая А (в нашем случае mes А = )

и т.д.

Пример. Задача о встрече. Два студента договорились встретиться от 10 до 11 часов на определенном месте, причем первый пришедший на место ждет товарища 15 минут и уходит. Какова вероятность встречи?

Выберем начало системы координат в точке (10, 10). Отложим по осям системы координат x- время прихода первого студента, y – время прихода второго студента.

Тогда множество |x-y|<1/4, 0

содержит точки (события) встречи студентов. Его мера (площадь) mesA равна 1- (3/4) 2 = 7/16. Так как mesW =1, то P(A) = 7/16.

Статистическая вероятность

Формулы классической вероятности и геометрической вероятности справедливы только для случая равновозможных исходов. В действительности мы на практике имеем место с неравновозможными исходами. В этих случаях можно определить вероятность случайного события, используя понятие частоты события . Допустим, что нам требуется определить вероятность того, что в испытании произойдет событие А . Для этого в одинаковых условиях проводятся испытания, в каждом из которых возможны два исхода: А и . Частотой события А будем называть отношение числа N A испытаний, в которых зафиксировано событие А к общему числу N испытаний.

Вероятностью события А называется предел частоты события А при неограниченном увеличении числа испытаний n , т.е. . Так определяется статистическая вероятность события .

Заметим, что по классическому, геометрическому и статистическому определениям для вероятности события P(A) выполнены три основных свойства:

P(A)³0, 2) P(W)=1, 3) P(A 1 + …+A n) = P(A 1) + …+P(A n), если A 1 , A n попарно несовместны. Однако в этих определениях элементарные события предполагаются равновозможными.

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

Аксиоматическое определение вероятности (по А.Н.Колмогорову).

Вероятностью P(A) называется числовая функция, заданная на сигма – алгебре событий, удовлетворяющая трем аксиомам:

1) не отрицательность P(A)³0, "AÎB - сигма – алгебре событий на W

2) нормировка P(W) = 1

3) расширенная аксиома сложения: для любых попарно несовместных событий A 1 , … A n … выполнено

P(A 1 + …+A n + …) = P(A 1) + …+P(A n) +…

(счетная аддитивность).

Итак, по А.Н. Колмогорову вероятность (вероятностная мера) это числовая неотрицательная нормированная счетно - аддитивная функция (множества – события), заданная на сигма – алгебре событий.

Если W состоит из конечного или счетного числа событий, то в качестве сигма – алгебры B может рассматриваться алгебра S событий. Тогда по аксиоме 3 вероятность любого события A равна сумме вероятностей элементарных событий, составляющих A.

Вероятностным пространством называется тройка (W, B, P).

Свойства вероятности

1) . В самом деле,, несовместны. По аксиоме 3 .

2) P(Æ) = 0. Так как "A A+Æ = A, по аксиоме 3 P(A+Æ) = P(A) + P(Æ) = P(A) ÞP(Æ) = 0

3) Если AÌ B, то P(A) £ P(B). Так как B = A+ BA, по аксиоме 3 P(B) = P(A) + P(BA), но по аксиоме 1 P(BA)³0

Пример . Из урны с четырьмя шарами с номерами 1, 2, 3, 4 три раза наугад вынимают шар и записывают его номер а) возвращая шары б) не возвращая шары. Какова вероятность 1) получить комбинацию 111, 2) из номеров шаров составить возрастающую последовательность?

В случае а) имеем размещения с возвращением, N = 4 3 , 1), N A =1, P = ¼ 3 , 2) N A = , так как возрастающую последовательность можно составить всегда из не повторяющихся номеров, P = / 4 3 .

В случае б) N = ,1) P = 0, так как номера шаров не повторяются, то N A =0, 2) P = 1, так как N = N A = .

Пример . Пять человек садятся в поезд метро, состоящий из пяти вагонов. Какова вероятность того, что они окажутся в разных вагонах?

Общее число элементарных событий равно числу размещений с повторением из пяти элементов по пять N = 5 5 . Число элементарных событий, составляющих А, равно 5! Поэтому Р = 5!/ 5 5 .


Лекции 1,2 написаны по лекциям В.Ф. Панова с добавлением авторского материала и примеров

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

Задача 1. Куб все грани которого закрашены, распилен на 1000 кубиков одинаковых размеров. Определить вероятность того что кубик вытянутый наугад будет иметь:

  • а) одну закрашеную грань;
  • б) две закрашеные грани.

Вычисления: Если куб распилить на кубики одинакового размера то все грани будут поделены на 100 квадратов. (Примерно как на рисунке)
Дальше по условию кубик должен иметь одну закрашенную грань - это значит что кубики должны принадлежать внешней поверхности но не лежать на ребрах куба (2 закрашеные поверхности) и не на углах - имеют три закрашеные поверхности.
Следовательно, искомое количество равно произведению 6 граней на количество кубиков в квадрате размером 8*8.
6*8*8=384 – кубики с 1 закрашеной поверхностью.
Вероятность равна количеству благоприятных событий к общему их количеству P=384/1000=0,384.
б) Две закрашеные грани имеют кубики по ребрам без самих вершин куба. На одном ребре будет 8 таких кубиков. Всего в кубе 12 ребер, поэтому две закрашенные грани имеют
8*12=96 кубиков .
А вероятность вытянуть их среди 1000 всех равная
P=96/1000=0,096.
На этом задание решено и переходим к следующему.

Задача 2. На одинаковых карточках написаны буквы А, А, А, Н, Н, С . Какова вероятность того, что случайно разместив карточки в ряд, получим слово АНАНАС?
Вычисления: Нужно рассуждать всегда от того, что известно. Дано 3 буквы А, 2-Н, и 1 - С, всего их 6. Начнем выбирать буквы для слова "ананас" . Первой идет буква А, которую мы можем выбрать 3 способами из 6, потому что есть 3 буквы А среди 6 известных. Поэтому вероятность вытянуть первой А равна
P 1 =3/6=1/2.
Вторая буква Н, но не следует забывать, что после того как вытащили А остается 5 букв для выбора. Поэтому вероятность вытянуть под 2 номером Н равна
P 2 =2/5.
Следующую А вероятность вытянуть среди 4, что осталось
P 3 =2/4.
Далее Н можно извлечь из вероятностью
P 4 =1/3.
Чем ближе к концу тем больше вероятность, и уже А можем извлечь при
P 5 =1/2.
После этого остается одна карточка С, поэтому вероятность ее вытащить равна 100 процентам или
P 6 =1.
Вероятность составить слово АНАНАС равна произведению вероятностей
P=3/6*2/5*2/4*1/3*1/2*1=1/60=0,016(6).
На этом и базируются подобные задачи по теории вероятностей.

Задача 3. Из партии изделий товаровед наугад выбирает образцы. Вероятность того что наугад взятое изделие окажется высшего сорта равна 0,8. Найти вероятность того, что среди 3 отобранных изделий будет два изделия высшего сорта?
Вычисления: Данный пример на применение формулы Бернулли .
p=0,8; q=1-0,8=0,2.
Вероятность вычисляем по формуле

Если объяснять не на языке формул, то нужно составить комбинации из трех событий, два из которых благоприятны, а одно нет. Это можно записать суммой произведений

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

Задача 4. Из пяти стрелков двое попадают в цель с вероятностью 0,6 и трое с вероятностью 0,4 . Что вероятнее: наугад выбранный стрелок попадает в цель или нет?
Вычисления: По формуле полной вероятности определяем вероятность, что стрелок попадет.
P=2/5*0,6+3/5*0,4=0,24+0,24=0,48.
Вероятность меньше P<0,5 , следовательно вероятнее что наугад выбранный стрелок не попадет в цель.
Вероятность не попадания составляет

или
P=2/5*(1-0,6)+3/5*(1-0,4)=0,16+0,36=0,52.

Задача 5. C 20 студентов, пришедших на экзамен, 10 подготовлены отлично (знают все вопросы), 7 хорошо (знают по 35 вопросов), а 3 плохо (10 вопросов). В программе 40 вопросов. Наугад вызванный студент ответил на три вопроса билета. Какова вероятность того, что он подготовлен на

  • а) отлично;
  • б) плохо.

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

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

Вероятность, что студент принадлежит группе которая плохо подготовилась достаточно мала и равна 0,00216 .

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

Задача 6. Монету бросают 5 раз. Найти вероятность того что герб выпадет менее 3 раз?
Вычисления: Вероятность вытянуть герб или решку равносильна и равна 0,5. Менее 3 раз означает, что герб может выпасть либо 0, либо 1, либо 2 раза. "Или" всегда в вероятности в операциях сказывается добавлением.
Вероятности находим по формуле Бернулли

Поскольку p=q=0,5 , то вероятность равна

Вероятность равна 0,5 .

Задача 7. При штамповке металлических клемм получается в среднем 90% стандартных. Найти вероятность того что среди 900 клемм стандартными будут не менее 790 и не более 820 клемм.

Вычисления: Вычисления необходимо проводить

В статье рассматриваются понятия простых и составных чисел. Даются определения таких чисел с примерами. Приводим доказательство того, что количество простых чисел неограниченно и произведем запись в таблицу простых чисел при помощи метода Эратосфена. Будут приведены доказательства того, является ли число простым или составным.

Yandex.RTB R-A-339285-1

Простые и составные числа – определения и примеры

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

Определение 1

Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1 .

Определение 2

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

Единица не является ни простым ни составным числом. Она имеет только один положительный делитель, поэтому отличается от всех других положительных чисел. Все целые положительные числа называют натуральными, то есть используемые при счете.

Определение 3

Простые числа – это натуральные числа, имеющие только два положительных делителя.

Определение 4

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

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

Определение 5

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

Простые числа: 2 , 3 , 11 , 17 , 131 , 523 . Они делятся только сами на себя и на 1 . Составные числа: 6 , 63 , 121 , 6697 . То есть число 6 можно разложить на 2 и 3 , а 63 на 1 , 3 , 7 , 9 , 21 , 63 , а 121 на 11 , 11 , то есть его делители будут 1 , 11 , 121 . Число 6697 разложится на 37 и 181 . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.

Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000 , тогда следует задуматься об использовании решета Эратосфена.

Рассмотрим теорему, которая объясняет последнее утверждение.

Теорема 1

Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

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

Возьмем, что а является натуральным числом, которое больше 1 , b является наименьшим отличным от единицы делителем для числа а. Следует доказать, что b является простым числом при помощи метода противного.

Допустим, что b – составное число. Отсюда имеем, что есть делитель для b , который отличен от 1 как и от b . Такой делитель обозначается как b 1 . Необходимо, чтобы условие 1 < b 1 < b было выполнено.

Из условия видно, что а делится на b , b делится на b 1 , значит, понятие делимости выражается таким образом: a = b · q и b = b 1 · q 1 , откуда a = b 1 · (q 1 · q) , где q и q 1 являются целыми числами. По правилу умножения целых чисел имеем, что произведение целых чисел – целое число с равенством вида a = b 1 · (q 1 · q) . Видно, что b 1 – это делитель для числа а. Неравенство 1 < b 1 < b не соответствует, потому как получим, что b является наименьшим положительным и отличным от 1 делителем а.

Теорема 2

Простых чисел бесконечно много.

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

Предположительно возьмем конечное количество натуральных чисел n и обозначим как p 1 , p 2 , … , p n . Рассмотрим вариант нахождения простого числа, отличного от указанных.

Примем на рассмотрение число р, которое равняется p 1 , p 2 , … , p n + 1 . Оно не равняется каждому из чисел, соответствующих простым числам вида p 1 , p 2 , … , p n . Число р является простым. Тогда считается, что теорема доказана. Если оно составное, тогда нужно принять обозначение p n + 1 и показать несовпадение делителя ни с одним из p 1 , p 2 , … , p n .

Если это было бы не так, тогда, исходя из свойства делимости произведения p 1 , p 2 , … , p n , получим, что оно делилось бы на p n + 1 . Заметим, что на выражение p n + 1 делится число р равняется сумме p 1 , p 2 , … , p n + 1 . Получим, что на выражение p n + 1 должно делиться второе слагаемое этой суммы, которое равняется 1 , но это невозможно.

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

Так как простых чисел очень много, то таблицы ограничивают числами 100 , 1000 , 10000 и так далее.

При составлении таблицы простых чисел следует учитывать то, что для такой задачи необходима последовательная проверка чисел, начиная с 2 до 100 . При отсутствии делителя оно фиксируется в таблицу, если оно составное, то в таблицу не заносится.

Рассмотрим пошагово.

Если начать с числа 2 , то оно имеет только 2 делителя: 2 и 1, значит, его можно занести в таблицу. Также и с числом 3 . Число 4 является составным, следует разложить его еще на 2 и 2 . Число 5 является простым, значит, можно зафиксировать в таблице. Так выполнять вплоть до числа 100 .

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

Способ при помощи решета Эратосфена считают самым удобным. Рассмотрим на примере таблиц, приведенных ниже. Для начала записываются числа 2 , 3 , 4 , … , 50 .

Теперь необходимо зачеркнуть все числа, которые кратны 2 . Произвести последовательное зачеркивание. Получим таблицу вида:

Переходим к вычеркиванию чисел, кратных 5 . Получим:

Вычеркиваем числа, кратные 7 , 11 . В конечном итоге таблица получает вид

Перейдем к формулировке теоремы.

Теорема 3

Наименьший положительный и отличный от 1 делитель основного числа а не превосходит a , где a является арифметическим корнем заданного числа.

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

Необходимо обозначить b наименьший делитель составного числа а. Существует такое целое число q , где a = b · q , причем имеем, что b ≤ q . Недопустимо неравенство вида b > q , так как происходит нарушение условия. Обе части неравенства b ≤ q следует умножить на любое положительное число b , не равное 1 . Получаем, что b · b ≤ b · q , где b 2 ≤ a и b ≤ a .

Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа, которое равняется b 2 и удовлетворяет неравенству b 2 ≤ a . То есть, если вычеркнуть числа, кратные 2 , то процесс начинается с 4 , а кратных 3 – с 9 и так далее до 100 .

Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят n . В примере, где n = 50 , у нас имеется, что n = 50 . Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из 50 . Поиск чисел производится при помощи вычеркивания.

Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.

Пример 1

Доказать что число 898989898989898989 является составным.

Решение

Сумма цифр заданного числа равняется 9 · 8 + 9 · 9 = 9 · 17 . Значит, число 9 · 17 делится на 9 , исходя из признака делимости на 9 . Отсюда следует, что оно составное.

Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.

Пример 2

Определить составное или простое число 11723 .

Решение

Теперь необходимо найти все делители для числа 11723 . Необходимо оценить 11723 .

Отсюда видим, что 11723 < 200 , то 200 2 = 40 000 , а 11 723 < 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Для более точной оценки числа 11723 необходимо записать выражение 108 2 = 11 664 , а 109 2 = 11 881 , то 108 2 < 11 723 < 109 2 . Отсюда следует, что 11723 < 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

При разложении получим, что 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 – это все простые числа. Весь данный процесс можно изобразить как деление столбиком. То есть разделить 11723 на 19 . Число 19 является одним из его множителей, так как получим деление без остатка. Изобразим деление столбиком:

Отсюда следует, что 11723 является составным числом, потому как кроме себя и 1 имеет делитель 19 .

Ответ: 11723 является составным числом.

Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter

Определение 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

Рекомендуем почитать