If $p$ is prime, show $kn$ mod $p$ cycles through all values $[0, p-1]$, where $k,n$ are integers.

Question

Let me restate the question in its entirety:

If $p$ is a prime and $n$ is an integer such that $0 < n < p$, show that the infinite sequence ($n\bmod$$p$, $2n\bmod$$p$, $3n\bmod$$p$, ...) cycles through all integer values $[0,p-1]$ in some order, then repeats.

For example, if $n = 2$ and $p = 5$, the sequence is $(2, 4, 1, 3, 0, REPEAT)$

So far, I understand why the sequence would repeat. However, I don't know how to prove that the sequence will go through every integer in $[0, p-1]$. Insight would be appreciated.

Answer 1

Consider reducing modulo $p$, in other words applying the canonical surjection from the ring of integers $\mathbb{Z}$ to its quotient $\mathbb{Z}/p\mathbb{Z}=\mathbb{Z}_p$, which is actually a field. In this field of quotients the class modulo $p$ of $n$ is invertible, as it is non-zero. Multiplication with an invertible element is a bijection on any ring, in other words if:

$A$ is a ring and $a \in A$ is invertible then the maps of left multiplication $A \rightarrow A, x \mapsto ax$ and right multiplication $A \rightarrow A, x \mapsto xa$ are bijections.