Residues of powers modulo a squarefree integer

Question

The following is an idle question on powers modulo composites. I find it natural and have no clue how to answer it. I am a beginning undergraduate, please include as many details as possible.

Setting : Let $n$ be an odd square-free composite integer. The ring $\mathbb{Z}/n\mathbb{Z}$ is thus not a field, and has cardinality $n$.

Let $k$ be any fixed integer between $1$ and $n$. Consider the $n$ powers : $0^k, 1^k,\dots, (n-1)^k$.

Questions :

a) is there a way to count explicitly the number of distinct values mod $n$ of these powers as a function of $n$ and $k$? Or maybe from the list of prime factors of $n$ and $k$?

b) better yet, is there a way to compute those values?

Remark: For a related (yet different) question, if $n = p$ is prime and $k=p$, then $a^p = a$ mod $p$: this is just Fermat's little theorem.

Answer 1

In principle, the answer to $a$ is "yes" (but it's perhaps a bit complicated), and the answer to $b$ is "not really".

First, reduce this to a question of primes by studying $\mathbb{Z}/p\mathbb{Z}$ for each prime $p \mid n$, and then use the Chinese Remainder Theorem to recombine to $\mathbb{Z}/n\mathbb{Z}$.

Now for each $p$, consider the $k$-power map $f$ from the multiplicative subgroup $(\mathbb{Z}/p\mathbb{Z})^\times \longrightarrow (\mathbb{Z}/p\mathbb{Z})^\times$, given by $f(x) = x^k \bmod p$. This is a homomorphism, so to find the size of the image it suffices to find the size of the kernel.

This group is cyclic, so there is some $a$ such that $(\mathbb{Z}/p\mathbb{Z})^\times = \langle a \rangle$. The kernel of the map $f$ in terms of $a$ consists of those elements $a^n$ such that $a^{nk} \equiv 1 \bmod p$. This occurs exactly when $nk$ is a multiple of $\varphi(p) = (p-1)$ (Fermat's Little Theorem and Carmichael's Theorem). Thus the kernel of the map $f$ consists of elements $a^n$ such that $nk \equiv 0 \bmod (p-1)$, or $nk = \alpha (p-1)$ for some integer $\alpha$. We may assume $1 \leq n \leq p-1$, as each element of $(\mathbb{Z}/p\mathbb{Z})^\times$ is given by one such $a^n$.

If $\gcd(k, p-1) = 1$, then necessarily $(p-1) \mid n$, which implies that $n = (p-1)$. In this case the only $a^n$ such that $a^{nk} \equiv 1 \mod p$ is $a^{p-1} \equiv 1 \bmod p$. Thus the size of the kernel is $1$, and so the image has size $p-1$. All numbers mod $p$ are $k$th powers.

More generally, if $\gcd(k, p-1) = d$, then $f(a^{\frac{p-1}{d}}) = 1$, and this is also true of the $d$ powers of $a^{\frac{p-1}{d}}$ up to $a^{p-1}$. The size of the kernel is $d$, and thus the size of the image is $\frac{p-1}{d}$. (This completely misses which $\frac{p-1}{d}$ elements are in the image).

Thus to fully answer $(a)$, factor $n$ and compute $$ \prod_{p \mid n} \big(1 + \frac{p-1}{\gcd(k, p-1)}\big).$$ This is because the image in $(\mathbb{Z}/p\mathbb{Z})^\times$ has $\frac{p-1}{\gcd(k, p-1)}$ elements, and $0$ is in the image (giving $+ 1$). And then CRT gives the product.

---

For example: consider $n = 15$ and $k = 4$. Then $15 = 3 \cdot 5$. We have that $(3-1)/\gcd(4, 3-1) = 1$ and $(5-1)/\gcd(4, 5-1) = 1$. Thus the image should be of size $(1 + 1)(1 + 1) = 4$. And if we explicitly compute these elements, they are $0, 1, 6, 10$.