Proof with reduced residue systems

ilikecandy · #1 $Old$ November 9th, 2009, 07:34 PM

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.

tonio · #2 $Old$ November 9th, 2009, 09:13 PM

Quote:

Originally Posted by ilikecandy $View Post$

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=<g>$ is a cyclic group of order m, then $G=<g^k>\Longleftrightarrow (k,m)=1$

Tonio

ilikecandy · #3 $Old$ November 10th, 2009, 01:24 PM

Thanks for the response, but I haven't learned what cyclic groups are in my class.

Bruno J. · #4 $Old$ November 10th, 2009, 04:18 PM

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?

ilikecandy · #5 $Old$ November 10th, 2009, 06:03 PM

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?

Bruno J. · #6 $Old$ November 10th, 2009, 06:23 PM

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.

ilikecandy · #7 $Old$ November 10th, 2009, 06:35 PM

I meant how did you get $gf(r)=g(r^k)=r^{kx}=r^{1-yn}=r$
From $r^{1-yn}=r$ ?

Bruno J. · #8 $Old$ November 10th, 2009, 07:32 PM

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

ilikecandy · #9 $Old$ November 10th, 2009, 08:01 PM

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)

Bruno J. · #10 $Old$ November 11th, 2009, 11:38 AM

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

Bruno J. · #11 $Old$ November 11th, 2009, 01:33 PM

Note that a proof using elementary group theory (Lagrange's theorem) is easy.