Let $p$ be prime, and $n < p$. Then $n\times i$ "hits" every residue class for $0 < i < p$. (Searching for clean proof)

Question

Intuitively, I'm trying to show that the first $p-1$ multiples of n give every possible remainder after division by p. Or equivalently,

$$ T = \{ \; ni \mod p \; | \; i \in \mathbb{Z}, \; 1 \leq i < p\} $$

$$S = \{ a \; | \; i \in \mathbb{Z}, \; 1 \leq a < p \} $$

are equal.

Showing $T \subseteq S$ is straightforward, but my proof for $ S \subseteq T$ is two handwritten pages long and (even by my standards) convoluted.

This has the feel of well-known theorem, but I can't find it anywhere. Could someone either provide or link to a short/clean proof for the above?

Answer 1

Suppose that two numbers fell into the same bin: $a\cdot n\equiv b\cdot n\pmod p$. Then $(a\cdot n-b\cdot n)\equiv 0\bmod p$, so there's some number $c$ with $(a-b)\cdot n=c\cdot p$. Now, can you finish up from here? (This is where it's essential that $p$ is prime.)

Once you know that no two numbers fall into the same bin, then the rest is just an application of the pigeonhole principle: there are $p$ distinct equivalence classes of $a\cdot n\bmod p$ for $0\leq a\lt p$, and there are $p$ distinct representatives $\langle b\rangle$ of those equivalence classes with $0\leq b\lt p$, so the former must cover all the latter.

Answer 2

This follows from the fact that $n$ is invertible in the ring $\mathbb{Z_p}$ so you can solve the equation

$$ni = y$$

as

$$i = n^{-1}y$$