How to prove if a Hash Function is collision resistant

Question

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?

Answer 1

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 < y < 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 < y$, and we know that $|x - y| < 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.

Answer 2

For this specific example, which doesn't make for a really useful hash function given that it isn't compressing, it's rather easy to prove the presence or absence of collisions.

So, assume $$H_{a,n}(x)=a\cdot x\bmod n$$ is the hash function we are looking it. Then if $H_{a,n}(x)\cdot a^{-1}\bmod n$ has a unique value, then there is exactly one input for each possible output value.

Luckily the ring of numbers $\bmod n$, also known as $\mathbb Z_n$ has been well-studied in mathematics, which allows us to know that the above value is unique if and only if $\gcd(a,n)=1$ holds.

---

As for the specific parameters in the question, we get $a=4,n=15$ and because $\gcd(4,15)=1$ no collisions occur if all inputs are in the range $0\leq x<15$.