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.