Олимпиадные задачи из источника «параграф 1. Простые числа»
параграф 1. Простые числа
НазадДоказать, что остаток от деления простого числа на 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<sup>n</sup></i> – 1 простое, то <i>a</i> = 2 и <i>n</i> – простое.
(Числа вида <i>q</i> = 2<sup><i>n</i></sup> – 1 называются <i>числами Мерсенна</i>.)
Докажите, что числа Ферма <i>f<sub>n</sub></i> = 2<sup>2<sup><i>n</i></sup></sup> + 1 при <i>n</i> > 1 не представимы в виде суммы двух простых чисел.
Пусть <i>f<sub>n</sub></i> = 2<sup>2<sup><i>n</i></sup></sup> + 1. Докажите, что <i>f<sub>n</sub></i> делит 2<i><sup>f<sub>n</sub></sup></i> – 2.
Пусть <i>a</i> и <i>n</i> – натуральные числа, большие 1. Докажите, что если число <i>a<sup>n</sup></i> + 1 простое, то <i>a</i> чётно и <i>n</i> = 2<sup><i>k</i></sup>.
(Числа вида <i>f<sub>k</sub></i> = 2<sup>2<sup><i>k</i></sup></sup> + 1 называются <i>числами Ферма</i>.)
Евклидово доказательство бесконечности множества простых чисел наводит на мысль определить рекуррентно <i>числа Евклида</i>:
<i>e</i><sub>1</sub> = 2, <i>e<sub>n</sub> = e</i><sub>1</sub><i>e</i><sub>2</sub>...<i>e</i><sub><i>n</i>–1</sub> + 1 (<i>n</i> ≥ 2). Все ли числа <i>e<sub>n</sub></i> являются простыми?
Верно ли, что все числа вида <i>p</i><sub>1</sub><i>p</i><sub>2</sub>...<i>p<sub>n</sub></i> + 1 являются простыми? (<i>p<sub>k</sub></i> – <i>k</i>-е простое число.)
Докажите неравенство <i>p</i><sub><i>n</i>+1</sub> < <i>p</i><sub>1</sub><i>p</i><sub>2</sub>...<i>p<sub>n</sub></i> (<i>p<sub>k</sub></i> – <i>k</i>-е простое число).
Пусть {<i>p<sub>n</sub></i>} – последовательность простых чисел (<i>p</i><sub>1</sub> = 2, <i>p</i><sub>2</sub> = 3, <i>p</i><sub>3</sub> = 5, ...).
а) Докажите, что <i>p<sub>n</sub></i> > 2<i>n</i> при <i>n</i> ≥ 5.
б) При каких <i>n</i> будет выполняться неравенство <i>p<sub>n</sub></i> > 3<i>n</i>?
Верно ли, что многочлен <i>P</i>(<i>n</i>) = <i>n</i>² + <i>n</i> + 41 при всех <i>n</i> принимает только простые значения?
При каких целых <i>n</i> число <i>n</i><sup>4</sup> + 4 – составное?
Докажите, что при <i>n</i> > 2 числа 2<sup><i>n</i></sup> – 1 и 2<sup><i>n</i></sup> + 1 не могут быть простыми одновременно.
Найдите все простые числа, которые равны сумме двух простых чисел и разности двух простых чисел.
Докажите, что 3, 5 и 7 являются единственной тройкой простых чисел-близнецов.
Предположим, что нашлись 15 простых чисел, образующих арифметическую прогрессию с разностью <i>d</i>. Докажите, что <i>d</i> > 30000.
Существуют ли арифметическая прогрессия, состоящая лишь из простых чисел?
Существуют ли а) 5, б) 6 простых чисел, образующих арифметическую прогрессию?
Докажите, что для любого натурального <i>n</i> найдутся <i>n</i> подряд идущих натуральных чисел, среди которых ровно одно простое.
Докажите, что существуют 1000 подряд идущих составных чисел.
Разложите на простые множители числа 111, 1111, 11111, 111111, 1111111.
Когда натуральное число имеет нечётное количество делителей?
Докажите, что составное число <i>n</i> всегда имеет делитель, больший 1, но не больший <img width="27" height="33" align="MIDDLE" border="0" src="/storage/problem-media/60461/problem_60461_img_2.gif">.
Докажите, что множество простых чисел вида <i>p</i> = 6<i>k</i> + 5 бесконечно.
Докажите, что множество простых чисел вида <i>p</i> = 4<i>k</i> + 3 бесконечно.