Блог пользователя Gampr

Автор Gampr, 12 лет назад, По-русски

Наткнулся недавно на задачу. Решить не смог, а как решать интересно)

Доказать что число 2^3^n + 1 для всех натуральных n делится на 3^(n+1), но не делится на 3^(n+2).

Источник: Приложение к кванту, "Арифметика и алгебра"

P.S. Всем спасибо, идеально.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

По индукции.

База n=0.

Для перехода раскладываем выражение как сумму кубов и доказываем, что вторая скобка делится на 3, но не делится на 9 для всех n.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Докажем по индукции. База 2^3 + 1 делится на 3^2, но не делится на 3^3. Переход 2^3^n + 1 делится на 3^(n+1), но не делится на 3^(n+2) 2^3^(n+1) + 1 = (2^3^n + 1)^3 — 3*(2^3^n + 1) — 3*(2^3^n + 1)^2 + 6*(2^3+1) = (2^3^n + 1)^3 + 3*(2^3^n + 1) — 3*(2^3^n + 1)^2 По предположению индукции получаем три слагаемых, которые делятся на 3^(n+2). Причём два из них делятся на 3^(n+3), а третье -- нет. Значит и сумма (2^3^(n+1)) делиться на 3^(n+3) не будет

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

1) Докажем что делится на 3^(n+1) для 1 это верно , пусть 2^3^n + 1 делится на 3^(n+1), докажем, что и 2^3^(n+1) + 1 делится на 3^(n+2) 2^3^(n+1)+1=(2^3^n)*(2^3^n)(2^3^n+1)-(2^3^n)*(2^3^n)+1 = (2^3^n)*(2^3^n)(2^3^n+1) — (2^3^n)(2^3^n+1) + (2^3^n+1). Потом за скобки общий множитель и должно получиться

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

x(n) = 23n + 1

для n=1 всё верно, индукция для больших n:

x(n + 1) = (x(n) - 1)3 + 1 = x(n)3 - 3x(n)2 + 3x(n)

1) все три слагаемых делятся на 3n + 2, а значит и всё делится.

2) первое и второе слагаемые делятся на 3n + 3, а третье нет, так как если бы делилось, то было бы противоречие (x(n) делилось бы на 3n + 2), а значит x(n + 1) тоже не делится.

»
12 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Укажите пожалуйста источник задачи. Спасибо.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Довольно типичная задача на ММИ. Во всех сборниках, в которых есть ММИ она есть.