Задача 110031

Темы:    [ Простые числа и их свойства ] [ Основная теорема арифметики. Разложение на простые сомножители ] [ Разложение на множители ]

Сложность: 3+ Классы: 8,9,10

Условие

Авторы: Произволов В.В., Сендеров В.А.

Рассматриваются 2000 чисел: 11, 101, 1001, ... . Докажите, что среди этих чисел не менее 99% составных.

Решение

Если p – нечётный простой делитель числа n, то  10ⁿ + 1 = (10^n/p)^p + 1  делится на  10^n/p + 1.  Значит, число  10ⁿ + 1  может оказаться простым лишь при
n = 2^k.  Но чисел вида 10^2k + 1  среди рассматриваемых лишь 11:  11, 101, ...,  10²¹⁰ + 1,  а  11 < 2000 : 100.

Замечания

Подозрительные числа могут оказаться и составными:  10⁴ + 1 = 73·137,  10⁸ + 1 = 17·5882353.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2000
Этап
Вариант	4
Класс
Класс	10
задача
Номер	00.4.10.1