Задачи с решениями. Простые числа

Задачи с решениями. Простые числа

1. Известно, что p 3 и p  — простое число, т.е. оно делится только на единицу и на себя само. Будет ли хотя бы одно из чисел (p + 1) и (p - 1) делиться на 4? А на 5?

Решение:

На 5 ни одно из чисел может не делиться (например, при p = 13). Что же касается 4, то здесь дело другое. Рассмотрим числа p - 1, p, p + 1, p + 2. Из четырех последовательных чисел одно обязательно делится на 4, но это не p (оно простое) и не p + 2 (оно нечётное). Значит, одно из чисел p + 1 или p - 1 будет делиться на 4.

2.Докажите, что любое простое число, большее трех, можно записать в одном из двух видов: 6n + 1 либо 6n - 1, где n  — натуральное число.

Решение:

Простое число, большее 3, при делении на 6 не может давать остатки 0, 2, 3, 4  — в любом из этих случаев оно будет составным. Возможны только остатки 1 и 5. Следовательно, простое число можно записать как 6n + 1 или 6n + 5, но  6n + 5 = 6(n + 1) - 1.

3.Может ли сумма двух простых чисел быть простым числом?

Решение:   Да, может, но при условии, что одно из этих чисел будет равно 2, иначе мы получим сумму двух нечётных чисел, которая в результате будет чётным числом, следовательно, делится на 2 и не является простым.

4.Может ли сумма двух последовательных натуральных чисел быть простым числом?

Решение: 2+3=5, 3+4=7, 5+6=11, 6+7=13, 8+9=17; 5, 7, 11, 13, 17 – простые числа;

 Попробуем показать это в общем виде:

Пусть n и n+1 два последовательных натуральных числа, значит одно из них чётное и делится на 2. Тогда их сумма будет равна n+n+1 = 2n+1.

Если n2 и n – чётное, то после сокращения n на 2 получится число, большее одного. Тогда данная сумма будет равна произведению двух чисел, больших 1 и меньших её самой (одно из них – это (n+1), другое то, что получилось после сокращения n на 2). Значит, эта сумма не может быть простым числом, так как имеет делители, отличные от 1 и самой себя.

Аналогично рассматривается случай, когда n2 и n – нечётное. (В этом случае, (n+1) – чётное и большее 2.)

Остались два возможных случая: n=1 и n=2. Если n=1, то сумма будет равна  2n+1 = 2?1+1 = 3 – простое число. Если n=2, то 2n+1= 2?2+1=5 – тоже простое число.

Ответ. На основании этого можно сказать, что сумма двух последовательных натуральных чисел может оказаться простым числом

5.Может ли сумма трёх последовательных натуральных чисел быть простым числом?

Решение: Проведём рассуждения в общем виде:

Пусть n, n+1и n+2 – три последовательных натуральных числа, тогда их сумма равна n+(n+1)+(n+2) = 3n+3 = 3(n+1), т.е. всегда делится на 3, следовательно, составное число.

Ответ. Нет, не может, т.к. полученная сумма является составным числом.

6.Может ли сумма четырех последовательных натуральных чисел быть простым числом?

Решение: Пусть n, n+1и n+2 и n+3 – четыре последовательных натуральных числа, тогда их сумма равна n+(n+1)+(n+2)+( n+3) = 4n+6 = 2(2n+3), т.е. всегда делится на 2, следовательно, составное число.

Ответ. Нет, не может, т.к. полученная сумма является составным числом.

7.Может ли любое натуральное число быть представлено в виде произведения простых чисел?

Решение: Разложим число n, где n – составное число и  16≤ n

16=2?2?2?2=2⁴, 18=2?3?3=2?3², 20=2?2?5=2²?5, 22=2?11, 24=2³?3, 25=5², 26=2?13, 27=3³, 28=2²?7, 30 = 2?3?5.

Вывод: Из данного разложения замечаем, что любое указанное n может быть представлено в виде произведения, не более трёх простых множителей.

Возникает вопрос: любое ли натуральное число представимо в виде произведения простых множителей?

Ответ на поставленный вопрос даёт основная теорема арифметики:

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

8.Может ли площадь квадрата, длина стороны которого выражена натуральным числом, быть простым числом?

Решение:  Пусть а – длина стороны квадрата, тогда его площадь равна а². Отсюда следует, что площадь квадрата составное число, т.к. имеет своим делителем ещё и а. Например, если сторона квадрата равна 13, то его площадь равна 169, и 169 имеет делителями 1, 13, 169.

Ответ. Нет, не может.

9.Клиент банка забыл четырёхзначный шифр своего сейфа и помнил лишь, что этот шифр – простое число, а произведение его цифр равно 243. За какое наименьшее число попыток он наверняка сможет открыть свой сейф.

Решение: Пусть abcd – искомое число. Разложим число 243 на простые множители: 243 = 3?3?3?3?3. Тогда возможны несколько случаев:

1. 243 = 3?3?3?9, но тогда число, составленное из этих цифр будет делиться на 3 (по признаку делимости, сумма цифр равна 18, а 18 делится на 3), значит оно составное;

2. 243 = 1?3?9?9.

Из четырех цифр 1,3,9,9 можно составить следующие комбинации: 1399, 1993, 1939, 3991, 3199, 3919, 9139, 9193, 9319, 9391, 9913, 9931. По условию задачи числа должны оказаться простыми. Пользуясь таблице простых чисел, оставляем только простые числа: 1993, 1399, 3919, 9931, 9319, 9391. Остаётся 6 простых чисел, это и есть число попыток, за которое клиент банка сможет открыть сейф.

Ответ. За 6 попыток.

10..Вася умножил некоторое число на 10 и получил простое число. А Петя умножил то же самое число на 15, но всё равно получил простое число. Может ли быть так, что никто из них не ошибся?

Решение: 0,2· 10 = 2  и  0,2·15 = 3  – простые числа.

11.Четверо ребят обсуждали ответ к задаче.    Коля сказал: "Это число 9".    Роман: "Это простое число".    Катя: "Это четное число".    А Наташа сказала, что это число делится на 15. Один мальчик и одна девочка ответили верно, а двое остальных ошиблись. Какой ответ в задаче на самом деле?

Решение

Если Коля ответил верно, то обе девочки ошиблись, так как число 9 нечётное и не делится на 15. Значит, верный ответ дал Роман.  Но простое число не делится на 15, а единственное чётное простое число – это 2.

12. Докажите, что для произвольного натурального числа 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².  

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

Решение: Так как  |n² – 7n + 10| = |n –2| · |n – 5|,

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

 Этому требованию удовлетворяют n = 3 и n = 4.

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

14.Доказать, что каждое простое число вида 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.

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

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

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