1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ How much arithmetic do you know? Depending on your background, this is somewhere between a relatively simple proof using the right theorems and “it's obvious”. $\endgroup$ – Gilles 'SO- stop being evil' May 22 '12 at 19:34
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.