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?
Best Answer
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$