Натуральное число называют простым, если оно не имеет других натуральных делителей, кроме и .
Простым числом будет наименьший, отличный от делитель целого .
Теорема 4.1 (Теорема Евклида)
Существует бесконечно много простых чисел.
Свойства простого числа :
1. Если , то делит нацело ;
Если , то и взаимно простые числа.
Критерий взаимной простоты чисел: два целых числа будут взаимно простые тогда и только тогда, когда (целые) такие, что: (например, : , действительно: ).
2. Если делит нацело , то делит нацело или делит нацело .
3. Всякое целое число разложимо в произведение простых множителей. Это разложение единственно с точностью до порядка следования множителей: .
Криптография, особенно криптография с открытыми ключами, часто использует простые числа (длиной 512 бит и более; существует приблизительно простых чисел длиной бит).
Если обозначить – число простых чисел, не превосходящих положительное , то (теорема о простых числах).