Редактирование: Простые числа

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
[[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|Натуральное]] число <tex>p</tex> называется '''простым''' (англ. ''prime number''), если <tex>p>1</tex> и <tex>p</tex> не имеет натуральных [[Классы_чисел#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5|делителей]], отличных от <tex>1</tex> и <tex>p</tex>.
+
[[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|Натуральное]] число <tex>p</tex> называется '''простым''' (англ. ''prime number''), если <tex>p>1</tex> и <tex>p</tex> не имеет натуральных [[Классы_чисел#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5|делителей]] отличных от <tex>1</tex> и <tex>p</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
[[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|Натуральное]] число <tex>n>1</tex> называется '''составным''' (англ. ''composite number''), если <tex>n</tex> имеет по крайней мере один натуральный [[Классы_чисел#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5|делитель]], отличный от <tex>1</tex> и <tex>n</tex>.  
+
[[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|Натуральное]] число <tex>n>1</tex> называется '''составным''' (англ. ''composite number''), если <tex>n</tex> имеет по крайней мере один натуральный [[Классы_чисел#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5|делитель]] отличный от <tex>1</tex> и <tex>n</tex>.  
 
}}
 
}}
  
Строка 19: Строка 19:
 
{{Утверждение
 
{{Утверждение
 
|about=свойство 1
 
|about=свойство 1
|statement=Если <tex>p_1</tex>, <tex>p_2</tex> {{---}} различные простые числа, то <tex>p_2</tex> '''не [[Натуральные числа#Деление чисел с остатком | делится без остатка]]''' на <tex>p_1</tex>.
+
|statement=Если <tex>p_1</tex>, <tex>p_2</tex> {{---}} различные простые числа, то <tex>p_2</tex> '''не [[Натуральные_и_целые_числа#.D0.94.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.87.D0.B8.D1.81.D0.B5.D0.BB_.D1.81_.D0.BE.D1.81.D1.82.D0.B0.D1.82.D0.BA.D0.BE.D0.BC|делится без остатка]]''' на <tex>p_1</tex>.
 
|proof=
 
|proof=
Натуральными делителями простого числа <tex>p_2</tex> являются только <tex>1</tex> и <tex>p_2</tex>. Простое число <tex>p_1 \neq 1</tex>, и <tex>p_1 \neq p_2</tex>. Значит, <tex>p_2</tex> не делится на <tex>p_1</tex>.
+
Натуральными делителями простого числа <tex>p_2</tex> являются только <tex>1</tex> и <tex>p_2</tex>. Простое число <tex>p_1 \neq 1</tex> и <tex>p_1 \neq p_2</tex>. Значит <tex>p_2</tex> не делится на <tex>p_1</tex>.
 
}}
 
}}
  
Строка 28: Строка 28:
 
|statement=Для любого [[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|натурального]] числа <tex>n>1</tex>, наименьший отличный от <tex>1</tex> натуральный делитель всегда является '''простым числом'''.
 
|statement=Для любого [[Классы_чисел#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.B0.D1.82.D1.83.D1.80.D0.B0.D0.BB.D1.8C.D0.BD.D1.8B.D1.85_.D1.87.D0.B8.D1.81.D0.B5.D0.BB|натурального]] числа <tex>n>1</tex>, наименьший отличный от <tex>1</tex> натуральный делитель всегда является '''простым числом'''.
 
|proof=
 
|proof=
Рассмотрим множество <tex>M</tex>, состоящее из натуральных, отличных от <tex>1</tex>, делителей числа <tex>n</tex>. Множество <tex>M</tex> не пустое, так как <tex>n \in M</tex>. Значит, в множестве <tex>M</tex> существует наименьшее число <tex>q>1</tex>.  
+
Рассмотрим множество <tex>M</tex>, состоящее из натуральных, отличных от <tex>1</tex> делителей числа <tex>n</tex>. Множество <tex>M</tex> не пустое, так как <tex>n \in M</tex>. Значит в множестве <tex>M</tex> существует наименьшее число <tex>q>1</tex>.  
  
Пусть <tex>q</tex> не простое, тогда существует <tex>a</tex> такое, что <tex>1<a<q</tex> и <tex>q</tex> делится на <tex>a</tex>. Так как <tex>n</tex> делится на <tex>q</tex>, то <tex> n</tex> делится на <tex>a</tex>. (Так как <tex>n</tex> делится на <tex>q</tex>, то существует такое натуральное число <tex>k</tex>, что <tex>n = k \times q</tex>. Так как <tex>q</tex> делится на <tex>a</tex>, то существует такое натуральное число <tex>f</tex>, что <tex>q = f \times a</tex>. Следовательно, существуют такие натуральные числа <tex>f</tex>, <tex>k</tex>, что <tex>q = k \times f \times a</tex>, т.е. <tex> n</tex> делится на <tex>a</tex>.) Значит, <tex>q</tex> не наименьшее в множестве <tex>M</tex>. Получили противоречие. Значит, <tex>q</tex> простое число.  
+
Пусть <tex>q</tex> не простое, тогда существует <tex>a</tex> такое, что <tex>1<a<q</tex> и <tex>q</tex> делится на <tex>a</tex>. Так как <tex>n</tex> делится на <tex>q</tex>, то <tex> n</tex> делится на <tex>a</tex>. Значит <tex>q</tex> не наименьшее число в множестве <tex>M</tex>. Получили противоречие. Значит <tex>q</tex> простое число.  
 
}}
 
}}
  
Из свойства 2 мы получаем алгоритм для поиска простых чисел "[[Решето Эратосфена]]".
+
Из свойства <tex>2</tex> мы получаем алгоритм для поиска простых чисел "[[Решето Эратосфена]]".
  
 
==Множество простых чисел==
 
==Множество простых чисел==
Строка 39: Строка 39:
 
|statement=Множество простых чисел '''бесконечно'''.
 
|statement=Множество простых чисел '''бесконечно'''.
 
|proof=
 
|proof=
Пусть множество простых чисел конечно и состоит из чисел <tex>2, 3, 5, \ldots , p</tex>, где <tex>p</tex> {{---}} последнее, самое большое простое число.  
+
Пусть множество простых чисел конечно и состоит из чисел <tex>2,3,5, \ldots ,p</tex>, где <tex>p</tex> {{---}} последнее, самое большое простое число.  
  
Рассмотрим число <tex>N=2 \times 3 \times 5 \times \ldots \times p +1</tex>.
+
Рассмотрим число <tex>N=2*3*5* \ldots *p +1</tex>. Число <tex>N</tex> не делится ни на одно из простых чисел (<tex>2, 3, 5, \ldots , p</tex>), так как при делении <tex>N</tex> на эти числа получится остаток <tex>1</tex>.  
Число <tex>N</tex> представимо в виде <tex>N=2 \times (3 \times 5 \times \ldots \times p) +1,</tex> где <tex>2\,</tex> — делитель, <tex>(3 \times 5 \times \ldots \times p)\,</tex> — частное, <tex>1\,</tex> — остаток, причем <tex>0\leqslant 1 < 2.</tex> Таким образом, при делении <tex>N</tex> на <tex>2</tex> получится остаток <tex>1</tex>, число <tex>N</tex> на простое число <tex>1</tex> не делится.
 
Аналогично <tex>N</tex> не делится ни на одно из простых чисел (<tex>3, 5, \ldots , p),</tex> так как при делении <tex>N</tex> на эти числа получится остаток <tex>1</tex>.  
 
  
Значит, число <tex>N=1</tex> (по свойству 2), так как у числа <tex>N</tex> нет простых делителей по предположению.
+
Значит число <tex>N=1</tex> (по свойству <tex>2</tex>), так как у числа <tex>N</tex> нет простых делителей по предположению.
C другой стороны, <tex>N>1</tex>. Значит, предположение о том, что множество простых чисел конечно, неверно.  
+
C другой стороны <tex>N>1</tex>. Значит предположение, что множество простых чисел конечно, неверно.  
 
}}
 
}}
  
 
Последовательность простых чисел начинается так:
 
Последовательность простых чисел начинается так:
: <tex>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, \ldots </tex>
+
: <tex>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, \dots </tex>
 
 
==Теорема о существовании бесконечного числа простых чисел==
 
 
 
{{Теорема
 
|id=th1
 
|statement=
 
Простых чисел бесконечно много.
 
|proof=
 
Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.
 
}}
 
 
 
==Теорема о расходимости ряда <tex>\sum_{}\frac{1}{n}</tex>==
 
 
 
{{Теорема
 
|id=th2
 
|statement=
 
Ряд <tex>\sum_{}\dfrac{1}{n}</tex> расходится.
 
|proof=
 
<tex>\sum_{n=1}^\infty\dfrac{1}{n} = \prod_{p} {(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)}</tex>, где <tex>p</tex> — простое. Таким образом, получаем все числа по одному разу после раскрытия скобок.
 
}}
 
Заметим для некоторого <tex>k</tex>: <tex>\sum_{p \leqslant  k}^{}{(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)} \ge \sum_{n \leqslant  k} \dfrac{1}{n}</tex>.
 
Теперь, пользуясь выражением <tex> \ln(1+x) \approx x + o(x) </tex> и логарифмируя, выводим:
 
<tex> \sum_{p} {\ln(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)} \approx \sum_{p} { (\dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)} \leqslant  \dfrac{c}{p^2} </tex> — расходится.
 
 
 
==Теорема о расходимости ряда <tex>\sum_{}^{}\frac{1}{p}</tex>==
 
 
 
{{Теорема
 
|id=th3
 
|statement=
 
Ряд <tex>\sum_{}^{}\dfrac{1}{p}</tex>, где <tex>p</tex> — простое, расходится.
 
|proof=
 
Работая в условиях [[#th2|предыдущей теоремы]], продолжаем:
 
<tex> \ln(1+x) \leqslant  x</tex>, тогда <tex> \sum_{}^{} {\ln(1 + \dfrac{1}{p} + \cdots)} \leqslant  \sum_{}^{} {( \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)}</tex>.
 
Финально: <tex> \sum_{}^{} \dfrac{1}{p} \geqslant  \sum_{}^{} {[\ln(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots) - \dfrac{c}{p^2}]} </tex> — расходится.
 
}}
 
  
 
==См. также==
 
==См. также==
* [[Натуральные числа]]
+
* [[Натуральные и целые числа]]
 
* [[Основная теорема арифметики]]
 
* [[Основная теорема арифметики]]
 
* [[Теоремы о простых числах]]
 
* [[Теоремы о простых числах]]
Строка 97: Строка 60:
 
* И. М. Виноградов. "Основы теории чисел" {{---}} c. 18 - 20.
 
* И. М. Виноградов. "Основы теории чисел" {{---}} c. 18 - 20.
  
[[Категория: Теория чисел]]
+
[[Категория: Алгоритмы алгебры и теории чисел]]
 
[[Категория: Классы чисел]]
 
[[Категория: Классы чисел]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)