# Thread: Proof with reduced residue systems

1. ## Proof with reduced residue systems

Let $\displaystyle r_{1}, r_{2},...,r_{n}$be a reduced residue system modulo m (n = ф(m)).
Show that the numbers $\displaystyle 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 $\displaystyle g, g^2,... g^{\phi(m)}$ will be a reduced residue system. Then, somehow, $\displaystyle 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.

2. Originally Posted by ilikecandy
Let $\displaystyle r_{1}, r_{2},...,r_{n}$be a reduced residue system modulo m (n = ф(m)).
Show that the numbers $\displaystyle 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 $\displaystyle g, g^2,... g^{\phi(m)}$ will be a reduced residue system. Then, somehow, $\displaystyle 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 $\displaystyle G=<g>$ is a cyclic group of order m, then $\displaystyle G=<g^k>\Longleftrightarrow (k,m)=1$

Tonio

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

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

5. Thank you very much! I am not that great with sets, so I have a question. Does $\displaystyle f: r \mapsto r^k$ mean that $\displaystyle f(r)=r^k$?
Also, how do you know that 1-yn=1, or that yn=0?

6. You are very welcome.

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

It's not quite that $\displaystyle yn=0$. It's because you have $\displaystyle r^n \equiv 1 \mod m$ (and hence that $\displaystyle r^{tn} \equiv 1$ also for all integers $\displaystyle t$). You probably know this statement in the form of Euler's theorem.

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

8. Euler's theorem states that $\displaystyle r^{\phi(m)} \equiv 1 \mod m$. So $\displaystyle r^{1-yn} \equiv r\times (r^{-1})^{yn} \equiv r \times 1^y \equiv r$.

9. Thanks, I didn't see that.

So the other direction would go as follows:

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

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

$\displaystyle \{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
$\displaystyle f: r \mapsto r^k$ has to be invertible.

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

$\displaystyle 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)

10. 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 $\displaystyle m=p^\alpha$ is a prime power. So now suppose the theorem holds when $\displaystyle m$ is a prime power.

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

Note that, by the CRT, amongst $\displaystyle R=\{r_1,...,r_n\}$, for every $\displaystyle 1 \leq j \leq l$, there is a unique subset $\displaystyle S_j\subset R$ containing $\displaystyle \phi(p_j^{\alpha_j})$ elements which forms a reduced system of residues modulo $\displaystyle p_j^{\alpha_j}$, such that every $\displaystyle x \in S_j$ is congruent to 1 modulo $\displaystyle p_i$ for $\displaystyle i \neq j$. Now if $\displaystyle R=R^k=\{r^k : r \in R\}$, we must also have $\displaystyle S_j=S_j^k$. Since the theorem holds for prime powers, we must have that $\displaystyle (k,\phi(p_j^{\alpha_j}))=1$, for every $\displaystyle 1 \leq j \leq l$. This implies that $\displaystyle (k,\phi(p_1^{\alpha_1})\hdots \phi(p_k^{\alpha_l}))=(k,n)=1$.

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

### reduced residue system proof

Click on a term to search for related topics.