|
Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа — элементарные «строительные блоки» натуральных чисел. Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина. Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так: Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор. Среди простых делителей натурального числа могут быть равные, и их
произведение можно записать в виде степени. Тогда разложение
натурального числа а на простые множители можно представить в следующем виде:
a = p 1 к1 * p 2 к2 * p 3 k 3 *...* pnkn где p 1 , p 2, p 3 ..., pn — различные простые числа, k 1 k 2 ..., kn — натуральные.
|
