Let $U = \{1, \dots, |U|\}$ and $p$ be a prime. Let $h : U \to \{0, \dots, p-1\}$ with $h(u) = (3 \cdot u) \bmod p$.
Prove that if $p > |U| \geq 4$, then $h$ is injective.
The problem comes from Computer Science where I need to show that the hash-function $h$ is collision-free, which amounts to just proving that it is injective. I know I need to show that $h(u) = h(u') \implies u = u'$ ($u, u' \in U$). Now I am stuck with $(3 \cdot u) \bmod p = (3 \cdot u') \bmod p$.
From that, how do I show that $u = u'$, using the fact that $p > |U| \geq 4$ and p is a prime?
Best Answer
This is a direct proof.
If $3u=3u'\bmod p$ then $3(u-u')=0\bmod p$. But $\gcd(3,p)=1$ (because $3$ and $p>4$ are prime, hence share no factors) so $(u-u')$ must be a multiple of $p$.
But $1\le u,u'\le|U|$, so $-|U|<u-u'<|U|$, and importantly $$-p<u-u'<p$$ and the only multiple of $p$ satisfying this is $0$. Thus $u=u'$.