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.