Let $a$, $x$ and $n$ three positive integers such that $\gcd(a,n)=1$ and $x^x=a \mod n^n$. Prove that we can find a positive integer $y$ such that $y^y=a\mod n^{n^n}$.
This is what I managed to prove :
Let $x$, $a$ and $r$ positive integers such that $\gcd(a,r)=1$ and $x^x=a\mod r$, then we can find a positive integer $y$ such that $y^y=a\mod r\frac{r}{\gcd(r,\varphi(r))}$, where $\varphi$ denote the Euler's totient function.
Proof : Let $K$ be the integer such that $a=x^x+Kr$. By Bézout, there is a positive integer $k$ such that $k\,x^x\frac{\varphi(r)}{\gcd(r,\varphi(r))}=K\mod \frac{r}{\gcd(r,\varphi(r))}$. Then $y=x+k\,\text{lcm}(r,\varphi(r))$ works.
Edit1 : Here are some details.
By binomial theorem, we have $(x+a)^{x+a}\equiv(1+a)x^{x+a}\;[a^2]$,
so $y^y\equiv (1+k\,\text{lcm}(r,\varphi(r)))x^{x+k\,\text{lcm}(r,\varphi(r))}\;[\text{lcm}(r,\varphi(r))^2]$.
Remember that $\gcd(m,n)\times\text{lcm}(m,n)=mn$.
$\gcd(r,\varphi(r))=1$, so $x^{\varphi(r)}\equiv1 \;[r]$, and by binomial theorem, $\left(x^{\varphi(r)}\right)^{\frac{r}{\gcd(r,\varphi(r))}}\equiv1 \;\left[\frac{r^2}{\gcd(r,\varphi(r))}\right]$,
so $x^{\text{lcm}(r,\varphi(r))}\equiv1 \;\left[\frac{r^2}{\gcd(r,\varphi(r))}\right]$.
Thus $y^y\equiv(1+k\,\text{lcm}(r,\varphi(r)))x^x\;\left[\frac{r^2}{\gcd(r,\varphi(r))}\right]$.
But $kx^x\,\text{lcm}(r,\varphi(r))\equiv Kr\;\left[\frac{r^2}{\gcd(r,\varphi(r))}\right]$, so $y^y\equiv a\;\left[\frac{r^2}{\gcd(r,\varphi(r))}\right]$.
Edit2 : Thanks to the link given by BillyJoe, I realized that the previous proof works with $\widetilde{\varphi}(r)$ instead of $\varphi(r)$, where $\widetilde{\varphi}(r)=\text{lcm}\left\{(p-1)p^{\nu_p(r)-1}\,,\,p\text{ prime with }p\,|\,r \right\}$, because if $r=n^n$, forall prime $p$ such that $p\,|\,r$, we have $p \,|\,\frac{r}{\gcd(r,\widetilde{\varphi}(r))}$.