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