aとbをそれぞれnだ割った際の余りが等しくなる時がぶつかる時なので。

a mod n = b mod n
a mod n – b mod n = 0
(a – b) mod n = 0

よって、(a – b)がnの倍数であればぶつかる。