сравнение x^x = a (mod m)

[maxal]

Докажите, что сравнение $x^x \equiv a\pmod{m}$ разрешимо относительно целого числа $x$ для всех целых чисел $a$, если и только если $m$ взаимно просто с $\varphi(m)$.
(здесь $\varphi$ -- функция Эйлера)

[Sonic86]

При решений сравнения $x^x \equiv a\pmod{m}$ ясно, что достаточно ограничиться рассмотрением $x:1\leqslant x \leqslant m\varphi(m)$ в силу того, что $x^x\mod m$ периодична с периодом $m\varphi(m)$.

$\Leftarrow$: Пусть $\gcd(m, \varphi(m))=1$.
Ясно, что $x^x\equiv (x \bmod m)^{x \bmod \varphi(m)}\pmod m$. Поскольку $\gcd(m, \varphi(m))=1$, то каждому $x$ из $[1;m\varphi(m)]$ соответствует единственная пара $u=x \bmod m, v=x \bmod \varphi(m)$, причем все такие пары различны.
В результате $x^x \equiv a\pmod{m} \Leftrightarrow u^v\equiv a\pmod m, u=\overline{1,m},v=\overline{1,\varphi(m)}$, последнее сравнение имеет решение $(u,v)=(a,1)$.

$\Rightarrow$: пусть $q:q\mid m, q\mid \varphi(m), q>1$.
Рассмотрим сравнение $x^x\equiv qb\pmod m, q\nmid b, \gcd(b,m)=1$. Т.к. $q\mid m$, то $q\mid x$. $x=qy$: $(qy)^{qy}\equiv qb\pmod m$.
Если $q^2\mid m$, то сравнение не имеет решений, т.к. $q^2\mid x^x, q^2\nmid qb$.
Поскольку $(\forall q)q^2\mid m \Rightarrow q\mid\varphi(m)$, то достаточно рассмотреть $m$ свободные от квадратов.
Остается случай $q||m$: $m=qh, q\nmid h$.
$(qy)^{qy}\equiv qb\pmod m \Rightarrow (qy)^{qy}\equiv qb\pmod h$.
Так как $\gcd(qb,h)=1$, и $b$ произвольно, то, не теряя общности, заменим $qb$ обратно на $a$.
$\varphi(h)=\varphi(\frac{m}{q}), v_q(\varphi(\frac{m}{q}))=v_q(\varphi(m))\Rightarrow q\mid \varphi(h)$
Возведем сравнение в степень $\frac{\varphi(h)}{q}$, получим:
$1\equiv a^\frac{\varphi(h)}{q} \pmod h$
$h=\frac{m}{q}, m$ свободно от квадратов, значит $h$ свободно от квадратов.
$h=p_1...p_s$
Порядок группы $\mathbb{Z}_h$ равен $\prod\limits_j\operatorname{lcm} (p_j-1)$.
Сравнение $(\forall a)1\equiv a^\frac{\varphi(h)}{q} \pmod h$ верно только при $\prod\limits_j\operatorname{lcm} (p_j-1) \mid \frac{\varphi(h)}{q}$. Но $q\nmid \frac{\varphi(h)}{q}$, а $q\mid \prod\limits_j\operatorname{lcm} (p_j-1)$. Последнее следует из того, что $q\mid\varphi(h)$.
Значит существует $a$, для которого не выполняется и исходное сравнение.