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 = 8So 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 ->1From 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 observationexactly 8 distinct multiples of 3 modulo 8.exactly 2 distinct multiples of 4 modulo 8exactly 1 distinct multiple of 8 modulo 8exactly 4 distinct multiples of 6 modulo 8exactly 8 distinct multiples of 6 modulo 8There are exactly LCM(n,c)/c = n/GCD(c,n)distinct multiples of c modulo nIs a better way of proving possible?
Proving that collision is less likely if the table size is prime in case modulo arithmetic is used
hash;hash tables;primes
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.