proof - set of remainders of a prime p multiplied by another co prime

Question

I've solvde the problem nuggets on usaco. I came to a point that I needed to prove that:

If we have a set S that contain numbers (0,1,2,3,...P-1) where P is a prime number. If we multiplied this set * X [where X and P are co-primes (relative primes)] we will get the same set S, maybe with different arrangement, but we will get the same elements. After multiplication we will take mod P for each element in the set.

Is that any theorem, or can it be proof related to this?

Answer 1

suppose, there are i and j in (0,1,2,3,...P-1) which yield same value for lambda a: (a*x)%p.

then

i*x = j*x mod p
=> i*x - j*x = 0 mod p
=> (i - j)*x = 0 mod p

so p divides (i-j)*x. now p and x are co prime, so p does not divide x. So p | i - j

Now notice, i and j both are less than p. so i - j also less than p. So p can not divide i - j unless, it is zero. So i - j = 0 => i = j.

So if i and j yields same, i = j. So when i != j, i and j yield different integers. So for each i in (0,1,2,3,...P-1), lambda a: (a*x)%p yields different integer. So if you collect the integer in a set, the set must have p elements. But all the integers must be less than p. So the set contains each elements from (0,1,2,...P-1).

---

Remark : p does not necessarily need to be prime. All it takes, p and x to be co prime.