Prove that if hash function $h_2(k)$ and $m$ are coprimes, then they produce a probe sequence that is a permutation of $(0, \cdots, ,m-1)$ Question: Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_1(k) + ih_2(k)) \bmod{m} $. Show that the probe sequence $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$ is a permutation of the slot sequence $(0, 1, ... , m-1)$ if and only if $h_2(k) $ is relatively prime to $m$. (Hint: See Greatest Common Divisor (GCD)).
Double hash function uses two hash functions, given that $h(k, i) = (h_i(k) + ih_2(k)) \bmod{m} $, such that integer $i$ is $i=0, \cdots, m-1$ when we probe in case of collision, so we start first with $i=0$, if there is a collision, then $i=1$ and so on until we find an empty slot. They key $k \in \mathbb{Z}$.
Attempt: Relatively prime and co-prime is same thing. So if $h_2(k) $ is relatively prime to $m$, then their $gcd(h_2(k), m) = 1$. So, if $h_2(k)$ is always co-prime to each other, we can see we always get a number between $h_2(k) \bmod{m}$ that is in slots $(0, \cdots, m-1)$. If $h_2(k) $ is not relatively prime to $m$, then for the probe sequence $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$, we might get two elements in the probe sequence that are identical to each other. This is how I approached it, so I am not sure how that will prove that $<h(k, 0), h(k, 1), \cdots , h(k, m - 1)>$ is a permutation of $(0, 1, ... , m-1)$ anyway.
 A: It seems that what you want is to show that
$$
\{a+bk\bmod m:0\le k\lt m\}\tag1
$$
goes through all $m$ residue classes mod $m$ if and only if $(b,m)=1$.

$\boldsymbol{(b,m)=1\implies}$ Covering All Residue Classes $\boldsymbol{\bmod{m}}$
If $(b,m)=1$, then Bezout's Identity says there are $x,y\in\mathbb{Z}$ so that
$$
bx+my=1\tag2
$$
In this case, $x$ is the inverse of $b$ mod $m$. Thus, for any $c$, if we let $k=x(c-a)$, we have
$$
\begin{align}
a+bk
&=a+b(x(c-a))\tag{3a}\\
&=a+(bx)(c-a)\tag{3b}\\
&\equiv a+(c-a)&\pmod{m}\tag{3c}\\
&=c\tag{3d}
\end{align}
$$
That is, $(1)$ goes through all residue classes mod $m$. That is, $a+bk$ is a surjection from the residue classes mod $m$ to the residue classes mod $m$, and a surjection from a finite set to itself is a permutation.

Covering All Residue Classes $\boldsymbol{\bmod{m}\implies(b,m)=1}$
Suppose we want
$$
a+bk\equiv a+1\pmod{m}\tag4
$$
$(4)$ says that there is an $x\in\mathbb{Z}$ so that
$$
bk+xm=1\tag5
$$
and $(5)$ says that $(b,m)=1$.
