Prove that $x^x\equiv k \mod n$ has integer solutions for every integer $k$ iff $gcd(n,\phi(n))=1$.

Question

Prove that $x^x\equiv k \mod n$ has integer solutions for every integer $k$ iff $gcd(n,\phi(n))=1$.

I know that if $x^x\equiv k \mod n$ has integer solutions then the least positive solution is less than $n\phi(n)$.

Answer 1

$x^x ≡ k \mod n$

One particular case for the condition $gcd (n, \phi(n))=1$ is when n is prime, because in this case $\phi(n)=(n-1)$. Suppose $x=n-1$, then we have:

$x^{n-1}≡1 \mod n$ ⇒ $\frac{x^n}{x}≡1 \mod n$.

Multiplying both sides by x we get:

$x^n ≡x \mod n$ ⇒ $x^{x+1} ≡ x \mod n$ ⇒ $x^x ≡ \frac{x}{x} \mod n$ ⇒ $x^x ≡ 1 \mod n≡(1-n) \mod n$

We may let $(1-n)=k$ and conclude that $x^x≡ k \mod n$

In this particular case the value of k is $1-n$, so for any $\{k=1-n, x=n-1; n.. prime\}$ we can write a relation such as $x^x≡k\mod n$

This argument can be applied for when $gcd (n. \phi(n))=1$; in this case n is replaced by $\phi(n)$ and we let $x=\phi(n)-1$ and we have:

$x^{\phi(n)} ≡x \mod n$ ⇒ $x^{x+1} ≡x \mod n$ ⇒ $x^x ≡1\mod n≡(1-n)\mod n$