Let $n \in \mathbb{N}$ with $(n,\varphi(n))=1$ , where $\varphi$ is the Euler-totient function. Prove the equation $x^x \equiv c \pmod{n}$ has integer solution for all $c \in \mathbb{N}$
My thought: By Euler's theorem one has $\varphi(n)^{\varphi(n)} \equiv 1 \pmod{n}$, so I need to find an $x$ such that $x^x \equiv c \varphi(n)^{\varphi(n)} \equiv c \pmod{n}$. It seems one needs to consider the primitive roots $\bmod(n)$ somehow, but $c$ may not be coprime to $n$.
Best Answer
First, note that the hypothesis $\gcd(n,\phi(n))=1$ implies that $n$ is a product of distinct primes (since $p^2\mid n$ implies $p\mid\phi(n)$).
Now we deduce that $${\rm if\ }\gcd(n,\phi(n))=1{\rm\ then\ }a^{1+k\phi(n)}\equiv a\pmod n{\rm\ for\ all\ }k.$$ Let $p$ be a prime dividing $n$. If $a\equiv0\pmod p$, then surely $a^{1+k\phi(n)}\equiv a\pmod p$, since both sides of the congruence are zero. If $\gcd(a,p)=1$, then $$a^{1+k\phi(n)}=a^{1+k'(p-1)}=a\bigl(a^{p-1}\bigr)^{k'}\equiv a\pmod p$$ for some integer $k'$. Thus we have $a^{1+k\phi(n)}\equiv a\pmod p$ for all primes $p$ dividing $n$. Since these primes are pairwise coprime, and since $n$ is their product, $a^{1+k\phi(n)}\equiv a\pmod n$ follows by the Chinese Remainder Theorem.
Now, given $c$, choose $k$ such that $1+k\phi(n)\equiv c\pmod n$. Again, the hypothesis $\gcd(n,\phi(n))=1$ guarantees $k$ exists. Now $$(1+k\phi(n))^{1+k\phi(n)}\equiv c^{1+k\phi(n)}\equiv c\pmod n$$ and we are done; we have shown we can take $x=1+k\phi(n)$.