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.