So we're using that

The contrapositive yields the test:

Of course, if we find that

then we cannot conclude whether or not

.

I'm guessing that A,B,C are small enough such that "N is large" means N is greater than A,B,C. This would mean that choosing N prime implies

. I think we want this because: consider the set

. If

then there must be duplicates in S mod N. The number of distinct elements of S is maximized (probabilistically) for N prime. See

A046144 at OEIS; the sequence is the number of primitive roots of n. So thinking in terms of probability, choosing N prime basically increases the population size, thus giving lower probability that two randomly chosen elements add to a third element, thus giving higher probability that the test will successfully weed out false equations.

Anyone else care to validate my reasoning? I'm a little unsure.