Задача 116644

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

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

Условие

Автор: Сендеров В.А.

Для натуральных чисел  a > b > 1  определим последовательность  x₁, x₂, ...  формулой   .   Найдите наименьшее d, при котором ни при каких a и b эта последовательность не содержит d последовательных членов, являющихся простыми числами.

Решение

  При  a = 4,  b = 2  имеем   ,   .   Осталось показать, что больше двух простых чисел подряд не встретится.
  Докажем более сильное утверждение: при  n > 2  хотя бы одно из чисел   ,     не является простым. Предположим противное; тогда
      (a – 1)(a^n–1 + ... + a + 1) = p(b – 1)(b^n–1 + ... + b + 1),     (1)
      (a – 1)(aⁿ + ... + a + 1) = q(b – 1)(bⁿ + ... + b + 1),     (2)
где p и q – простые числа.
  Пусть  a – 1  не делится на  b – 1.  Тогда некоторое простое число r входит в разложение числа  b – 1  в степени большей, чем в  a – 1.
  Из (1) и (2) следует, что r – общий делитель чисел  a^n–1 + ... + a + 1  и  aⁿ + ... + a + 1,  но  (a^n–1 + ... + a + 1,  aⁿ + ... + a + 1) = (a^n–1 + ... + a + 1, aⁿ) = 1.  Противоречие.
  Пусть число     целое. Тогда  k(a^n–1 + ... + a + 1) = p(b^n–1 + ... + b + 1),  причём  1 < k < p,  так как  b < a.  Значит,  (k, p) = 1,  поэтому
b^n–1 + ... + b + 1  делится на k. Аналогично  bⁿ + ... + b + 1  делится на k.  Но числа  b^n–1 + ... + b + 1  и  bⁿ + ... + b + 1,  очевидно, взаимно просты. Противоречие.

Ответ

d = 3.

Замечания

Двумя последовательными простыми чисел в такой последовательности могут быть любые два простых числа вида  p = b + 1,  q = b² + 1.  Действительно, полагая  a = b²,  имеем   ,   .   Такими парами являются, например,  (7, 37),  (11, 101)  и  (2⁸ + 1, 2¹⁶ + 1).

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2010-2011
Этап
Вариант	5
класс
Класс	10
Задача
Номер	10.7