Bijection from modular multiplication?

Question

Say we have two integers $n$ and $k$, such that $0 < k < n$ and $gcd(n, k) = 1$.

Why is it that if we take every integer $x\in\{0,\dots, n-1\}$ and compute $k\cdot x \ (mod \ n)$, we get as remainders all numbers from $0$ to $n-1$, with no repeats?

In other words, why is $\ f:\{0,\dots,n-1\}\rightarrow\{0,\dots,n-1\}$, $\ f(x)=k\cdot x\ (mod\ n)$ a bijection for $k,n\in\mathbb{N},\ gcd(k,n)=1$?

Answer 1

The assumptions imply that $k$ is invertible $\pmod n$. More precisely, Bezout tells us that $\gcd(n,k)=1$ implies the existence of integers $a,b$ such that $ak+bn=1$. We note that $ak\equiv 1 \pmod n$ so $a$ is a multiplicative inverse of $k\pmod n$.

Your claim follows at once from this. To see that a residue class $r$ is in the image of multiplication by $k$, we note that $k\times a\times r \equiv r \pmod n$. Thus the map is surjective (and as it is a map between finite sets of the same size, surjective implies bijective).

As another argument, note that the map is injective since $$k\times r_1\equiv k\times r_2\pmod n\implies n\,|\,k(r_1-r_2)$$

But, since $\gcd(n,k)=1$ this implies $n\,|\,r_1-r_2$. Again, since this is a map between finite sets of the same size, injective implies bijective.

Answer 2

See below for a few ways to prove it. $ $ OP is $\rm\, c,d = k,0\,$ below.

Theorem $\ $ The following are equivalent for integers $\rm\:c,d, n.$

$(1)\rm\ \ \ gcd(c,n) = 1$
$(2)\rm\ \ \ c\:$ is invertible $\rm\,(mod\ n)$
$(3)\rm\ \ \ x\to cx+d\:$ is $\:1$-$1\:$ $\rm\,(mod\ n),\,$ i.e. $\rm\,c\,$ is cancellable $\rm\!\bmod n,\,$ i.e. $\rm\,cx\equiv cy\Rightarrow x\equiv y$ $(4)\rm\ \ \ x\to cx+d\:$ is onto $\rm\,(mod\ n)$

Proof $\ (1\Rightarrow 2)\ $ By Bezout $\rm\, gcd(c,n)\! =\! 1\Rightarrow cd\!+\!kn =\! 1\,$ for $\rm\,d,k\in\Bbb Z\,$ $\rm\Rightarrow cd\equiv 1\!\pmod{\! n}$
$(2\Rightarrow 3)\ \ \ \rm cx\!+\!d \equiv cy\!+\!d\,\Rightarrow\,c(x\!-\!y)\equiv 0\,\Rightarrow\,x\!-\!y\equiv 0\,$ by multiplying by $\rm\,c^{-1}$
$(3\Rightarrow 4)\ \ $ Every $1$-$1$ function on a finite set is onto (pigeonhole).
$(4\Rightarrow 1)\ \ \ \rm x\to cx\,$ is onto, so $\rm\,cd\equiv 1,\,$ some $\rm\,d,\,$ i.e. $\rm\, cd+kn = 1,\,$ some $\rm\,k,\,$ so $\rm\gcd(c,n)=1$

See here for a conceptual proof of said Bezout identity for the gcd.