Если a не кратно p, то существует такое число k, что a*k = 1 (mod p).

Предположим, что существуют два различных числа i и j, такие что ia = ja (mod p), где i и j находятся в пределах от 1 до p-1.

Тогда ia = ja (mod p)
(i - j)a = 0 (mod p)
(i - j)k*a = 0 (mod p) (умножаем обе части на k)
(i - j) = 0 (mod p)
i = j (mod p)

Но это противоречит нашему предположению о том, что i и j - различные числа. Следовательно, нет двух различных чисел i и j в пределах от 1 до p-1, таких что ia = ja (mod p), если a не кратно p.