Докажите что при любом нечетном n, 46^n + 296 * 13^n делится на 1947.
Давайте подробно докажем, что для любого нечетного n число \( 46^n + 296 \times 13^n \) делится на 1947.
Шаг 1: Анализ задачи
Нам нужно доказать, что для нечетных n: \[ 46^n + 296 \times 13^n \equiv 0 \ (\bmod \, 1947). \]
Рассмотрим число 1947. Чтобы понять его делимость и разложить на простые множители, сделаем факторизацию 1947.
Шаг 2: Факторизация 1947
Рассмотрим делители 1947.
Проверим делимость на небольшие простые числа:
- Делим 1947 на 3: \[ 1 + 9 + 4 + 7 = 21, \] кратно 3, значит 1947 делится на 3.
Вычислим деление: \[ 1947 \div 3 = 649. \]
Теперь разложим 649.
Проверим делимость на 13: \[ 13 \times 50 = 650, \] значит 649 — это \(13 \times 49\), но 49 — не простое число.
Проверим делимость 649 на 7: \[ 7 \times 92 = 644, \text{ осталось } 5, \] нет, не делится.
Проверим делимость на 17: \[ 17 \times 38 = 646, \] не совпадает.
Также попробуем 7, 11, 13 и т.д.
Давайте разложим 649 точно:
- 649 делится на 7? Нет, так как \(7 \times 92=644\), остаток 5.
- На 13? \(13 \times 49=637\), остаток 12.
- На 17? \(17 \times 38=646\), остаток 3.
Попробуем 13: \[ 649 \div 13 = 49.923... \] Нет.
Посмотрим на 7: \[ 649 \div 7 \approx 92.7, \] не делится.
Обратимся к факторизации 649 с помощью простых делителей:
- \(649 = 13 \times 50 + 19\)
- Попробуем делить 649 на 17: \[ 17 \times 38=646, \] остаток 3, не делится.
81 — не делит.
Но заметим, что \(649= 7 \times 92 + 5\), не делится.
Проверка делимости числа 649:
Делится ли 649 на 13? \[ 13 \times 49=637, \] остаток 12— не делится.
Делится ли на 17? \[ 17 \times 38=646, \] остаток 3— не делится.
Делится ли на 19? \[ 19 \times 34=646, \] остаток 3— не делится.
Как вариант, попробуем разложить 1947 иначе:
Напомню, что \(1947 = 3 \times 649\).
Обратим внимание — 649 — это число ягня:
\[ 649 \div 13 = 49.923 \] не делится.
Также 649 — это \( 7^2 \times 13 \): Давайте проверим:
\( 7^2 \times 13 = 49 \times 13 = 637 \), нет, не равно 649.
\( 13 \times 49=637 \) — рядом.
Проверим 649 делится на 13:
\[ 13 \times 49= 637, \] остается 12. Значит, 13 не делит 649.
Пока есть подозрение, что 649 — это либо простое число, либо произведение двух простых.
Проверим делимость на простых:
- 649 делится ли на 11? \[ 11 \times 59 = 649, \] Да! Вот оно.
Следовательно:
\[ 649 = 11 \times 59, \] где 11 и 59 — простые числа.
Следовательно:
\[ 1947 = 3 \times 649 = 3 \times 11 \times 59. \]
Общий вывод:
\[ 1947 = 3 \times 11 \times 59. \]
Шаг 3: Проверка делимости по модулю 3, 11, 59
Чтобы доказать что число делится на 1947, достаточно показать, что оно делится одновременно на 3, 11 и 59.
Шаг 4: Докажем, что \( 46^n + 296 \times 13^n \equiv 0 \pmod{p} \) для каждого простого делителя \( p \in \{3, 11, 59\} \) и для нечетного \( n \).
Обозначим:
\[ A(n) = 46^n + 296 \times 13^n. \]
Нам нужно показать, что для нечетных n:
\[ A(n) \equiv 0 \pmod{3}, \] \[ A(n) \equiv 0 \pmod{11}, \] \[ A(n) \equiv 0 \pmod{59}. \]
Проверка по модулю 3:
Рассмотрим выражение по модулю 3.
Заметим:
\[ 46 \equiv ? \pmod{3}. \] Так как \( 46 = 3 \times 15 + 1 \Rightarrow 46 \equiv 1 \pmod{3}\).
Аналогично:
\[ 13 \equiv 1 \pmod{3}, \] \[ 296 \equiv ? \pmod{3}. \] \[ 296 = 3 \times 98 + 2 \Rightarrow 296 \equiv 2 \pmod{3}. \]
Тогда:
\[ A(n) \equiv 1^n + 2 \times 1^n = 1 + 2 = 3 \equiv 0 \pmod{3}. \]
Получается, что:
\[ A(n) \equiv 0 \pmod{3}. \]
Это справедливо для любого n, в том числе и для нечетных.
Проверка по модулю 11:
Найдём остатки по модулю 11:
\[ 46 \equiv ? \pmod{11}. \] Так как \(11 \times 4=44\), \[ 46 - 44=2 \Rightarrow 46 \equiv 2 \pmod{11}. \]
Аналогично:
\[ 13 \equiv 13 - 11=2 \pmod{11}, \] \[ 296 \div 11 = 26 \times 11=286,\; 296-286=10, \]
то есть:
\[ 296 \equiv 10 \pmod{11}. \]
Далее:
\[ A(n) \equiv 2^n + 10 \times 2^n = (1 + 10) \times 2^n = 11 \times 2^n \equiv 0 \pmod{11}. \]
Это выражение делится на 11 для любого n, особенно для нечетных.
Проверка по модулю 59:
Рассмотри:
\[ 46 \equiv ? \pmod{59}. \]
Выразим остаток:
\[ 46 \equiv 46 \pmod{59}, \] оставим как есть.
Для 13:
\[ 13 \equiv 13 \pmod{59}. \]
Для 296:
\[ 296 \div 59 \approx 5 \times 59=295, \] \[ 296 - 295 = 1, \] поэтому:
\[ 296 \equiv 1 \pmod{59}. \]
Подставляем:
\[ A(n) \equiv 46^n + 1 \times 13^n = 46^n + 13^n \pmod{59}. \]
Получилась задача — показать, что для нечетных n:
\[ 46^n + 13^n \equiv 0 \pmod{59}. \]
Рассмотрим знаменатель. Заметим, что:
\[ 46 \equiv 46 \pmod{59}, \] \[ 13 \equiv 13 \pmod{59}. \]
Обратим внимание, что:
\[ 46 \equiv -13 \pmod{59}, \] ведь \(59 - 13=46\).
Да, получается:
\[ 46 \equiv -13 \pmod{59}. \]
Таким образом,
\[ A(n) \equiv (-13)^n + 13^n \pmod{59}. \]
Если n — нечетное число, то \((-13)^n = -13^n\). Тогда:
\[ A(n) \equiv -13^n + 13^n = 0 \pmod{59}. \]
Итак, для нечетных n,
\[ A(n) \equiv 0 \pmod{59}. \]
Итог:
- По модулю 3: \(A(n) \equiv 0\),
- По модулю 11: \(A(n) \equiv 0\),
- По модулю 59: \(A(n) \equiv 0\),
при любом нечетном n.
Так как 3, 11 и 59 — простые числа, и их произведение равно 1947, то по теореме о половинных числах:
\[ A(n) \equiv 0 \pmod{1947}, \] то есть число \(46^n + 296 \times 13^n\) делится на 1947 при любом нечетном n.
Ответ:
При любом нечетном n число \(46^n + 296 \times 13^n\) делится на 1947.
