Proposition 3

Let $k$ and $n \geq 1$ be two integers. Then the following assertions are equivalent:

a) the residue class of $k$ mod $n$ is invertible in the ring $\mathbf{Z}/n\mathbf{Z}$; b) the residue class of $k$ mod $n$ generates the cyclic group $\mathbf{Z}/n\mathbf{Z}$; c) the integers $k$ and $n$ are relatively prime (I, p. 112).

Each of the conditions a) and b) means that there exists an integer $x$ such that $kx \equiv 1 \pmod{n}$, that is, there exist two integers $x$ and $y$ such that $kx + ny = 1$. This latter condition just means that $k$ and $n$ are relatively prime.