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?

  • $\begingroup$ The reduced residue system only contains elements coprime to $m$ right? $\endgroup$ – Jorge Fernández Hidalgo Oct 9 '16 at 20:22
  • $\begingroup$ @JorgeFernándezHidalgo Yes $\endgroup$ – b_pcakes Oct 9 '16 at 20:24

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$

  • $\begingroup$ This is a bit too succinct for me. For case 1, how do we know that $k \mid \phi(q^\alpha)$? And I don't quite see how the statement of the theorem I am trying to prove follows from this. I would be happy to accept this answer if you could edit it to be a bit more rigorous and fill in some of the missing steps. Thanks $\endgroup$ – b_pcakes Oct 9 '16 at 21:36
  • $\begingroup$ It should have been a $p$ in the denominator. I proved the contrapositive of your return statement. $\endgroup$ – Jorge Fernández Hidalgo Oct 10 '16 at 5:17
  • $\begingroup$ Okay, so you've proven that if $(k, \phi(m)) > 1$ then there exists some $w$ such that $w^k \equiv 1 \pmod m$. It is still not clear to me why this implies that $r_1^k,r_2^k,\ldots,r_n^k$ is not a reduced residue system. Is it because $w \not \equiv 1 \pmod m$? $\endgroup$ – b_pcakes Oct 10 '16 at 5:36
  • $\begingroup$ yes, that's exactly it. $\endgroup$ – Jorge Fernández Hidalgo Oct 10 '16 at 5:44

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$.


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$.

  • $\begingroup$ Thanks, but I'm looking for a proof that doesn't use group theory :) $\endgroup$ – b_pcakes Oct 9 '16 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.