So we're using that

\(\displaystyle A^X + B^Y = C^Z \Rightarrow A^X + B^Y \equiv C^Z\ (\text{mod}\ N)\ \forall N\in\mathbb{Z},N>0\)

The contrapositive yields the test:

\(\displaystyle \text{Let}\ N\in\mathbb{Z},N>0\text{. Then}\ A^X + B^Y \not\equiv C^Z\ (\text{mod}\ N) \Rightarrow A^X + B^Y \ne C^Z\)

Of course, if we find that \(\displaystyle A^X + B^Y \equiv C^Z\ (\text{mod}\ N)\) then we cannot conclude whether or not \(\displaystyle A^X + B^Y = C^Z\).

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 \(\displaystyle \gcd(A,N) = \gcd(B,N) = \gcd(C,N) = 1\). I think we want this because: consider the set \(\displaystyle S=\{A^1, A^2, ..., A^{N-1}\}\). If \(\displaystyle \gcd(A,N) \ne 1\) 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.