Наткнулся недавно на задачу. Решить не смог, а как решать интересно)
Доказать что число 2^3^n + 1 для всех натуральных n делится на 3^(n+1), но не делится на 3^(n+2).
Источник: Приложение к кванту, "Арифметика и алгебра"
P.S. Всем спасибо, идеально.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Наткнулся недавно на задачу. Решить не смог, а как решать интересно)
Доказать что число 2^3^n + 1 для всех натуральных n делится на 3^(n+1), но не делится на 3^(n+2).
Источник: Приложение к кванту, "Арифметика и алгебра"
P.S. Всем спасибо, идеально.
Название |
---|
По индукции.
База n=0.
Для перехода раскладываем выражение как сумму кубов и доказываем, что вторая скобка делится на 3, но не делится на 9 для всех n.
Докажем по индукции. База 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) не будет
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). Потом за скобки общий множитель и должно получиться
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) тоже не делится.
Укажите пожалуйста источник задачи. Спасибо.
Довольно типичная задача на ММИ. Во всех сборниках, в которых есть ММИ она есть.