Олимпиадные задачи из источника «параграф 1. Простые числа» для 4-9 класса - сложность 2 с решениями

Доказать, что остаток от деления простого числа на 30 – простое число или единица.

Пусть <i>P</i>(<i>x</i>) – многочлен ненулевой степени с целыми коэффициентами. Могут ли все числа <i>P</i>(0), <i>P</i>(1), <i>P</i>(2), ... быть простыми?

Пусть <i>a</i> и <i>n</i> – натуральные числа, большие 1. Докажите, что если число <i>aⁿ</i> – 1 простое, то  <i>a</i> = 2  и <i>n</i> – простое.

(Числа вида  <i>q</i> = 2^<i>n</i> – 1  называются <i>числами Мерсенна</i>.)

Докажите, что числа Ферма  <i>f_n</i> = 2^{2^<i>n</i>} + 1  при  <i>n</i> > 1  не представимы в виде суммы двух простых чисел.

Пусть  <i>f_n</i> = 2^{2^<i>n</i>} + 1.  Докажите, что  <i>f_n</i>  делит  2<i>^f_n</i> – 2.

Пусть <i>a</i> и <i>n</i> – натуральные числа, большие 1. Докажите, что если число  <i>aⁿ</i> + 1  простое, то <i>a</i> чётно и  <i>n</i> = 2^<i>k</i>.

(Числа вида  <i>f_k</i> = 2^{2^<i>k</i>} + 1  называются <i>числами Ферма</i>.)

Евклидово доказательство бесконечности множества простых чисел наводит на мысль определить рекуррентно <i>числа Евклида</i>:

<i>e</i>₁ = 2,  <i>e_n = e</i>₁<i>e</i>₂...<i>e</i>_<i>n</i>–1 + 1  (<i>n</i> ≥ 2).  Все ли числа <i>e_n</i> являются простыми?

Верно ли, что все числа вида  <i>p</i>₁<i>p</i>₂...<i>p_n</i> + 1 являются простыми? (<i>p_k</i> – <i>k</i>-е простое число.)

Докажите неравенство  <i>p</i>_<i>n</i>+1 < <i>p</i>₁<i>p</i>₂...<i>p_n</i>  (<i>p_k</i> – <i>k</i>-е простое число).

Пусть  {<i>p_n</i>} – последовательность простых чисел  (<i>p</i>₁ = 2,  <i>p</i>₂ = 3,  <i>p</i>₃ = 5, ...).

  а) Докажите, что  <i>p_n</i> > 2<i>n</i>  при  <i>n</i> ≥ 5.

  б) При каких <i>n</i> будет выполняться неравенство  <i>p_n</i> > 3<i>n</i>?

При каких целых <i>n</i> число  <i>n</i>⁴ + 4  – составное?

Докажите, что при  <i>n</i> > 2  числа  2^<i>n</i> – 1  и  2^<i>n</i> + 1  не могут быть простыми одновременно.

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

Докажите, что 3, 5 и 7 являются единственной тройкой простых чисел-близнецов.

Предположим, что нашлись 15 простых чисел, образующих арифметическую прогрессию с разностью <i>d</i>. Докажите, что  <i>d</i> > 30000.

Существуют ли арифметическая прогрессия, состоящая лишь из простых чисел?

Существуют ли  а) 5,  б) 6 простых чисел, образующих арифметическую прогрессию?

Докажите, что для любого натурального <i>n</i> найдутся <i>n</i> подряд идущих натуральных чисел, среди которых ровно одно простое.

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

Когда натуральное число имеет нечётное количество делителей?

Докажите, что множество простых чисел вида  <i>p</i> = 6<i>k</i> + 5  бесконечно.

Докажите, что множество простых чисел вида  <i>p</i> = 4<i>k</i> + 3  бесконечно.

Пусть  <i>n</i> > 2.  Докажите, что между <i>n</i> и <i>n</i>! есть по крайней мере одно простое число.

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