I have this problem:

For what positive integers $n$ is the function $f : \mathbb{N} \to \mathbb{Z}/n\mathbb{Z}$ given by $f(x)=x^x \pmod{n}$ surjective?

I know the answer is $n$ such that $\gcd(n,\phi(n))=1$. I want to make my proof sketch more formal:

proof: n must be squarefree; if n = p²m then p can never be reached. if n and totient(n) are coprime, then by adding n enough times to x we can make the exponent do the same thing as 1, and thus reach any x desired. this is because for squarefree n, we can use chinese remainder theorem to decompose Z/nZ into prime fields, and every orbit of x ∈ Z/nZ wrt exponenting has order dividing totient(n) for reasons mostly evident but annoying to explain. as for the converse, let gcd(n, p - 1) > 1 for some p | n. then write n = pm and thus gcd(m, p - 1) > 1 too. contemplate (am)^(am) and realize that because the orbit order of am divides p - 1, exponenting by something divisible by m cannot possibly reach a primitive, as desired. (likely needs to use the fact that all groups of order n are cyclic iff gcd(n, phi(n))=1 perhaps)



Claude gave me this, can you check it's correct (please don't tell me the gcd(n, phi(n))=1 answer is incorrect because I know it is correct- note that x ranges over all natural numbers! not just up to n and x^x doesn't have period n):

Thank you for sharing your proof sketch. It's a good starting point, and I'll help you formalize it. Let's break down the proof into several steps and make each part more rigorous.
Theorem: For positive integers $n$, the function $f : \mathbb{N} \to \mathbb{Z}/n\mathbb{Z}$ given by $f(x) = x^x \pmod{n}$ is surjective if and only if $\gcd(n, \phi(n)) = 1$.
Proof:

Necessity of $n$ being squarefree:

Let's prove that if $n$ is not squarefree, then $f$ is not surjective.
Suppose $n = p^2m$ for some prime $p$ and integer $m$. Consider the equation $x^x \equiv p \pmod{n}$. This implies $x^x \equiv p \pmod{p^2}$. However, for any $x$, we have:

If $p \mid x$, then $x^x \equiv 0 \pmod{p^2}$
If $p \nmid x$, then by Euler's theorem, $x^{\phi(p^2)} \equiv 1 \pmod{p^2}$, so $x^x \equiv x^{x \bmod \phi(p^2)} \pmod{p^2}$. But $\phi(p^2) = p(p-1)$, so this can never be congruent to $p \pmod{p^2}$.

Therefore, $p$ is not in the image of $f$, so $f$ is not surjective.

Sufficiency when $\gcd(n, \phi(n)) = 1$:

Assume $n$ is squarefree and $\gcd(n, \phi(n)) = 1$. We'll prove that $f$ is surjective.
Let $n = p_1 \cdots p_k$ be the prime factorization of $n$. By the Chinese Remainder Theorem, it suffices to show that for each $i$, the function $f_i : \mathbb{N} \to \mathbb{Z}/p_i\mathbb{Z}$ given by $f_i(x) = x^x \pmod{p_i}$ is surjective.
For any $a \in \mathbb{Z}/p_i\mathbb{Z}$, consider the equation $x^x \equiv a \pmod{p_i}$. Let $g$ be a primitive root modulo $p_i$. Then there exists some $y$ such that $x \equiv g^y \pmod{p_i}$.
The equation becomes $(g^y)^{g^y} \equiv a \pmod{p_i}$, or $g^{y \cdot g^y} \equiv a \pmod{p_i}$.
Since $g$ is a primitive root, this is equivalent to:
y⋅gy≡log⁡ga(modpi−1)y \cdot g^y \equiv \log_g a \pmod{p_i - 1}y⋅gy≡logg​a(modpi​−1)
Now, since $\gcd(n, \phi(n)) = 1$, we have $\gcd(p_i, p_i - 1) = 1$ for each $i$. This means there exists an integer $z$ such that $z \cdot p_i \equiv 1 \pmod{p_i - 1}$.
Let $y = z \cdot \log_g a$. Then:
y⋅gy≡z⋅log⁡ga⋅gz⋅log⁡ga≡log⁡ga⋅(gz⋅log⁡ga)≡log⁡ga⋅az≡log⁡ga(modpi−1)y \cdot g^y \equiv z \cdot \log_g a \cdot g^{z \cdot \log_g a} \equiv \log_g a \cdot (g^{z \cdot \log_g a}) \equiv \log_g a \cdot a^z \equiv \log_g a \pmod{p_i - 1}y⋅gy≡z⋅logg​a⋅gz⋅logg​a≡logg​a⋅(gz⋅logg​a)≡logg​a⋅az≡logg​a(modpi​−1)
Thus, we've found an $x$ (namely, $g^y$) such that $x^x \equiv a \pmod{p_i}$, proving that $f_i$ is surjective for each $i$, and therefore $f$ is surjective.

Necessity of $\gcd(n, \phi(n)) = 1$:

Now, let's prove the converse: if $\gcd(n, \phi(n)) > 1$, then $f$ is not surjective.
If $\gcd(n, \phi(n)) > 1$, then there exists a prime $p$ dividing $n$ such that $\gcd(p-1, n) > 1$. Let $d = \gcd(p-1, n) > 1$.
Consider the subgroup $H = {x^n : x \in (\mathbb{Z}/p\mathbb{Z})^}$ of $(\mathbb{Z}/p\mathbb{Z})^$. The order of this subgroup divides $(p-1)/d < p-1$.
Now, for any $x$ with $p \nmid x$, we have:
xx≡xx mod (p−1)≡(xn)x/n(modp)x^x \equiv x^{x \bmod (p-1)} \equiv (x^n)^{x/n} \pmod{p}xx≡xxmod(p−1)≡(xn)x/n(modp)
This means that $x^x \bmod p$ is always in the subgroup $H$, which doesn't contain all elements of $(\mathbb{Z}/p\mathbb{Z})^*$.
For $x$ with $p \mid x$, we have $x^x \equiv 0 \pmod{p}$.
Therefore, $f$ cannot reach all elements of $\mathbb{Z}/n\mathbb{Z}$, so it's not surjective.
This completes the proof, showing that $f$ is surjective if and only if $\gcd(n, \phi(n)) = 1$.



Please write a completely sound and formal rigorous proof.