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  -&gt;1
   6%24 = 6  -&gt;2
   9%24 = 9   -&gt;3
   12%24 = 12 -&gt;4
   15%24 = 15 -&gt;5
   18%24 = 18 -&gt;6
   21%24 = 21 -&gt;7
   24%24 = 0  -&gt;8
   27 %24 = 3 -&gt;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?
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)$"

These conclusions will be the core of the proof.