# hash – If the second function in double hashing \$h_2(k)\$ and \$m\$ are relatively primes, then the probe sequence that is a permutation of \$(0, cdots, ,m-1)\$

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 $$$$ 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 $$$$, 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 $$$$ is a permutation of $$(0, 1, … , m-1)$$ anyway.