Is open adressing with prime steps bijective?

Question

Who can help me with this topic: Probing with a step width that is a prime number.

I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of length m, that is, with slots numbers $0, 1, 2, \dots ,m − 1$.

We know that a function $h(k, i) = h_1(k) + i \cdot h_2(k) \mod m$ produces a permutation for every $k$ if $h_2(k)$ and $m$ are relatively prime, that is, if $\operatorname{gcd}(h_2(k),m) = 1$.

We can assume that $m, w$ be integers such that the greatest common divisor $\operatorname{gcd}(m,w) = 1$.

How can I prove that the function above

$\qquad f : \{ 0, \dots,m − 1 \} \to \{ 0, \dots,m − 1 \}\\ \qquad f(i) = i \cdot w \mod m$

is a permutation, in other words, a bijective function?

Answer 1

The following proof only uses basic modular arithmetic, and the fact that the least common multiple $\mathrm{lcm}(a,b)$ is equal to $a\cdot b$, if $\gcd(a,b)=1$.

Injectivity:

Assume there are two different $a,b\in \{0,...,m-1\}$, $a>b$, such that $f(a)=f(b)$. This means that

$$ a\cdot w \mod m = b\cdot w \mod m $$ and $$ a\cdot w=b\cdot w+k\cdot m $$ for some integer $k>0$. We reorder to $$ (a-b)\cdot w=k\cdot m $$ Both sides of the equation are a multiple of $w$ and $m$. However, since $w$ and $m$ don't share any divisor, any common multiple is larger than $w\cdot m$. The left hand side of the equation clearly contradicts this fact. Hence, there are no such choices for $a$ and $b$, and $f$ is injective.

Surjectivity

This can be argued by counting. The function $f$ is total on the set $\{0,...,m-1\}$, and since $f$ is injective as shown above, $f$ is also surjective.