Простые числа

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

Простым числом будет наименьший, отличный от делитель целого .

 

Теорема 4.1 (Теорема Евклида)

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

 

Свойства простого числа :

1. Если , то делит нацело ;

Если , то и взаимно простые числа.

Критерий взаимной простоты чисел: два целых числа будут взаимно простые тогда и только тогда, когда (целые) такие, что: (например, : , действительно: ).

2. Если делит нацело , то делит нацело или делит нацело .

3. Всякое целое число разложимо в произведение простых множителей. Это разложение единственно с точностью до порядка следования множителей: .

 

Криптография, особенно криптография с открытыми ключами, часто использует простые числа (длиной 512 бит и более; существует приблизительно простых чисел длиной бит).

Если обозначить – число простых чисел, не превосходящих положительное , то (теорема о простых числах).