# Decision-LWE to Search-LWE

Regev requires $q$ to be prime on lemma 4.2 of his paper for LWE.

Why does he require that and how this effect the proof of lemma 4.2?

If $p$ is a prime, then multiplication by any non-zero value is a bijection, so a uniformly distributed $l$ maps to a uniformly distributed product $l(k-s_1)$.
If $p$ is composite, then multiplication by a value that isn't relatively prime to $p$ would not be a bijection, so a uniformly distributed $l$ might not map to a uniformly distributed product $l(k-s_1)$.