Найдите все n, для которых 1+2^n+3^n

[rightways]

Пусть $m$ фиксированое число. Найдите все натуральные $n$ , для которых $n<7^m$ такие, что $7^m|1+2^n+3^n$.

[gris]

уточняю по непонятливости:

для $m=1 \Rightarrow n=2; n=4 (7|14; 7|98)$

для $m=2 \Rightarrow n=4; n=10; n=... (49|98;49|60074;...)$

Дальше не получается:( Правильно понял?

[rightways]

Ответ через $m$ надо будет выразить

[lel0lel]

Для фиксированного $m>1$, наименьшее, подходящее под условие $n$ равно $3\cdot 7^{m-2}+1$. Вообще, кажется, что можно описать все такие $n$ без ограничения $n<7^m$.

[mathematician123]

lel0lel в сообщении #1559943 писал(а):

Вообще, кажется, что можно описать все такие $n$ без ограничения $n<7^m$.

Нахождения всех $n < 7^m$ достаточно для определения вообще всех $n$, поскольку $\varphi(7^m) = 6 \cdot 7^{m-1}$.

[lel0lel]

mathematician123 в сообщении #1559945 писал(а):

Нахождения всех $n < 7^m$ достаточно для определения вообще всех $n$, поскольку $\varphi(7^m) = 6 \cdot 7^{m-1}$

Да, это понятно. Думал о замкнутой формуле, при желании её можно получить.

Эмпирический результат.
$m=1$, $n\in \{2, 4\}$
$m=2$, $n\in \{4, 10, 14, 16, 22, 28, 34, 40, 46\}$
$m=3$, $n\in A$, где $A:=\{22, 28, 64, 70, 98, 106, 112, 148, 154, 190, 196, 232, 238, 274, 280, 316, 322\}.$
$m>3$, $n\in 7^{m-3} (A-B)+B$, где $B:=\{1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0\}$.

[lel0lel]

Покажем например, что $n(m)=4\cdot 7^{m-1}$ подходят под условие задачи. Рассмотрим $1+2^{n(m)}+3^{n(m)}\equiv 1+2^{\frac{2 \varphi(7^m)}{3}}+3^{\frac{2 \varphi(7^m)}{3}}\pmod{7^m}$. Так как $2\cdot 3\equiv -1\pmod{7}$, то сумма $1+2^{\frac{2 \varphi(7^m)}{3}}\pmod{7^m}+3^{\frac{2 \varphi(7^m)}{3}}\pmod{7^m}$ есть сумма трёх (их всего три) решений сравнения $x^3\equiv 1\pmod{7^m}$, а эта сумма равна нулю по модулю $7^m$.

Можно рассматривать и другие подходящие $n$. Вот доказательство, что других нет должно быть хитрее. Видимо, получив полный набор $n$ для случая $m=3$ (множество $A$), нужно показать, что для $m>3$ множества подходящих $n$ связаны с $A$. Это вроде понятно как сделать: если есть делимость на $7^m$, то значит есть и на $7^{m-1}$. Но нюансы там, конечно, есть.

[lel0lel]

Запишу по-человечески:
при $m>1$ подходящие значения $n<7^m$, в порядке возрастания, следующие

$$\phantom{1} 3\cdot 7^{m - 2} + 1, 4\cdot 7^{m - 2}, 9\cdot 7^{m - 2} + 1, 10\cdot 7^{m - 2}, 14\cdot 7^{m - 2}, 15\cdot 7^{m - 2}+ 1, 16\cdot 7^{m - 2}, 21\cdot 7^{m - 2}+ 1, 22\cdot 7^{m - 2}, 27\cdot 7^{m - 2}+ 1, 28\cdot 7^{m - 2}, 33\cdot 7^{m - 2}+ 1, 34\cdot 7^{m - 2}, 39\cdot 7^{m - 2}+ 1, 40\cdot 7^{m - 2}, 45\cdot 7^{m - 2}+ 1, 46\cdot 7^{m - 2}.$$

[rightways]

А как нашли решение? Что мотивировало

[lel0lel]

Пока решения нет. Найти ответ мотивировала сама задача. Есть такая серия решений $n(k,m)=(6k+4)7^{m-2},$ $k=0,1,..,7$. Можно доказать, что она верна для любого $m>3$ по индукции. База: при $m=3$ убеждаемся, что она работает, то есть $1+2^{n(k,3)}+3^{n(k,3)}\equiv 0 \pmod{7^3}$, также проверяем, что $6^{n(k,3)}+2^{n(k,3)}+3^{n(k,3)}\equiv 0 \pmod{7^2}$. Переход с помощью формул:

$$1+2^{n(k,m+1)}+3^{n(k,m+1)}\equiv 7\cdot 6^{n(k,m)} (6^{n(k,m)}+2^{n(k,m)}+3^{n(k,m)})^2 \pmod{7^{m+1}}$$

$$6^{n(k,m+1)}+2^{n(k,m+1)}+3^{n(k,m+1)}\equiv 7\cdot 36^{{2 n(k,m)}} (1 + 2^{n(k,m)} + 3^{n(k,m)})^2 \pmod{7^{m}}$$

Возможно, что удобно перейти к рассмотрению линейных рекурсий, тогда задача будет стандартнее решаться.

[Null]

Если $(n,m)$ -решение то и $(n_1,m-1)$ - решение, где $n_1=n \pmod{6\cdot 7^{m-2}}$. Это легко доказать.
Докажем интересный факт. Если $n=4\pmod 6$, то$(n_1,m)$ - решение.(При таких ограничениях $n_1=4\pmod 6$, $2^{n_1}=2\pmod 7$, $3^{n_1}=4\pmod 7$)
Действительно пусть $1+2^n+3^n\vdots 7^m, n_1=n-6\cdot7^{m-2}k$ Надо доказать что $1+2^n+3^n-(1+2^{n_1}+3^{n_1})\vdots 7^m$

$$1+2^n+3^n-(1+2^{n_1}+3^{n_1})\vdots 7^m=2^{n_1}(2^{6\cdot7^{m-2}k}-1)+3^{n_1}(3^{6\cdot7^{m-2}k}-1)=7^{m-1}L$$

$$L=2^{n_1}\frac{2^{6\cdot7^{m-2}k}-1}{7^{m-1}}+3^{n_1}\frac{3^{6\cdot7^{m-2}k}-1}{7^{m-1}}$$

Мы имеем $2^{n_1}=2\pmod7$,$3^{n_1}=4\pmod7$, и (поля слишком коротки) $\frac{2^{6\cdot7^{m-2}k}-1}{7^{m-1}}=2k\pmod7$, $\frac{3^{6\cdot7^{m-2}k}-1}{7^{m-1}}=6k\pmod7$
А значит и $L=2\cdot 2k+4\cdot 6k=0\pmod7$

$n=2\pmod 6$ похоже только при $n=2\cdot7^{m-1}$