Олимпиадная задача по теории чисел: эффективная конструкция для степенных сумм простых чисел

  Лемма. Пусть p – простое число. Тогда число 2ⁿ представляется в виде  a^p + b^p  тогда и только тогда, когда  n – 1  кратно p.

  Доказательство. Если  n – 1   = kp,  то  2ⁿ = (2^k)^p + (2^k)^p.

  Предположим, что  2ⁿ = a^p + b^p.  Пусть  a = 2^sk, b = 2^tm,  где k, m нечётны. Если, скажем,  s > t,  то  a^p + b^p = 2^pt(2^p(s–t)k^p + m^p),  и число 2ⁿ имеет нечётный делитель  2^p(s–t)k^p + m^p,  больший единицы, что невозможно. Значит,  s = t,  и тогда  a^p + b^p = 2^pt(k^p + m^p).  Если  p = 2,  то число  k^p + m^p  имеет остаток 2 при делении на 4, и если оно больше 2, то 2ⁿ имеет нечётный делитель  ½ (k^p + m^p),  больший 1, что невозможно. Поэтому

k = m = 1,  2ⁿ = 2·2^pt,  и  n = pt + 1,  что и требовалось.

  Если же  p > 2,  то оно нечётно, и  k^p + m^p = (k + m)(k^p–1 – k^p–2m + ... + m^p–1).   Вторая скобка нечётна и является делителем числа 2ⁿ, поэтому она равна 1; значит,  k^p + m^p = k + m,  что возможно лишь при  k = m = 1,  и тогда опять получаем  n = pt + 1.

  Пусть  P = {p₁, ..., p_n}.  Положим  x = 2^{p₁p₂...p_n+1}.  Тогда по лемме это число удовлетворяет условию задачи.

Ответ задачи отсутствует