# Proof with reduced residue systems

• Nov 9th 2009, 07:34 PM
ilikecandy
Proof with reduced residue systems
Let $r_{1}, r_{2},...,r_{n}$be a reduced residue system modulo m (n = ф(m)).
Show that the numbers $r_{1}^k, r_{2}^k,..., r_{n}^k$ form a reduced residue system
(mod m) if and only if (k, ф(m)) = 1.

I am thinking of letting g be a primitive root modulo m, so that $g, g^2,... g^{\phi(m)}$ will be a reduced residue system. Then, somehow, $g^k, g^{2k},... g^{\phi(m)k}$ will be a reduced residue system if (k, ф(m)) = 1.

Could anyone help me prove this? Thanks.
• Nov 9th 2009, 09:13 PM
tonio
Quote:

Originally Posted by ilikecandy
Let $r_{1}, r_{2},...,r_{n}$be a reduced residue system modulo m (n = ф(m)).
Show that the numbers $r_{1}^k, r_{2}^k,..., r_{n}^k$ form a reduced residue system
(mod m) if and only if (k, ф(m)) = 1.

I am thinking of letting g be a primitive root modulo m, so that $g, g^2,... g^{\phi(m)}$ will be a reduced residue system. Then, somehow, $g^k, g^{2k},... g^{\phi(m)k}$ will be a reduced residue system if (k, ф(m)) = 1.

Could anyone help me prove this? Thanks.

Hint: if $G=$ is a cyclic group of order m, then $G=\Longleftrightarrow (k,m)=1$

Tonio
• Nov 10th 2009, 01:24 PM
ilikecandy
Thanks for the response, but I haven't learned what cyclic groups are in my class.
• Nov 10th 2009, 04:18 PM
Bruno J.
Your idea to use primitive root is not bad, but you have to be careful because primitive roots do not always exist. For instance if you look at a reduced system modulo 8, you will find that the square of every element is the identity! (Tonio, you should also take note of this. Your hint is misleading!)

So we need a different approach here.

Suppose $(k,\phi(m))=1$. It should be clear that the numbers $\{r_1^k,\hdots,r_n^k\}$ form a reduced system if and only if no two of them are congruent $\mod m$ - i.e. if and only if the map $f: r \mapsto r^k$ is a bijection. So it suffices to show that this map is invertible. Since $(k,n)=1$, we can find integers $x,y$ such that $xk+yn=1$. Now let $g:r\mapsto r^x$. Then $gf(r)=g(r^k)=r^{kx}=r^{1-yn}=r$. So the map is invertible, and we are done.

Can you do the other direction now?
• Nov 10th 2009, 06:03 PM
ilikecandy
Thank you very much! I am not that great with sets, so I have a question. Does $f: r \mapsto r^k$ mean that $f(r)=r^k$?
Also, how do you know that 1-yn=1, or that yn=0?
• Nov 10th 2009, 06:23 PM
Bruno J.
You are very welcome.

Yes, that is what $r \mapsto r^k$ means.

It's not quite that $yn=0$. It's because you have $r^n \equiv 1 \mod m$ (and hence that $r^{tn} \equiv 1$ also for all integers $t$). You probably know this statement in the form of Euler's theorem.
• Nov 10th 2009, 06:35 PM
ilikecandy
I meant how did you get $gf(r)=g(r^k)=r^{kx}=r^{1-yn}=r$
From $r^{1-yn}=r$?
• Nov 10th 2009, 07:32 PM
Bruno J.
Euler's theorem states that $r^{\phi(m)} \equiv 1 \mod m$. So $r^{1-yn} \equiv r\times (r^{-1})^{yn} \equiv r \times 1^y \equiv r$.
• Nov 10th 2009, 08:01 PM
ilikecandy
Thanks, I didn't see that.

So the other direction would go as follows:

Let $(k,\phi(m))=d$
so $d=kx+yn$

Let:
$f: r \mapsto r^k$
$g:r\mapsto r^x$

$\{r_1^k,\hdots,r_n^k\}$ will form a reduced residue system if and only if no two of them are congruent modulo m , which means that the map
$f: r \mapsto r^k$ has to be invertible.

Which means that $f(g(r))=g(f(r))=r^{kx}\equiv r^{d-yn}$
$f(g(r))=g(f(r)) = r$ because the map is invertible and f and g are inverses functions of each other
so $r \equiv r^{d-yn}$

$r^{d-yn} \equiv r^d * (r^{-1})^{yn} \equiv r^d * 1^y \equiv r^d \mbox{ which needs to be congruent to r }$
Thus, d must be 1.
(I am a little unsure why the last line must be true)
• Nov 11th 2009, 11:38 AM
Bruno J.
Alright, so I gave this a bit of thought and it ends up being a bit harder to prove than I initially thought. You tried reversing the argument I gave, but as you saw it doesn't really work.

I believe you need the Chinese Remainder Theorem here. I will let you prove the theorem when $m=p^\alpha$ is a prime power. So now suppose the theorem holds when $m$ is a prime power.

Write $m=p_1^{\alpha_1}\hdots p_k^{\alpha_l}$. Then $n=\phi(m)=\phi(p_1^{\alpha_1})\hdots \phi(p_k^{\alpha_l})$.

Note that, by the CRT, amongst $R=\{r_1,...,r_n\}$, for every $1 \leq j \leq l$, there is a unique subset $S_j\subset R$ containing $\phi(p_j^{\alpha_j})$ elements which forms a reduced system of residues modulo $p_j^{\alpha_j}$, such that every $x \in S_j$ is congruent to 1 modulo $p_i$ for $i \neq j$. Now if $R=R^k=\{r^k : r \in R\}$, we must also have $S_j=S_j^k$. Since the theorem holds for prime powers, we must have that $(k,\phi(p_j^{\alpha_j}))=1$, for every $1 \leq j \leq l$. This implies that $(k,\phi(p_1^{\alpha_1})\hdots \phi(p_k^{\alpha_l}))=(k,n)=1$.
• Nov 11th 2009, 01:33 PM
Bruno J.
Note that a proof using elementary group theory (Lagrange's theorem) is easy.