Таблицы Брадиса

Если же р имеет вид

Если же р имеет вид

Элементы математики в задачах - Г. А. Мерзон

& Пользуясь идеей этого рассуждения можно предложить следую­щий «алгоритм» построения простых чисел: «пусть мы знаем все простые числа до рп включительно; тогда число рх • ... ■ рп + 1 — простое». Стоит разобраться, почему это рассуждение неверно. (Первый контрпример — 2 ■ 3 ■ 5 ■ 7 ■ 11 ■ 13 + 1 = 30031 = 59 ■ 509.)

Задача 10. Докажите, что для любого п найдутся п подряд идущих составных чисел.

Решение. Вот пример п подряд идущих составных чисел: (п + 1)! + 2, (п + 1)! + 3,..., (п +1)! + (п +1). Каждое из них не является простым. Действительно, первое делится на 2, второе — на 3, третье — на 4, и так далее. Напомним, что п! — это обозначение для произведения

1 ■ 2 •... ■ (п — 1) ■ п.

Задача 11*. Обозначим через п? произведение всех простых чисел, меньших п. Докажите, что при п > 3 выполняется неравенство п? > п.

Решение. Пусть р1,..., рк — все простые числа, меньшие п. Рассмот­рим N = п? — 1 = р1 р2...рк — 1; пусть т — какой-либо его простой делитель. Число N не делится ни на одно из чисел р{, поэтому т ^ п. С другой стороны, N + 1 > т. Значит, п? > п.

Задача 12. а) Найдите все простые р такие, что р + 2 и р + 4 также простые.

б**) Докажите, что существует бесконечно много таких простых чисел р, что число р + 2 также простое.

Ответ. а) 3.

Решение. а) Пусть р имеет вид 3к для некоторого целого к. Тогда оно может быть равно лишь трем. Если же р имеет вид 3к + 1 для некоторого целого к, то тогда р + 2 = 3к + 3 — составное, следова­тельно р не может иметь такой вид. Остается последняя возможность: р = 3к + 2 для некоторого целого к, но тогда р + 4 = 3к + 6 делится на 3, следовательно такого тоже быть не может.

б)  Эта несложная на вид задача представляет собой нерешенную проблему.