# Is modular multiplication under a prime modulus uniformly distributed?

Given a prime $$p$$ and $$m \in Z_p^*$$.

Assume we draw $$a \stackrel{u}{\in} Z_p^*$$ uniformly at random.

Will $$a \cdot m \; mod \; p$$ be distributed uniformly over $$Z_p^*$$?

• For any $k \in Z^*_p$, the chance of getting $k$ is $1\over p-1$, because it only happens for one value of $a$, namely when $a \equiv m^{-1}k \pmod p$. Is that what you mean? – Théophile Mar 9 '16 at 19:54
• That is exactly what I mean - thanks! – joshlf Mar 9 '16 at 20:00
• Glad to help! I'll write it as an answer. – Théophile Mar 9 '16 at 20:30

Yes, the $am$ will be distributed uniformly modulo $p$. For any $k \in \mathbb Z^*_p$, the chance of getting $k$ is $\frac1 {p-1}$, because it happens for only one value of $a$, namely when $a \equiv m^{-1}k \pmod p$.
Note that if $p$ is not prime, then the same result holds only when $\gcd(m,p)=1$.