Recently, I became aware of this result:
$\textbf{Theorem 1:}$ if $n>1$ and $a$ is relatively prime to $n$, then there exists an integer $x$ such that $x^x \equiv a\pmod n$.
I found the proof of this theorem on this page (at the bottom of the page), but I was not able to fully understand it, could you help me?
It goes as follow:
$\textbf{Proof 1:}$ let us introduce an intermediate lemma.
-
$\textbf{Lemma:}$ if $m\in\mathbb{N}^*$ is such that $\gcd(m,\varphi(n))=1$, then $0^m,1^m,2^m,\dots,(n-1)^m$ is a permutation of $0,1,2,\dots, n-1$ (modulo $n$). ($\textbf{Edit:}$ as noticed by @metamorphy, the lemma only hold when $n$ is square-free)
-
$\textbf{Proof of the lemma:}$ Let $p$ be a prime divisor of $n$. If $a,b$ are such that $a^m\equiv b^m\pmod{n}$, then in particular $a^m\equiv b^m\pmod{p}$. Because $\gcd(m,\varphi(n))=1$, we have $\gcd(m,\varphi(p))=1$, so there exists $\lambda,\mu\in \mathbb{Z}$ such that $\lambda m + \mu \varphi(p) = 1$. As a result, $$a\equiv a^{\lambda m + \mu \varphi(p)}\equiv b^{\lambda m + \mu \varphi(p)}\equiv b\pmod{p}$$
Note that we can lift $a$ and $b$ to the power $\lambda m$ and $\mu \varphi(p)$ because both $a$ and $b$ are $\equiv 0$ or they are both invertible modulo $p$ (as $p$ is a prime).
There, I don't understand how we conclude:
Using the Chinese Remainder Theorem, we conclude that $a\equiv b\pmod{n}$, which proves the lemma.
I also don't understand the next part of Proof 1: For every $m\in \mathbb{Z}/p\mathbb{Z}$, let
$$\delta(m) :=\{m+p,m+2p,\dots, m+p(p-1), m+p^2\}\quad \pmod{\varphi(p) = p-1}$$
Consider all pairs (which pairs? what does it precisely mean in this context?) of equation $x^{m_1}\equiv a\pmod{p}$ where $m_1\in \delta(x)$. Clearly, all such $x$ work (Why does it "clearly" work?) and once we have obtained all pairs $x_1,x_2,\dots,x_{w(n)}$ (what is $w(n)$?), we use Hensel's Lemma to lift these solutions to $p^{v_p(n)}$ (How do we precisely apply Hensel Lemma here?) and finish by Chinese Remainder Theorem.
$\textbf{End of Proof 1}$
As you can see, there are many point where I couldn't catch what the author wanted to say. It's been a few days and I still don't understand. If someone could help me, I would really appreciate it.
Thanks.
Best Answer
Thanks to @metamorhpy, I found an answer to my question here. I detail it there.
We will prove that if $a\geq 0$ and $n\geq 0$ are integers such that $\gcd(a,n) =1$, then the equation $x^x \equiv a\pmod{n}$ always has a solution $x\in\mathbb{N}$.
We proceed by induction on the greatest prime divisor of $n$ (denoted by $\Omega_n$ in the following proof). We also denote the Chinese Remainder Theorem by CRT.
$\textbf{Initialisation:}$ For $n=1$, $a=0$ verifies $\gcd(a,n) = 1$, and $x=1$ works.
$\textbf{Induction:}$ Let $K>1$ be such that for all $n$ such that $\Omega_n<K$, for all $a\in \mathbb{N}^*$, $$\gcd(a,n)=1 \;\Rightarrow\; x^x\equiv a\pmod{n}\quad \text{has a solution.}$$ We take $n=p^k\cdot m$, where $\Omega_n = p$ is the smallest prime bigger than $K$, $k\geq 1$, and $\Omega_m < K$.
We also take $a\in \mathbb{N}$ which is relatively prime to $n$. We have $\gcd(a,m)=1$.
Moreover, let $r$ be the product of $q^{v_q(p-1)}$ where $q$ is a prime number that divides both $m$ and $p-1$.
$\gcd\left(\frac{p-1}{r},m\right) = 1$ so we can take $a\equiv 1\pmod{\frac{p-1}{r}}$. Applying CRT, we get that $\gcd(a,(p-1)m)=1$.
As $\Omega_{(p-1)m}<K$, there exists $x\in\mathbb{N}^*$ such that $x^x\equiv a\pmod{(p-1)m}$ $\color{red}{(i)}$.
We are now looking for $y\equiv x\pmod{(p-1)m\cdot\varphi((p-1)m)}$ $\color{red}{(ii)}$ such that $y^y\equiv a\pmod{p^k}$.
Notice that $\color{red}{(ii)}$ implies $y^y\equiv a\pmod{m}$. $\color{red}{(ii)}$ also implies that $y\equiv x\pmod{p-1}$, so $y^y\equiv a\pmod{p}$ is equivalent to $y^x\equiv a\pmod{p}$. Considering that $\gcd(x,p) = 1$, $y\mapsto y^x$ is a bijection modulo $p$, so there exists a unique $y_1$ modulo $p$ such that $y_1^{y_1}\equiv a\pmod{p}$.
We are now looking for $y$ such that $y\equiv x\pmod{(p-1)m\cdot\varphi((p-1)m)}$ and $y\equiv y_1\pmod{p}$.
The two conditions $y\equiv x\pmod{p-1}$ and $y\equiv y_1\pmod{p}$ merge into $y\equiv a_1\pmod{p(p-1)}$ where $x_1$ is inversible modulo $p(p-1)$ and is given by CRT. $y^y\equiv a\pmod{p^2}$ becomes $y^{x_1}\equiv a\pmod{p^2}$, which has a unique solution $y_2$ (again, because $x_1$ is relatively prime to $p^2$, so $y\mapsto y^{x_1}$ is a bijection from and to the group of invertibles modulo $p^2$.)
Following this process, we find $y_1,y_2,\dots, y_k$, with at last $$ y\equiv y_k\pmod{p^k}\quad \Rightarrow\quad y^{y}\equiv a\pmod{p^k}$$ Using CRT (remember that we already have $y^y\equiv a\pmod{m}$), we are able to construct $y$ such that $y^y\equiv a\pmod{p^k\cdot m = n}$, which concludes the proof.
Thanks for reading and sorry for my bad english.