Let be a reduced residue system modulo m (n = ф(m)).
Show that the numbers 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 will be a reduced residue system. Then, somehow, will be a reduced residue system if (k, ф(m)) = 1.
Could anyone help me prove this? Thanks.
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 . It should be clear that the numbers form a reduced system if and only if no two of them are congruent - i.e. if and only if the map is a bijection. So it suffices to show that this map is invertible. Since , we can find integers such that . Now let . Then . So the map is invertible, and we are done.
Can you do the other direction now?
Thanks, I didn't see that.
So the other direction would go as follows:
Let
so
Let:
will form a reduced residue system if and only if no two of them are congruent modulo m , which means that the map
has to be invertible.
Which means that
because the map is invertible and f and g are inverses functions of each other
so
Thus, d must be 1.
(I am a little unsure why the last line must be true)
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 is a prime power. So now suppose the theorem holds when is a prime power.
Write . Then .
Note that, by the CRT, amongst , for every , there is a unique subset containing elements which forms a reduced system of residues modulo , such that every is congruent to 1 modulo for . Now if , we must also have . Since the theorem holds for prime powers, we must have that , for every . This implies that .