$n^x\equiv x\mod 10^9$

[Alexander Evnin]

Верно ли следующее утверждение:
для любого натурального $n<100$, не кратного 10,
существует ровно одно число $x<1\,000\, 000\,000$ такое,
что последние 9 цифр числа $n^x$ образуют число $x$?

[maxal]

Нетрудно убедиться, что для любого натурального $n<100$ некратного 10 существует такое натуральное $m_n<100$, что $n^{m_n}\equiv m_n\pmod{100}$.

Для заданного $n$ определим последовательность $(q_k)_{k\geq 2}$ рекуррентным соотношением:

$$q_k = \begin{cases} m_n, & k=2;\\ n^{q_{k-1}}\bmod 10^k, & k\geq 3. \end{cases}$$

Тогда $x=q_9$ - искомое. Предлагаю доказать.

-- Thu Jan 22, 2015 09:19:48 --

Пример последовательности $q_k$ для $n=2$: A109405.

[ИСН]

Здесь это уже когда-то всплывало. Десятичность существенна; ключевым оказывался факт, что $10^k$ делится на $\varphi(10^{k-1})$.

[maxal]

ИСН в сообщении #966825 писал(а):

ключевым оказывался факт, что $10^k$ делится на $\varphi(10^{k-1})$.

Вроде надо чуть сильнее: $\lambda(10^k)\mid 10^{k-1}$ для $k\geq 3$ (где $\lambda$ - фукнция Кармайкла).

[Alexander Evnin]

Утверждение дл $q_k$ следует из свойства $q_{k-1}$ благодаря свойству
функции Кармайкла, которое Вы отметили.

Возникают естественные вопросы:

1) Ваше первое утверждение доказывается непосредственным перебором?

2) А как насчёт единственности?

[maxal]

Alexander Evnin в сообщении #966841 писал(а):

1) Ваше первое утверждение доказывается непосредственным перебором?

2) А как насчёт единственности?

Да, небольшим перебором. Им же устанавливается единственность $m_n$, из которой следует (индукцией по $k$) единственность значения $x\mod 10^k$ (и поэтому однозначно равного $q_k$).

-- Thu Jan 22, 2015 11:59:01 --

Значения $m_n$ для $n=2,3,\dots,99$:

36, 87, 96, 25, 56, 43, 56, 89, 11, 16, 53, 36, 75, 16, 77, 76, 79, 21, 96, 47, 76, 25, 76, 83, 96, 69, 31, 76, 13, 16, 75, 36, 17, 16, 59, 41, 56, 7, 56, 25, 96, 23, 36, 49, 51, 36, 73, 96, 75, 56, 57, 56, 39, 61, 16, 67, 36, 25, 16, 63, 76, 29, 71, 96, 33, 76, 75, 76, 97, 96, 19, 81, 76, 27, 16, 25, 36, 3, 16, 9, 91, 56, 93, 56, 75, 96, 37, 36

-- Thu Jan 22, 2015 12:12:16 --

Статья по теме:
J. J. Urroz, J. L. A. Yebra, On the Equation $a^x \equiv x \pmod{b^n}$, Int. Seq. 12 (2009), #09.8.8