Show that the $k^\text{th}$ powers of a reduced residue system form a reduced residue system if and only if $(k, \phi(m)) = 1$.

Question

Let $r_1,r_2,\ldots, r_n$ be a reduced residue system modulo $m$, where $n = \phi(m)$. Show that the numbers $r_1^k,r_2^k,\ldots,r_n^k$ form a reduced residue system modulo $m$ if and only if $(k, \phi(m)) = 1$.

I am supposed to make use of the following lemmas:

Lemma 1: Suppose that $m$ is a positive integer and that $(a,m) = 1$. If $k$ and $\overline k$ are positive integers such that $k\overline k \equiv 1 \pmod{\phi(m)}$, then $a^{k\overline{k}} \equiv a \pmod m$

Lemma 2: Suppose that $m = 1, 2, 4, p^\alpha$ or $2p^\alpha$, where $p$ is an odd prime. If $(a,m) = 1$ then the congruence $x^n \equiv a \pmod m$ has $(n, \phi(m))$ solutions or no solution, according as $$a^{\phi(m)/(n, \phi(m))} \equiv 1 \pmod m$$ or not.

I am also making use of the fact that $m$ has primitive roots iff $m = 1, 2, 4, p^\alpha$ or $2p^\alpha$.

I think I have almost proved it, here's what I have so far:

Suppose that $(k, \phi(m)) = 1$. Each $r_i^k$ is clearly a reduced residue, so we only need to show that the $r_i^k$ are distinct. Suppose that $r_i^k \equiv r_j^k$. Then their powers must be congruent, and in particular $r_i^{k\overline{k}} \equiv r_j^{k\overline{k}}$ (the fact that $(k, \phi(m)) = 1$ implies that $\overline{k}$ exists), but this implies $r_i \equiv r_j$ by Lemma 1.

Conversely, suppose that $r_1^k,r_2^k,\ldots,r_n^k$ form a reduced residue system. We consider two cases:

• Suppose $m = 1, 2, 4, p^\alpha$ or $2p^\alpha$, and consider what happens if $(k, \phi(m)) > 1$. Then by Lemma 2, we deduce that $x^k \equiv r_i$ has either $0$ or $(k, \phi(m))$ solutions, the first of which is clearly a contradiction since one of $r_j^k$ must be congruent to $r_i$. Hence, $r_i^{\phi(m)/(k, \phi(m))}\equiv 1$ for every $r_i$, which means that none of them is a primitive root. This is also a contradiction since $m$ has primitive roots.
• Suppose that $m \neq 1, 2, 4, p^\alpha$ or $2p^\alpha$. What next?

How do I prove the case where I cannot use Lemma 2?

Answer 1

Proof without group theory:

Suppose that $p|\varphi(m)$ and $p|k$. Let $q^a$ be prime such that $p|\varphi(q^a), p| k$ and $m=q^ar$ with $(q,r)=1$.

Case $1$: $q\neq 2$, then there exists a primitive root $\bmod q^a$, let $x$ be the primitive root, notice that $y=x^{\varphi(q^a)/p}$ satisfies $y^k\equiv 1 \bmod q^a$.

Case $2$: $q=2$, then $p=2$. Notice that $y=-1$ satisfies $y^k\equiv 1 \bmod q^a$.

In any case we can take $w$ so that $w\equiv y \bmod q^a$ and $w\equiv 1\bmod r$ by CRT.

Notice that $w^k\equiv 1 \bmod m$

Answer 2

Alternative proof:

We, can prove something more general.

Let $G$ be a finite abelian group, then the morphism $f:x\mapsto x^k$ is a bijection if and only if $(k,|G|)=1$.

Proof:

First suppose $(k,|G|)\neq 1$, take a prime $p$ such that $p||G|$ and $p|k$ and use cauchy's theorem to obtain an element of order $p$. Clearly the morphism will not be injective.

Now suppose $(k,|G|)=1$, factor $G$ into a product of cyclic groups $C_1\times C_2\dots \times C_n$, we must calculate the kernel. Our function is clearly $f:(x_1,x_2,\dots x_n)\mapsto (x_1^k,x_2^k,\dots x_n^k)$.

So its kernel is equal to the product of the kernels of $f_i:C_i\rightarrow C_i$ defined by $f(x_i)=x_i^k$.

The following lemma finishes the proof:

In a cyclic group $G$ of order $m$ and $k$ an integer with $(k,n)=1$ we have $g^k=e\iff g=e$.

Proof: Let $x$ be a generator and let $g=x^z$. We have $e=(x^z)^k=x^{zk}$. therefore $m|zk$, since $(m,k)=1$ we conclude $m|z$ and so $g=e$.