Thanks...I should have specified though, I've only been in this number theory class for 3 weeks and we have only covered basic theorems about congruence / number theory. Nothing with fermat's little theorem / euler's theorem so I don't think it would be acceptable for me to use that in a proof.
I think we can do as follows. It will be a stronger result than what you need to prove.
Let p be any prime, and let a be an integer not divisible by p.
Consider the set . Claim: each element of S is distinct modulo p.
Proof: Suppose the opposite. Then there exist integers x, y such that and . The latter implies . So we have a product of two non-multiples of p being divisible by p; contradiction.
Now consider that there are p distinct equivalence classes in S modulo p, thus it is the set of all equivalence classes modulo p, and .