Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Простые числа - что это такое и на что нужно

На главную Математический раздел Криптография и т.д. Новости

1. Понятия

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

Простое число - натуральное число, которое делится только на единицу и на само себя, больше ни на что оно не делится. То есть эта сволочь имеет два делителя.

Составное число - натуральное число, которое имеет не менее трёх делителей, включая единицу и самого себя.

Примеры: 2, 3, 5 - простые числа, а вот 9 - составное число (делится на 1, 3, 9 - три делителя). 6 - тоже составное число (эта сволочь делится на 1, 2, 3, 6 - имеет четыре делителя). В табличке выше жёлтым выделены все простые числа, которые не больше 40. Пользуйтесь сколько угодно и бесплатно)

Единица не подходит ни под одно из двух определений. Она сама по себе и не является ни простым числом, ни составным числом)

(Школоте не читать этот абзац, а вот студентам можно!) С точки зрения теории множеств, множество натуральных чисел - объединение множества простых чисел, множества составных чисел и ещё одного странного множества, состоящего только из единицы. Множество простых чисел и множество составных чисел не пересекаются, даже после пива)

Применение простых чисел (зачем вообще эта наука?)

Где применяются простые числа?

Ну допустим, в криптографии (науке о "тайнописи") понятие простых чисел применяется довольно активно. Так, в описании шифра Хилла можно увидеть рекомендацию использовать такой алфавит, который имеет число символов в виде простого числа. Также упоминание простых чисел часто встречается в теории случайных генераторов. Если количество символов в алфавите - простое число, то это упрощает подбор ключа для системы подстановок Цезаря.

Простые числа могут быть использованы для получения групп так называемых взаимно простых чисел (перейдя по ссылке, можно узнать, как именно и что это вообще за гадость - взаимно простые числа).

2. О генераторах простых чисел

В самые разные времена учёный народ пытался получить такую функцию f(n), которая при любом натуральном n (или целом неотрицательном) давала бы простое число. Занятие интересное, но, как показывает практика, крайне сложное. Смысл такие функции имеют для получения больших простых чисел, ибо в лобовую тут никак.

Такой известный математик, как Леонард Эйлер, в своё время получил полином

Как установил автор, при n от 1 до 40 эта формула даёт простые числа. А вот дальше начинается облом. При n = 41 и вообще при любом n, кратном 41, формула даёт сбой - результат кратен 41. Для разнообразия давайте подставим ещё n = 42, получим 42*42 - 1 = (42 - 1)(42 + 1) = 41 * 43 - а это точно составное число.

Пьер Ферма предлагал другую МегаФормулу:

Как он полагал, при неотрицательных n она будет давать простое число. При n от 0 до 4 это так. При n = 5 получается число, кратное 641 (легко проверить, когда это уже знаем). Впрочем, в те далёкие времена, когда жил сей товарищ, это выяснить не так уж просто было - не было компов и языков программирования)

3. Числа-близнецы

Пара простых чисел x, y называется числами-близнецами, если x = y + 2 или y = x + 2.

Примеры: 3 и 5, 5 и 7, 29 и 31.

Также у математиков вызывают интерес "четвёрки" простых чисел вида {n-4, n-2, n+2, n+4} (например, 11, 13, 17, 19). А вот "пятёрок" вида {n-4, n-2, n, n+2, n+4}, где все числа - простые, не бывает, поскольку какое-то из чисел обязательно будет кратно трём.

"Тройня" в ряду простых чисел только одна - 3, 5, 7. Других наборов простых чисел вида {n, n+2, n+4} не существует, так как в такой тройке хотя бы одно число будет делиться на 3.

Примечательное свойство чисел-близнецов: все их пары, кроме (3, 5), имеют вид (6n+1, 6n-1), где n - натуральное число, но не всякая пара (6n+1, 6n-1) является парой простых чисел-близнецов.

Пример к свойству: при n = 6 получаем пару (35, 37), где 35 - составное число.

4. Кое-какие свойства из оперы простых чисел

1. Если число x не делится на простое число y, то x не делится на любое составное число, делящееся на y.

Допустим обратное: всё-таки x будет делиться на такое составное число z, то есть x = kz, где k > 1 - натуральное число. Учтём, что z = my, где m > 1 - натуральное число. Выходит, что x = kmy, то есть x делится на y, чего у нас нет. Противоречие...

2. Если число x не делится ни на одно из простых чисел, лежащих в диапазоне от 2 до x-1, то x-простое число.

Пояснение: если x не делится на простые числа, меньшие него, то и на составные числа, меньшие его, x также делиться не может. Допустим, подумайте: если x не делится на 2, то может ли он делиться на 4? Если x не делится на 3, то может ли делиться на 6, 9?

Пусть . Иначе говоря, p * p не превышает x, а вот (p+1)*(p+1) > x.

3. Если число x не делится ни на одно из простых чисел, лежащих в диапазоне от 2 до p, то x-простое число.

Пояснение: пусть x = yz, y > p. Тогда z должен быть не больше p. Если это не так, то yz >= (p+1) * (p+1) > x, что есть противоречие. Это значит, что нарушение свойства простого числа точно обнаружится при проверке возможных делителей от 2 до p.

Чтобы x имело составной делитель y, x должно делиться на простые числа, на которые делится y. Стало быть, для проверки на простоту достаточно искать остатки от деления числа x на простые числа, которые не больше p.

По сути свойство 3 "перекликается" со вторым и на практике заменяет второе, поскольку требует меньше действий для проверки, является ли x простым числом. Приведём ещё одно свойство, не связанное с первыми двумя:

4. Сумма простых чисел z, y может быть простым числом x, только если z=2, а x и y - близнецы или y=2, а x и z - близнецы.

Пояснение: двойка - единственное чётное простое число. Стало быть, если z и y отличны от 2 и при этом просты, то оба они нечётны. Это значит, что x - чётное, причём x > 2, то есть x - составное число.

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X