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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м ("Так как n делится на q, то n делится на a." - расписано подробней в ())
(Метки: правка с мобильного устройства, правка из мобильной версии)
Строка 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>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>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, k</tex> , что <tex>q = k\,f\,a</tex>, т.е. <tex> n</tex> делится на <tex>a</tex>.) Значит <tex>q</tex> не наименьшее число в множестве <tex>M</tex>. Получили противоречие. Значит <tex>q</tex> простое число.  
 
}}
 
}}
  

Версия 18:12, 10 мая 2018

Определение:
Натуральное число [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] не простое, тогда существует [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\,q[/math]. Так как [math]q[/math] делится на [math]a[/math], то существует такое натуральное число [math]f\,[/math], что [math]q = f\,a[/math]. Следовательно, существуют такие натуральные числа [math]f, k[/math] , что [math]q = k\,f\,a[/math], т.е. [math] n[/math] делится на [math]a[/math].) Значит [math]q[/math] не наименьшее число в множестве [math]M[/math]. Получили противоречие. Значит [math]q[/math] простое число.
[math]\triangleleft[/math]

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

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

Утверждение:
Множество простых чисел бесконечно.
[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]2, 3, 5, \ldots , p[/math]), так как при делении [math]N[/math] на эти числа получится остаток [math]1[/math].

Значит число [math]N=1[/math] (по свойству [math]2[/math]), так как у числа [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]

См. также

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

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