If $(h_2(k),m) = 1$ then $h_1(k)+ih_2(k) \bmod{m}$ is a permutation of $0,\ldots,m-1$

Question

The following question appears in Introduction to Algorithms (CLRS):

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 $\langle h(k, 0), h(k, 1), \dots , h(k, m - 1) \rangle$ is a permutation of the slot sequence $(0, 1, \dots , 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, \dots, 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. The key $k$ is an integer.

Attempt: Relatively prime and co-prime is same thing. So if $h_2(k) $ is relatively prime to $m$, then $\gcd(h_2(k), m) = 1$. So, if $h_2(k)$ and $h_2(k)$ and $m$ are 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, \dots, m-1)$. If $h_2(k)$ is not relatively prime to $m$, then for the probe sequence $\langle h(k, 0), h(k, 1), \dots , h(k, m - 1)\rangle$, 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 $\langle h(k, 0), h(k, 1), \cdots , h(k, m - 1) \rangle$ is a permutation of $(0, 1, \dots , m-1)$ anyway.

Answer 1

Let's write your question more succinctly:

Let $m \geq 1$ and $a,b$ be integers. The set $S = \{ a+ib \bmod{m} : 0 \leq i \leq m-1 \}$ consists of the integers $0,\ldots,m-1$ iff $b$ is relatively prime to $m$.

Note that $S$ consists of the integers $0,\ldots,m-1$ iff the values $a+ib \bmod{m}$ are all distinct.

Suppose first that $b$ is not relatively prime to $m$. This means that we can find $c > 1$ that divides both $b$ and $m$. It follows that $a \bmod{m} = a + (m/c)b \bmod{m}$, since $(m/c)b$ is a multiple of $m$. Since $1 \leq m/c \leq m-1$, this shows that $S$ contains fewer than $m$ distinct values.

Now suppose that $b$ is relatively prime to $m$. Assume, by way of contradiction, that not all values in $S$ are distinct, say $a+ib \bmod{m} = a+jb \bmod{m}$ for some $i < j$. Then $(j-i)b \bmod{m} = 0$, where $1 \leq j-i \leq m-1$. This means that $(j-i)b$ is a multiple of $m$. Since $b$ is relatively prime to $m$, this implies that $j-i$ is a multiple of $m$, which is impossible since $1 \leq j-i \leq m-1$.