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

16

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

Как в математике делаются открытия? Часто — так же, как в других наукках: подмеченный факт исследователь пытается включить в качестве частного случай в общую закономерность. Найти эту закономерность не всегда удается, и математик, как и любой другой исследователь, действует «методом проб и ошибок».
Как при этом могут выглядеть его рассужdenя, когда речь идет о делимости чисел, расссказано в этой статье.

1. Малая теорема Ферма

Ясно, что квадрат $n^2$ натурального числа $n$ будет четным или нечетным одновременно с самим числом $n$. Таким образом, числа $n^2$ и $n$ всегда будут одновременно четными или нечетными одновременно. Но, более того, эта разность всегда и на 3. В самом деле, число $n$ либо делится на 3 (то есть имеет вид $3k$), либо дает при делении на 3 остаток 1 (имеет вид $n=3k+1$), либо дает при делении на 3 остаток 2 (тогда его можно представить в виде $n=3k+2=3(k+1)-1=3(k'-1)$).

Если $n$ делится на 3, то и $n^3$ делится на 3. Если же $n$ имеет вид $3k \pm 1$, то $n^3=(3k \pm 1)^3=3(9k^3 \pm 9k^2+3k) \pm 1$, то есть $n^3=3l \pm 1$.

Во всех случаях разность $n^3-n$ кратна 3. Итак, имеет место

Утверждение 2. Разность $n^3-n$ делится на 3 при любом $n$.

Упражнения

1. Докажите утверждение 1 и 2 разложением многочленов $n^2-n$ и $n^3-n$ на множители.
2. Докажите, что разность $n^3-n$ делится на 6 при любом $n$.

Утверждение 1 и 2 внушают надежду, что справедлива.

Гипотеза 1. Разность $n^m-n$ делится на $m$ при любых $m$ и $n$.

Увы! Легко набрести на контрпример, опровергающий эту гипотезу: разность $2^4-2=14$ не делится на 4.

Все же хотелось бы найдеть, что сходство между утверждениями 1 и 2 не является случайным. Попробуем проверить разность $n^5-n$. Например, $2^5-2=30$ делится на 5. Легко установить, что это не случайно, и справедливо.

Утверждение 3. Разность $n^5-n$ делится на 5 при любом $n$.

В самом деле, число $n$ либо делится на 5, либо дает при делении на 5 один из остатков 1, 4 (в этих случаях оно представимо в виде $5k \pm 1$), либо дает при делении на 5 один из остатков 2, 3 (тогда $n=5k \pm 2$). Если $n$ делится на 5, то и $n^5$ делится на 5. Если $n=5k \pm 1$, то

$$n^2=(5k \pm 1)^2=5(5k^2 \pm 2k)+1.$$

Если $n=5k \pm 2$, то

$$n^2=(5k \pm 2)^2=5(5k^2 \pm 4k+1)-1.$$

Таким образом, если $n$ не делится на 5, то число $n^2$ имеет вид $5L \pm 1$ и

$$n^4=(5L \pm 1)^2=5(5L^2 \pm 2L)+1$$

дает при делении на 5 остаток 1. Отсюда следует, что разность $n^4-1$, а значит и разность $n^5-n=n(n^4-1)$, делится на 5.

Теперь мы имеем уже три положительных утверждения. Это заставляет нас продолжать поиск. Разность

18

2. Почти простые числа

Вспомним, как мы в предыдущем пункте пришли к малой теореме Ферма. Фиксировав $m$, мы выязывали, все ли разности $n^m - n$ делятся на $m$. Чтобы сформировать правильное прибодобную гипотезу, мы каждый раз сначала проверяли, делится ли на $m$ число $2^m - 2$. При всех рассмотренных простых $m$ разность $2^m - 2$ делилась на $m$, при составных — не делилась. Естественно возникает

Гиотеза 5. Разность $2^m - 2$ делится на $m$ при простом $m$ и не делится — при составном*).

Гипотезу 5 высказали еще древнекитайские математики — около 2,5 тысячи лет назад.

В древнем Китае, как и во всех других предшествующих древней Греции цивилизациях (Вавилоне, Древнем Египте и т. д.), математика была неедуктивной, а решетурной наукой. Основную роль в математике играли не выводы, а факты, причем вопрос о том, как тот или иной факт был установлен, не считался особенно важным: достаточно правдополобная доказка в полне могла заменить доказательство. Выписав несколько десятков первых чисел $N_m = 2^m - 2$ ($m = 2, 3, 4, \dots$) и проверив, какие из них делятся на $m$, а какие не делятся, древнекитайские математики уверлились в справедливости гипотезы 5 и зафиксировали ее как теорему. Однако мы с вами — не древние китайцы. Великие Евклид и Архимед (а еще ранее их — и Пифагор, и Платон, и Аристотель) убедили нас, что существ математики состоит именно в доказательстве гипотезы 5 и зафиксировали ее как теорему. Однако，我们没有证据表明 $m \neq 1$ почти простым, если разность $2^m - 2$ делится на $m$.

В силу малой теоремы Ферма любое простое число является почти простым. Поэтому гипотезу 5 можно переформулировать так:

Гипотеза 5’. Какое почти простое число является простым.

*) Первая «половина» гипотезы 5 является, конечно, частью случая теоремы Ферма.

Мы уже сказали, что древнекитайские математики рассмотрели делимость на $m$ нескольких десятков первых чисел $N_m$ и не нашли опровергающих примеров. Сегодня, с помощью ЭВМ, нетрудно было бы проверить делимость на $m$ нескольких сотен первых чисел $N_m$. Однако и тут опровергнуть гипотезу 5 было бы непросто: среди первых 300 натуральных чисел мы бы не нашли почти простых чисел, не являющихся простыми. Однако гипотеза 5 все таки неверна, то есть справедлива.

Теорема 2. Существуют почти простые числа, не являющиеся простыми.

Самым маленьким таким числом является 341. Найти его было нельзя, доказать же, что оно — почти простое, совсем несложно, если к нашим услугам будет

Лемма 1. Разность $n^m - 1$ делится на $n - 1$ при любых $m$ и $n$, вытекаювая из точки простых чисел, не являющихся простыми.

Лемма 2. Разность $n^m - 1$ делится на $n - 1$ при любых $m$ и $n$, вытекаювая из точки простых чисел, не являющихся простыми, причем $m_1 > m$.

В самом деле, так как $m$ — не простое, $m = kL$, где $k > 1$, $L > 1$. Тогда, в силу леммы 1,

$$m_1 = 2^m - 1 = 2^{kL} - 1 = (2^k)^L - 1$$

делится на $2^k - 1$. Из $L > 1$ следует $2^k - 1 < m_1$. Из $k > 1$ вытекает $2^k - 1 > 1$. Значит, $m_1$ — не простое.

Так как $m$ — почти простое, $m_1 = 2^m - 2 = N_m$ делится на $m$: $N_m = mn$. Поэтому, в силу леммы 1,