How to prove if a Hash Function is collision resistant
For the function $F(x) = ax \bmod n$, where the inputs are limited to the range $[0, n)$, this function will be a bijection (that is, no collisions) if and only if $a$ and $n$ are relatively prime.

Here is a proof in the direction you're asking about:

Suppose there exists a collision, that is, we have a pair $x, y$ with $0 \le x &lt; y &lt; n$ where $F(x) = F(y)$.  This implies that $a(x-y) \equiv 0 \pmod n$, that is, there exists an integer $k$ with $a(x-y) = kn$.  $x-y$ is not a multiple of $n$ (it is not zero, as $x &lt; y$, and we know that $|x - y| &lt; n$, hence it is not a larger multiple of $n$), hence there exists a prime power $p^k$ where $n$ is a multiple of $p^k$, but $x-y$ is not.

We know that $a(x-y)$ must be a multiple of $p^k$, hence $a$ must be a multiple of $p$, and hence $a$ and $n$ are not relatively prime.

The other direction is easier; suppose $a$ and $n$ are not relatively prime, that is, there exists a prime $p$ for which both $a$ and $n$ are a multiple.  Then, we have $F(0) = F(n/p)$, hence there exists a collision.