# Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets,

  where m = table_length/GreatestCommonFactor(table_length, x)


Can someone help me to prove the above equation.

 Example for the above question would be:
x = 3, table_length = 24
m = 24/gcd(3,24) = 24/3 = 8

So 3%24 = 3  ->1
6%24 = 6  ->2
9%24 = 9   ->3
12%24 = 12 ->4
15%24 = 15 ->5
18%24 = 18 ->6
21%24 = 21 ->7
24%24 = 0  ->8
27 %24 = 3 ->1


From the above equation inference can be drawn that when

   table_length/GreatestCommonFactor(table_length, x) is 1,


i.e when x and table_length are co-prime, the distribution would be proper and will cover all the buckets.

Based on observation

exactly 8 distinct multiples of 3 modulo 8.
exactly 2 distinct multiples of 4 modulo 8
exactly 1 distinct multiple of 8 modulo 8
exactly 4 distinct multiples of 6 modulo 8
exactly 8 distinct multiples of 6 modulo 8


There are exactly LCM(n,c)/c = n/GCD(c,n)distinct multiples of c modulo n

Is a better way of proving possible?

• What have you done to try to solve this on your own? We expect you to make a serious effort and to show your work. Have you tried to do some small examples to see what happens? What have you tried, to prove it? What kind of "proof" are you looking for? What is the context and motivation for your question? This is not a "homework help" site where you paste your exercise and we solve it for you. Are you familiar with modular arithmetic, modular inverses, for which constants $c$ the function $f(x) = cx \bmod n$ is bijective, and related topics?
– D.W.
Feb 26 '14 at 10:20
• I have made the effort,and as such the problem is now reduced to. How many distinct multiples of x modulo n are there? Feb 26 '14 at 10:52
• You show one case. It doesn't prove the general case. Feb 26 '14 at 13:03
• Ya, i am asking for a proof!! I couldn't come up with one. Above equatoin can be deduced based on observation. Feb 26 '14 at 15:58

It requires Theorem 31.20 on Page 927 from the CLRS (for which there is a proof of the theorem on the same page) that "if $d = gcd(a, n)$ then $\langle a\rangle = \langle d \rangle = \{0, d, 2d, \ldots, ((n/d) -1)d\}$ in $\mathbb{Z}_n$, and thus $|\langle a\rangle| = n/d$"
But it's Corollary will be more useful to the proof: "The equation $ax \equiv b \mod n$ is solvable for the unknown $x$ if and only if $d|b$, where $d = gcd(a, n)$"