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

Натуральное число, большее 1, называется простым, если оно делится только на 1 и на само себя. Натуральное число называется составным, если оно имеет больше двух различных делителей.

Принято считать, что число 1 не относится ни к простым, ни к составным числам.

Отсюда следует, что множество натуральных чисел можно разбить на такие три подмножества: множество простых чисел, множество составных чисел и множество содержащее единственный элемент 1.

Справедлива следующая теорема.

Любое натуральное число, большее 1, можно и притом единственным образом представить в виде произведения простых чисел.

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

Среди простых делителей натурального числа могут быть равные, и их произведение можно записать в виде степени. Тогда разложение натурального числа а на простые множители можно представить в следующем виде:

a = p₁ ^k1 p₂ ^k2 … p_n^kn ,

где p₁, p₂,…, p_n - различные простые числа, k1, k2,…, kn – натуральные.

Задачи

5.17.К двузначному числу приписали такое же число. Может ли полученное число быть простым?

5.18. К числу, являющемуся произведением двух последовательных натуральных чисел, приписали справа число 21. Докажите, что полученное число – составное.

5.19. Натуральные числа a и b таковы, что 31a = 54b. Докажите, что число a + b – составное.

Решение.

Так как число 31а делится на 54 и числа 31 и 54 – взаимно простые, то а делится на 54: a = 54n; где nÎN. Тогда

31 54 n = 54b, b = 31n.

Отсюда a + b = 54n + 31n = 85n, а следовательно, число a + b является составным.

5.20. Натуральные числа a и b удовлетворяют условию 15a = 32b. Может ли число a – b быть простым? Если может – постройте пример; если не может – докажите.

5.21. Назовите все натуральные n, при которых число n⁴ + 4 –составное.

Решение.

Попробуем разложить выражение n⁴ + 4 на множители с целыми коэффициентами. Мы привыкли к тому, что сумма квадратов на множители с целыми коэффициентами не раскладывается. В данном случае это делается с помощью приема «плюс – минус» следующим образом:

n⁴ + 4 = (n⁴ + 4 + 4n²) - 4n² = (n² + 2)² - 4n² = (n² + 2n + 2)( n² - 2n + 2).

Очевидно, множитель n² + 2n + 2 всегда больше 1. Второй множитель n² - 2n + 2 может быть равным 1:

n² - 2n + 2 = 1, n² - 2n + 1 = 0, (n – 1)² = 0, n = 1.

Так как при n = 1 множитель n² + 2n + 2 принимает значение 5, являющееся простым числом, то значение n = 1 нужно отбросить.

Ответ: все n не равные 1.

5.22. Докажите, что любое число вида а = 101010…101 (n нулей, n + +1 единица, где n > 1) – составное.

Решение.

Преобразуем число а, учитывая, что всего у него 2n + 1 цифр, а следовательно, первая единица – разряда 2n:

a = 101010…101 = 10²ⁿ + 10^2n-2 + 10^2n-4 +…+ 10² + 1 =

= (1/(10² -1))(10² – 1)(10²ⁿ + 10^2n-2 +…+10² +1) =

= (1/99)(10²ⁿ⁺²-1) = (1/99)((10ⁿ⁺¹)² – 1) = (1/99)(10ⁿ⁺¹+1)( 10ⁿ⁺¹-1).

Теперь рассмотрим два случая.

1. Пусть n четно.

Тогда сумма 10ⁿ⁺¹+1 делится на 11, причем частное от такого деления больше 1, так как 10ⁿ⁺¹+1 >11; разность 10ⁿ⁺¹-1 делится на 9, причем частное также больше 1, так как 10ⁿ⁺¹+1 >11; разность 10ⁿ⁺¹-1 делится на 9, причем частное также больше 1. Получилось составное число

а = ((10ⁿ⁺¹+1)/11) ((10ⁿ⁺¹-1)/9).

2. Пусть n нечетно.

В этом случае разность 10ⁿ⁺¹-1 делится на 10² – 1= 99 и частное больше 1, поскольку 10ⁿ⁺¹-1 > 99.

5.23. Докажите, что все числа вида

10001,100010001,1000100010001,…

• составные.

5.24. Докажите, что число 8(3^5k + 5⁵ⁿ) – 5 при любых натуральных k и n является составным.

5.25. Какое наибольшее число простых чисел может быть среди 15 последовательных натуральных чисел, больших 2?

Решение.

Очевидно, простые числа нужно искать среди нечетных. Из 15 последовательных натуральных чисел имеется 7 или 8 нечетных. Среди любых трех последовательных натуральных чисел ровно одно делится на 3, поэтому среди 7 или 8 последовательных нечетных натуральных чисел имеется 2 или 3 числа, делящихся на 3. Если их отбросить, то останется 5 или 6 нечетных чисел.

Нужно еще убедиться, что такие 6 простых чисел возможны. Например, если взять такие 15 последовательных натуральных чисел: 3, 4, 5, 6,…, 17, то среди них – 6 простых. 3, 5, 7, 11, 13, 17.

О т в е т: 6.

5.26. Составьте из простых чисел все возможные арифметические прогрессии с разностью 6 и числом членов, большим 4.

5.27. Докажите, что все числа p, p + 2, p + 4 являются простыми только в случае, когда они образуют тройку 3, 5, 7.

Решение.

Рассмотрим несколько случаев, в зависимости от p.

При p = 2 число p +2 = 4 – составное, поэтому значение p = 2 отпадает.

При p = 3 получим тройку 3, 5, 7, о которой упоминается в условии задачи.

При p = 5 число p + 2 = 7 – простое, но число p + 4 = 9 – составное, значит, p = 5 нужно отбросить.

При p = 7 число p + 2 = 9 – составное.

При p = 11 число p + 4 = 15 – тоже составное.

Возникает предположение, что подходит только p = 3. Докажем его.

Нетрудно заметить, что значение p = 5, p = 7, p = 11 не подходили потому, что или p + 2 или p + 4 делятся на 3. Убедимся, что так будет всегда при простом p>3.

Простое число, большее 3, не делится на 3 и, следовательно, при делении на 3 может давать в остатке только 1 или 2. Рассмотрим оба случая.

1. Пусть p при делении на 3 дает в остатке 1: p = 3k + 1 (kÎN). Тогда число p + 2 = (3k + 1) + 2 = 3k = 3 делится на 3, причем частное от этого деления больше 1. Значит число p + 2 составное.

2. Пусть p = 3k + 2 (kÎN). Тогда число p + 4 = (3k + 2) + 4 = 3k + 6 – составное.

5.28. Найдите все такие p, что числа p, p + 10 и p + 20 – простые.

Задачи этого пункта – это, по существу, числовые ребусы. Своеобразие таких задач в том, что одна из двух компонент действия получается из другой путем перестановки или зачеркивания цифр.