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

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.

• let's consider only h2(k) * i part, and have a = h2(k). i is 0 ... m-1. a * i is m different values, we want to prove that a * i takes each of these values exactly once. Let's assume that it is not the case. Then there are i_1 and i_2 such that a * i_1 = a * i_2 = b mod m, b is arbitrary value. But we know that if gcd(a, m) = 1 then linear congruence can have only one solution. So a * i takes m different values -> thus all values between 0 and m - 1. If i understand correctly adding h1 will just rotate these values. Sep 8, 2021 at 0:15
• see here about linear congruence: math.niu.edu/~richard/Math420/lin_cong.pdf Sep 8, 2021 at 0:16
• @effenok. Thank you very much.
– Avv
Sep 8, 2021 at 0:21
• does it work? then i will post it as answer. Sep 8, 2021 at 0:21
• i think stackoverflow generally prefers having accepted answers to questions. but if @robjohn has a better answer, he should post it. Sep 8, 2021 at 0:26

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$$.