Первообразный корень

[rightways]

Докажите, что для каждого натурального $n$ существует натуральное $m$ такое, что $2^m+2008$ делится на $3^n$.

[Руст]

$2$ является образующим по модулю $3^n$ или даже 3-адическим образующим.

[megamix62]

rightways в сообщении #845827 писал(а):

Докажите, что для каждого натурального $n$ существует натуральное $m$ такое, что $2^m+2008$ делится на $3^n$.

Если $2^m=3 \mod m$, тогда $3^n \not = 2 \mod m$

[maxal]

Вообще это сразу следует из того, что $2$ является первообразным корнем по модулю каждого $3^n$. Но если хочется явную конструкцию - то вот:

Для заданного $n$ обозначим искомое $m$ через $m_n$. Понятно, что можно положить $m_1=1$.
Пусть теперь мы знаем $m_n$, тогда $2^{m_n} + 2008 \equiv k\cdot 3^n\pmod{3^{n+1}}$ для некоторого $k\in\{0,1,2\}$.

Будем искать $m_{n+1}$ в виде $m_{n+1} = m_n + t\cdot 2\cdot 3^{n-1}$, где $2\cdot 3^{n-1} = \varphi(3^n)$ -- значение функции Эйлера.
Пусть $z\in\{1,2\}$ таково, что $2^{2\cdot 3^{n-1}} \equiv 1 + z\cdot 3^n\pmod{3^{n+1}}$.

Имеем

$$2^{m_{n+1}} + 2008 \equiv k\cdot 3^n\cdot (1+z\cdot 3^n)^t - 2008\cdot ((1+z\cdot 3^n)^t - 1) \equiv 3^n\cdot (k - 2008\cdot t\cdot z)\pmod{3^{n+1}}.$$

Поэтому достаточно выбрать $t$ так, чтобы $t \equiv k\cdot z^{-1}\pmod{3}$.