Простые числа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства простых чисел)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Теорема о существовании бесконечного числа простых чисел)
(не показано 10 промежуточных версий 2 участников)
Строка 30: Строка 30:
 
Рассмотрим множество <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\,q</tex>. Так как <tex>q</tex> делится на <tex>a</tex>, то существует такое натуральное число <tex>f</tex>, что <tex>q = f\,a</tex>. Следовательно, существуют такие натуральные числа <tex>f</tex>, <tex>k</tex>, что <tex>q = k\,f\,a</tex>, т.е. <tex> n</tex> делится на <tex>a</tex>.) Значит, <tex>q</tex> не наименьшее число в множестве <tex>M</tex>. Получили противоречие. Значит, <tex>q</tex> — простое число.  
+
Пусть <tex>q</tex> неЛУЧШИЙ ФАНФИК ВСЕХ ВРЕМЕН И НАРОДОВ ПО ССЫЛКЕ (НЕ ВРУ, ЧЕСТНО) https://ficbook.net/readfic/9834408 простое, тогда существует <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> не наименьшее числоЛУЧШИЙ ФАНФИК ВСЕХ ВРЕМЕН И НАРОДОВ ПО ССЫЛКЕ (НЕ ВРУ, ЧЕСТНО) https://ficbook.net/readfic/9834408 в множестве <tex>M</tex>. Получили противоречие. Значит, <tex>q</tex> — простое число.  
 
}}
 
}}
  
Строка 59: Строка 59:
 
Простых чисел бесконечно много.
 
Простых чисел бесконечно много.
 
|proof=
 
|proof=
Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.
+
Представим, что количество простых чисел конечно ЛУЧШИЙ ФАНФИК ВСЕХ ВРЕМЕН И НАРОДОВ ПО ССЫЛКЕ (НЕ ВРУ, ЧЕСТНО) https://ficbook.net/readfic/9834408 Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.
 
}}
 
}}
  
Строка 67: Строка 67:
 
|id=th2
 
|id=th2
 
|statement=
 
|statement=
Ряд <tex>\textstyle \sum_{}^{}frac{1}{n}</tex> расходится.
+
Ряд <tex>\sum_{}\dfrac{1}{n}</tex> расходится.
 
|proof=
 
|proof=
<tex>\sum_{n=1}^\infty\frac{1}{n} = \prod_{p} {(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots)}</tex>, где <tex>p</tex> — простое. Таким образом, получаем все числа по одному разу после раскрытия скобок.
+
<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 \le k}^{}{(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots)} \ge \sum_{n \le k} \frac{1}{n}</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> \ln(1+x) \approx x + o(x) </tex> и логарифмируя, выводим:
<tex> \sum_{p} {\ln(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots)} \approx \sum_{p} { (\frac{1}{p} + \frac{1}{p^2} + \cdots)} \le \frac{c}{p^2} </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}{n}</tex>==
+
==Теорема о расходимости ряда <tex>\sum_{}^{}\frac{1}{p}</tex>==
  
 
{{Теорема
 
{{Теорема
 
|id=th3
 
|id=th3
 
|statement=
 
|statement=
Ряд <tex>\sum_{}^{}\frac{1}{p}</tex>, где <tex>p</tex> — простое, расходится.
+
Ряд <tex>\sum_{}^{}\dfrac{1}{p}</tex>, где <tex>p</tex> — простое, расходится.
 
|proof=
 
|proof=
 
Работая в условиях [[#th2|предыдущей теоремы]], продолжаем:
 
Работая в условиях [[#th2|предыдущей теоремы]], продолжаем:
<tex> \ln(1+x) \le x</tex>, тогда <tex> \sum_{}^{} {\ln(1 + \frac{1}{p} + \cdots)} \le \sum_{}^{} {( \frac{1}{p} + \frac{1}{p^2} + \cdots)}</tex>.
+
<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_{}^{} \frac{1}{p} \ge \sum_{}^{} {[\ln(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots) - \frac{c}{p^2}]} </tex> — расходится.
+
Финально: <tex> \sum_{}^{} \dfrac{1}{p} \geqslant  \sum_{}^{} {[\ln(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots) - \dfrac{c}{p^2}]} </tex> — расходится.
 
}}
 
}}
  
Строка 97: Строка 97:
 
* И. М. Виноградов. "Основы теории чисел" {{---}} c. 18 - 20.
 
* И. М. Виноградов. "Основы теории чисел" {{---}} c. 18 - 20.
  
[[Категория: Алгоритмы алгебры и теории чисел]]
+
[[Категория: Теория чисел]]
 
[[Категория: Классы чисел]]
 
[[Категория: Классы чисел]]

Версия 17:53, 10 марта 2021

Определение:
Натуральное число [math]p[/math] называется простым (англ. prime number), если [math]p\gt 1[/math] и [math]p[/math] не имеет натуральных делителей, отличных от [math]1[/math] и [math]p[/math].


Определение:
Натуральное число [math]n\gt 1[/math] называется составным (англ. composite number), если [math]n[/math] имеет по крайней мере один натуральный делитель, отличный от [math]1[/math] и [math]n[/math].


Согласно определениям, множество натуральных чисел разбивается на [math]3[/math] подмножества:

  1. Простые числа.
  2. Составные числа.
  3. Число [math]1[/math], которое не причисляется ни к простым, ни к составным числам.


Свойства простых чисел

Утверждение (свойство 1):
Если [math]p_1[/math], [math]p_2[/math] — различные простые числа, то [math]p_2[/math] не делится без остатка на [math]p_1[/math].
[math]\triangleright[/math]
Натуральными делителями простого числа [math]p_2[/math] являются только [math]1[/math] и [math]p_2[/math]. Простое число [math]p_1 \neq 1[/math], и [math]p_1 \neq p_2[/math]. Значит, [math]p_2[/math] не делится на [math]p_1[/math].
[math]\triangleleft[/math]
Утверждение (свойство 2):
Для любого натурального числа [math]n\gt 1[/math], наименьший отличный от [math]1[/math] натуральный делитель всегда является простым числом.
[math]\triangleright[/math]

Рассмотрим множество [math]M[/math], состоящее из натуральных, отличных от [math]1[/math], делителей числа [math]n[/math]. Множество [math]M[/math] не пустое, так как [math]n \in M[/math]. Значит, в множестве [math]M[/math] существует наименьшее число [math]q\gt 1[/math].

Пусть [math]q[/math] неЛУЧШИЙ ФАНФИК ВСЕХ ВРЕМЕН И НАРОДОВ ПО ССЫЛКЕ (НЕ ВРУ, ЧЕСТНО) https://ficbook.net/readfic/9834408 простое, тогда существует [math]a[/math] такое, что [math]1\lt a\lt q[/math] и [math]q[/math] делится на [math]a[/math]. Так как [math]n[/math] делится на [math]q[/math], то [math] n[/math] делится на [math]a[/math]. (Так как [math]n[/math] делится на [math]q[/math], то существует такое натуральное число [math]k[/math], что [math]n = k \times q[/math]. Так как [math]q[/math] делится на [math]a[/math], то существует такое натуральное число [math]f[/math], что [math]q = f \times a[/math]. Следовательно, существуют такие натуральные числа [math]f[/math], [math]k[/math], что [math]q = k \times f \times a[/math], т.е. [math] n[/math] делится на [math]a[/math].) Значит, [math]q[/math] не наименьшее числоЛУЧШИЙ ФАНФИК ВСЕХ ВРЕМЕН И НАРОДОВ ПО ССЫЛКЕ (НЕ ВРУ, ЧЕСТНО) https://ficbook.net/readfic/9834408 в множестве [math]M[/math]. Получили противоречие. Значит, [math]q[/math] — простое число.
[math]\triangleleft[/math]

Из свойства 2 мы получаем алгоритм для поиска простых чисел "Решето Эратосфена".

Множество простых чисел

Утверждение:
Множество простых чисел бесконечно.
[math]\triangleright[/math]

Пусть множество простых чисел конечно и состоит из чисел [math]2, 3, 5, \ldots , p[/math], где [math]p[/math] — последнее, самое большое простое число.

Рассмотрим число [math]N=2 \times 3 \times 5 \times \ldots \times p +1[/math]. Число [math]N[/math] представимо в виде [math]N=2 \times (3 \times 5 \times \ldots \times p) +1,[/math] где [math]2\,[/math] — делитель, [math](3 \times 5 \times \ldots \times p)\,[/math] — частное, [math]1\,[/math] — остаток, причем [math]0\leqslant 1 \lt 2.[/math] Таким образом, при делении [math]N[/math] на [math]2[/math] получится остаток [math]1[/math], число [math]N[/math] на простое число [math]1[/math] не делится. Аналогично [math]N[/math] не делится ни на одно из простых чисел ([math]3, 5, \ldots , p),[/math] так как при делении [math]N[/math] на эти числа получится остаток [math]1[/math].

Значит, число [math]N=1[/math] (по свойству 2), так как у числа [math]N[/math] нет простых делителей по предположению.

C другой стороны, [math]N\gt 1[/math]. Значит, предположение о том, что множество простых чисел конечно, неверно.
[math]\triangleleft[/math]

Последовательность простых чисел начинается так:

[math]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 [/math]

Теорема о существовании бесконечного числа простых чисел

Теорема:
Простых чисел бесконечно много.
Доказательство:
[math]\triangleright[/math]
Представим, что количество простых чисел конечно ЛУЧШИЙ ФАНФИК ВСЕХ ВРЕМЕН И НАРОДОВ ПО ССЫЛКЕ (НЕ ВРУ, ЧЕСТНО) https://ficbook.net/readfic/9834408 Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.
[math]\triangleleft[/math]

Теорема о расходимости ряда [math]\sum_{}\frac{1}{n}[/math]

Теорема:
Ряд [math]\sum_{}\dfrac{1}{n}[/math] расходится.
Доказательство:
[math]\triangleright[/math]
[math]\sum_{n=1}^\infty\dfrac{1}{n} = \prod_{p} {(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)}[/math], где [math]p[/math] — простое. Таким образом, получаем все числа по одному разу после раскрытия скобок.
[math]\triangleleft[/math]

Заметим для некоторого [math]k[/math]: [math]\sum_{p \leqslant k}^{}{(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)} \ge \sum_{n \leqslant k} \dfrac{1}{n}[/math]. Теперь, пользуясь выражением [math] \ln(1+x) \approx x + o(x) [/math] и логарифмируя, выводим: [math] \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} [/math] — расходится.

Теорема о расходимости ряда [math]\sum_{}^{}\frac{1}{p}[/math]

Теорема:
Ряд [math]\sum_{}^{}\dfrac{1}{p}[/math], где [math]p[/math] — простое, расходится.
Доказательство:
[math]\triangleright[/math]

Работая в условиях предыдущей теоремы, продолжаем: [math] \ln(1+x) \leqslant x[/math], тогда [math] \sum_{}^{} {\ln(1 + \dfrac{1}{p} + \cdots)} \leqslant \sum_{}^{} {( \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots)}[/math].

Финально: [math] \sum_{}^{} \dfrac{1}{p} \geqslant \sum_{}^{} {[\ln(1 + \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots) - \dfrac{c}{p^2}]} [/math] — расходится.
[math]\triangleleft[/math]

См. также

Источники инфомации

  • А.А. Бухштаб. "Теория чисел" — Просвещение. 1966 г. — с. 28 - 33.
  • И. М. Виноградов. "Основы теории чисел" — c. 18 - 20.