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?

  • 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$ Commented May 22, 2012 at 19:34

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


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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