**Question**: I took this question from CLRS book. 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)$ 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, 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.