A little more detail, since I bothered to go learn it:

Lemma: If x and y are coprime, then the gcd of x + y and (x^n + y^n)/(x + y) divides n.

Proof: Expand out the polynomial division (note that x + y does indeed divide x^n + y^n), and then divide the result by (x + y) again, observing a remainder of ny^(n - 1). Thus, the gcd of interest is the same as gcd(x + y, ny^(n - 1)). As y^(n - 1) is coprime to x + y (by coprimeness of x and y), this is furthermore the same as gcd(x + y, n), completing the proof.

Lemma: If x^p + y^p + z^p = 0, for odd prime p, with z indivisible by p, then (x + y) and (x^p + y^p)/(x + y) are coprime p-th powers.

Proof: As z is indivisible by p, so is -z^p = x^p + y^p, and thus so is its factor x + y. At this point, invoking the above lemma and the primeness of p, we find that (x + y) and (x^p + y^p)/(x + y) are coprime; as their product is a p-th power (-z^p), we conclude they are furthermore each p-th powers.

Sophie Germain's theorem: Suppose p is an odd prime, t is a prime, and the mod-t exponent-p case of FLT is true (in the sense that there is no solution to x^p + y^p + z^p = 0 (mod t) where x, y, and z are nonzero (mod t)), but the non-modular exponent-p (A) case of FLT fails (in the sense that there IS some solution to x^p + y^p + z^p = 0 in integers, all indivisible by p, which we can assume minimal so that x, y, and z are pairwise coprime). Then p is a p-th power modulo t.

Proof: Invoking the above lemma, we have some a, b, c such that a^p = y + z, b^p = x + z, and c^p = x + y.

Furthermore, since mod-t FLT is true, we have that (precisely) one of x, y, or z is zero mod t; WLOG, let this be x. But as 2x = b^p + c^p - a^p, we can invoke mod-t FLT again to conclude that one of b, c, or a is zero mod t. It cannot be b or c, as y and z, respectively, are nonzero mod t; thus, a is zero mod t. Thus, y + z = 0 (mod t), and therefore, by expanding out the polynomial (y^p + z^p)/(y + z), we see that its integer value is equal to py^(p - 1) modulo t. As x is zero mod t, we must have furthermore that (x^p + y^p)/(x + y) must be y^(p - 1) modulo t (note that this is nonzero modulo t). As the former and latter are both p-th powers by the above lemma, so is their ratio in modulo t arithmetic, which is p, completing the proof.

We can now rephrase Sophie Germain's theorem like so: To establish the (A) case of FLT for exponent p, it suffices to find some prime t such that BOTH the mod-t exponent-p case of FLT is true AND p is not a p-th power modulo t.

Such a t is the auxiliary prime for p discussed above. Note that the truth or falsehood of this condition on t relative to p is decidable by finite search.

A couple more comments:
As a consequence of the multiplicative group modulo a prime being cyclic, we have that, for primes p and t, EVERY value is a p-th power modulo t unless t is 1 mod p. Thus, an auxiliary prime t for odd prime p must be of the form kp + 1. Furthermore, as t cannot be 2, it must be an odd prime, and therefore k must be even. Finally, we can also rule out k divisible by 3 by again invoking the cyclicity of the multiplicative group modulo t (were k divisible by 3, we would have some primitive cube root of 1 modulo t which was furthermore a p-th power; the three powers of this value would sum to zero and thus provide a counterexample to the mod-t exponent-p case of FLT). So when searching for auxiliary t to prime p, we are looking for primes of the form kp + 1 where k is an even value not divisible by 3; for all such k up through 16, Germain and Legendre managed to prove that conversely, whenever kp + 1 is prime, it satisfies all the conditions to be an auxiliary prime for p (with a slight exception for the two cases where p = 3 and k is 14 or 16), which provides auxiliary primes for each p < 197; however, at p = 197, one must go beyond this, to a minimal k of 38.

I do not at the moment know if there are auxiliary primes for each p (and I suspect no one does?), nor how one goes about showing that, for various k, kp + 1 is automatically an auxiliary prime whenever prime (or whether this generalizes beyond k = 16). Oh well. More to learn, always.