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

Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел.

Перечень первых 1229-ти простых чисел приведён в таблице простых и парных простых чисел, не превосходящих 10000.

Приведём некоторые свойства простых чисел.

• Основная теорема арифметики. Каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей.

• Простых чисел бесконечно много.

• В натуральном ряде чисел можно найти последовательности не содержащие простых чисел любой длины.

• Если p – простое, и p делит a·b, то p делит a или b.

• Mалая теорема Ферма. Если p – простое, a – натуральное, то a^p – a делится на p.

• Теорема Вильсона. Натуральное p > 1 является простым тогда и только тогда, когда (p – 1)! + 1 делится на p.

• Постулат Бертрана. Если n > 1 – натуральное, то существует простое p, такое, что n < p < 2n.

• Теорема Дирихле о простых числах в арифметической прогрессии. Любая арифметическая прогрессия вида a, a + q, a + 2q, a + 3q, ... , где a, q > 1 – целые взаимно простые числа, содержит бесконечно много простых чисел.

• Теорема Ферма. Каждое простое число вида 4k + 1 есть сумма двух квадратов натуральных чисел.

• Всякое простое число, большее 3, представимо в виде 6k + 1 или 6k – 1, где k – некоторое натуральное число.

• Число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, большим 2.

• Число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, большим 1.

1. Три простых числа, каждое из которых больше 10, образуют арифметическую прогрессию. Докажите, что разность прогрессии делится на 6.

Все данные простые числа нечётные, поэтому их разность делится на 2. Покажем, что она делится и на 3. Пусть данные числа a, a + d, a + 2d. Ни одно из них не делится на 3, поэтому при делении на 3 даёт остаток или 1, или 2. Следовательно, по крайней мере, два из этих чисел дают при делении на 3 одинаковые остатки. Разность этих чисел, равная d или 2d, делится на 3. Поскольку 2 на 3 не делится, то d делится на 3. Итак, разность прогрессии, которая делится на взаимно простые числа 2 и 3, делится на 6, что и требовалось доказать.

2. Докажите, что для произвольного натурального числа n найдётся натуральное m такое, что nm + 1 – составное число.

Можно выбрать m = n + 2, тогда

nm + 1 = n(n + 2) + 1 = n² + 2n + 1 = (n + 1)²

является составным числом.

Или , например, определить m так: если n = 1, то m = 3, в противном случае m = n².  

3. Найдите все целые числа n, для которых модуль значения трёхчлена n² – 7n + 10 будет простым числом.

Так как

|n² – 7n + 10| = |n –2| · |n – 5|,

то следует искать такие n при которых один из множителей последнего произведения равен 1, а второй является простым числом. Этому требованию удовлетворяют n = 3 и n = 4.

Ответ: n = 3, n = 4.

4. Докажите, что если числа

а) m и m² + 2 простые, то число m³ + 2 тоже простое;

б) р, р – 10, р + 10 простые, то число р – 2 тоже простое.

а) Любое простое число m, отличное от 3, можно представить в виде 3n+1 или в виде 3n–1, где n – некоторое натуральное число. В первом случае можно записать

m² + 2 = 9n² + 6n +3,

во втором –

m² + 2 = 9n² – 6n +3,

Так как m > 2, то в любом случае число m²+2 больше 3 и делится на 3, а значит является составным. Следовательно, число m²+2 может быть простым, только если m = 3. В этом случае m²+2 = 11 – простое число, m³+2 = 29 – тоже простое число, что и требовалось доказать.

б) Так как р – 10 = (р – 1) – 9 и р + 10 = (р + 1) + 9, то числа р – 10 и р – 1 при делении на 3 имеют одинаковые остатки, и числа р + 10 и р + 1 при делении на 3 имеют одинаковые остатки.

Из трёх последовательных чисел р – 1, р, р + 1 одно и только одно делится на 3. С учётом выше сказанного, то же утверждение верно для чисел р – 10, р, р + 10. Так как эти числа простые, то р – 10 = 3 и р = 13, поэтому р – 2 = 11 – простое число, что и требовалось доказать.

5. Сколько раз входит двойка в разложение на простые множители произведения

(n + 1) · (n + 2) · (n + 3) · . . . · (2n – 1) · 2n ?

Ответ на поставленный вопрос получим из следующих преобразований:

Ответ: n раз.

6. Найдите все простые p такие, что число p² + 11 имеет ровно 6 различных делителей (включая единицу и само число).

Заметим, что p² + 11 = p² –1 + 12 = (p – 1)(p + 1) + 12 .

Если p > 5 и простое, то числа p – 1 и p + 1 оба четные, и одно из них кратно трем. Поэтому произведение (p – 1)(p + 1) делится на 12, следовательно, p² + 11 также делится на 12, а значит, имеет не менее семи делителей (6 делителей числа 12 и само число p² + 11 > 12 ). Осталось проверить p = 2 и p = 3.

Если p = 2, то p² + 11 = 2² + 11 = 15 имеет 4 делителя (1, 3, 5, 15).

Если p = 3, то p² + 11 = 3² + 11 = 20 имеет 6 делителей (1, 2, 4, 5, 10, 20).

Ответ: p = 3.

7. Найти все натуральные числа n, для которых каждое из шести чисел

n + 1, n + 3, n + 7, n + 9, n + 13 и n + 15

является простым.

Рассмотрим варианты. Для n = 1 число n + 3 = 4 составное.

Для n = 2 число n + 7 = 9 составное.

Для n = 3 число n + 1 = 4 составное.

Для n > 4 все наши числа больше 5 и по крайней мере одно из них делится на 5, так как числа 1, 3, 7, 9, 13 и 15 при делении на 5 дают соответственно остатки 1, 3, 2, 4, 3 и 0, то есть все возможные остатки, откуда следует, что и числа

n + 1, n + 3, n + 7, n + 9, n + 13 и n + 15

при делении на 5 дают все возможные остатки и, следовательно, хотя бы одно из них делится на 5 и как число, большее пяти (так как n > 4), является составным.

Но для n = 4 мы получаем простые числа 5, 7, 11, 13, 17 и 19.

Ответ: n = 4.

8. Доказать, что каждое простое число вида 4k + 1 является длиной гипотенузы прямоугольного треугольника, стороны которого выражаются натуральными числами.

Согласно известной теореме Ферма каждое простое число вида 4k + 1 есть сумма двух квадратов натуральных чисел. Поэтому для такого р верно, что р = а² + b², где а и b – некоторые натуральные числа и притом различные (так как р – нечетное), например, а > b. Отсюда р² = (а² – b²)² + (2ab)², то есть р является гипотенузой прямоугольного треугольника, катетами которого являются натуральные числа а² – b² и 2ab.

Так, например,

5² = 3² + 4², 13² = 5² + 12², 17² = 15² + 8², 29² = 21² + 20².

Замечание. Другие примеры подобных троек можно найти в таблице пифагоровых чисел с наибольшим числом не превосходящим 110 и в таблице примитивных пифагоровых чисел со средними числами, не превосходящими 256.

9. Сколькими способами можно раскрасить круг, разбитый на р равных секторов с помощью n красок, если р – простое число и каждый сектор раскрашиваем одной краской? Две раскраски, совпадающие при повороте круга, считаем одинаковыми.

Каждый сектор можно раскрасить в любой из n цветов, поэтому для круга с р секторами получим n^p раскрасок, среди которых (n^p – n) не одноцветных. Каждая из этих раскрасок поворотами переходит в (р – 1) одинаковую с ней, значит, существенно различных не одноцветных раскрасок будет (n^p – n)/p, откуда общее число раскрасок равно n + (n^p – n)/p.

Ответ: n + (n^p – n)/p.

10. Доказать, что для любого простого числа p > 5 уравнение х⁴ + 4^x = p в целых числах не имеет решений.

Докажем, что если для некоторого целого значения х число

f(x) = х⁴ + 4^x

является целым, то это число либо не превосходит пяти, либо является составным.

Действительно, если х < 0, то число f(x) не целое.

Далее, при х = 0 и х = 1

f(0) = 0⁴ + 4⁰ < 5, f(1) = 1⁴ + 4¹ = 5.

Если x = 2k (k – натуральное число), то число

f(x) = 2⁴k⁴ + 4^2k = 2⁴( k⁴ + 4^2(k–1))

является составным.

Наконец, если x = 2k + 1 (k – натуральное число), то число

f(x) = x⁴ + 4·4^2k = (x⁴ + 4x²(2^k)² + 4(2^k)⁴) – 4x²(2^k)² =

= (x² + 2(2^k)²)² – (2·x·2^k)² =

= (x² + 2·x·2^k + 2(2^k)²)·( x² – 2·x·2^k + 2(2^k)²) =

= ((x + 2^k)² + 2^2k)·((x – 2^k)² + 2^2k)

так же является составным, поскольку каждый из двух сомножителей последнего произведения больше 1 (ибо 2^2k > 1 при k > 0).

Таким образом, если число p > 5 простое, то равенство х⁴ + 4^x = p не выполняется ни при каких целых значениях х.

1. Известно, что р, р + 10, р + 14 – простые числа. Найдите число р.

2. Докажите, что число

а) 2¹⁰ + 5¹²;

б) n⁴ + 64;

в) 4⁵⁴⁵ + 545⁴;

является составным.

3. Найдите все простые р для которых число р² + 14 так же будет простым числом.

4. Докажите, что уравнение х² + х + 1 = р·у имеет решение в целых числах (х, у) для бесконечного числа простых р.

5. Введём обозначение для суммы первых n простых чисел через S_n:

S_n = 2 + 3 + 5 + . . . + р_n.

Докажите, что между числами S_n и S_n+1 всегда существует число, являющееся полным квадратом.