How to prove if a Hash Function is collision resistant Say we have the following Hash Function, H(x) = 4x mod N where N is a number generated by multiplying two prime numbers and x={0,1,2,3,...,N-1}. So lets assume that N=15 where 15 is made from 3 and 5

How would we prove whether it is collision resistant or not? I tried manually doing it like below:

x=0; 4(0) mod 15 = 0
x=1; 4(1) mod 15 = 4
x=2; 4(2) mod 15 = 8
x=3; 4(3) mod 15 = 12
x=4; 4(4) mod 15 = 1
x=5; 4(5) mod 15 = 5
x=6; 4(6) mod 15 = 9
x=7; 4(7) mod 15 = 13
x=8; 4(8) mod 15 = 2
x=9; 4(9) mod 15 = 6
x=10; 4(10) mod 15 = 10
x=11; 4(11) mod 15 = 14
x=12; 4(12) mod 15 = 3
x=13; 4(13) mod 15 = 7
x=14; 4(14) mod 15 = 11


As you can see in the example, there are no collisions but how do you prove it Mathematically without providing numbers?
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.