0
$\begingroup$

Why does $\{ax \mod n: a, x, n > 0 \land \gcd(a, n) = 1 \}$ is a permutation of $\{0, 1, .., n - 1\}$? I've seen some proofs, but I can't intuitively see why is that true. I like to think about euclidean algorithm etc. with two sticks of length $a$ and $b$, but even using this I still can't understand why does set of all multiplies of $a \mod n$ is a permutation of $\{0, 1, ..., n - 1\}$

$\endgroup$
2
$\begingroup$

It is enough to show that $$ x \mapsto a x \pmod{n} $$ is injective.

If $a x \pmod{n} = a y \pmod{n}$, then $n \mid a x - a y = a (x - y)$. Since $\gcd(a, n) = 1$, we have $n \mid x - y$, so $x = y$.

$\endgroup$
  • $\begingroup$ Thx. ${}{}{}{}$ $\endgroup$ – Andreas Caranti Mar 16 '17 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.