# A power-exponential congruence equation

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$.

-
Primitive root won't work, most $n$ don't have one. –  André Nicolas Jul 24 '12 at 0:15
If $\gcd(c,n)=1$, then choose $k$ such that $c+kn\equiv1\pmod{\phi(n)}$, and you get $(c+kn)^{c+kn}\equiv c\pmod n$. Still working on $\gcd(c,n)\gt1$.... –  Gerry Myerson Jul 24 '12 at 1:14
One thing's sure: $\,n\,$ must be odd... –  DonAntonio Jul 24 '12 at 2:00
@Don, $n=2$ seems to be OK. Other even values of $n$ are ruled out by the hypothesis, $\gcd(n,\phi(n))=1$. –  Gerry Myerson Jul 24 '12 at 2:32
I think the question can be generalized with Carmichael Function in place of Euler-totient function. mathworld.wolfram.com/CarmichaelFunction.html –  lab bhattacharjee Jul 26 '12 at 5:36
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)$.
Nice solution! The core relation $a^{1+k\phi(n)}\equiv a\pmod n$ is so powerful which helps to avoid discussion in several cases..Thanks! –  user31899 Jul 24 '12 at 4:48