## On Case 1 of Fermat's Last Theorem

```Fermat's Last Theorem asserts that the equation x^p + y^p = z^p has no
solution in integers x,y,z and prime p.  Traditionally this proposition
was split into Cases 1 and 2, depending on whether xyz is not or is
divisible by p.

Case 1 is by far the simpler, and with the exponent p=3 turns out to
be trivial.  Here the assertion is that the equation x^3 + y^3 = z^3
has no solution in integers x,y,z assuming none of them is divisible
by 3.  This can trivially be ruled out by just examining the equation
modulo 9.  Similarly, it's trivial to show that x^5 + y^5 = z^5 has
no solutions modulo 25 if none of x,y,z is divisible by 5.  The same
applies to many other primes.  This is related to the elementary fact
(noted by Gauss) that if the congruence

x^p + y^p  =  (x+y)^p    (mod p^2)

has no "non-trivial" solutions (meaning that none of x, y, (x+y)
are zero modulo p) then Case 1 of FLT is true for the prime exponent
p.  Unfortunately, if p is of the form 3k+1 there are always non-
trivial solutions, so the observation isn't of much value for such
primes.  However, for the first several primes of the form 3k-1 it's
easy to verify that there are no solutions.

Incidentally, since division by non-zero residue is unique modulo p
(and recallling that an algebraic factor of p can be cancelled), we
can divide through any solution of the above congruence by x^p, and
so setting z=y/x we have the congruence (1+z)^p - z^p  - 1 = 0
(mod p^2).  Thus we need only examine this simpler form to check
for possible solutions.  For a more extensive discussion of this
congruence, see the note On the Density of Some Exceptional Primes.

G.B Mathews (1885) took up this idea and evidently concluded that
it settles Case 1 of FLT for ALL prime exponents of the form 3n-1.
Dickson seems to agree, saying that the method "leaves in doubt the
case p=3n+1".  Later, in his review of A. Flechsenhaar's 1909 paper
on the Fermat equation modulo p^2, Dickson flatly claims that the
congruence has no solutions for primes of the form p=6m-1 in integers
coprime to p.  However, the claim is false, as shown below.

The approach can be summarized by noting that if x^p + y^p = z^p then
we have x+y=z (mod p), which implies that z=kp+(x+y) for some integer
k.  Thus, we have

x^p  +  y^p  =  [kp + (x+y)]^p

Expanding the binomial on the right hand side we see that the first
term is (kp)^p and every subsequent term (except the last) contains
some positive power of (kp) AND has a coefficient divisible by p.
Thus, all of those terms drop out (mod p^2) and we are left with

x^p  +  y^p  =  (x+y)^p     (mod p^2)

Since Case 1 of FLT stipulates that none of x,y,z are divisible by p,
and recalling that z=x+y (mod p), it's clear that Case I is proven if
we can show that the above congruence (mod p^2) has no solutions with
each of x, y, and (x+y) not equal to 0 (mod p).  To see how this can
easily be verified for some small primes, notice that (as Mathews
observed in 1886) we have

(x+y)^p - x^p - y^p = 0     (mod p^2)

and so
(x+y)^p - x^p - y^p  =  pxy(x+y)Q(x,y)

where Q(x,y) is a homogeneous integer function of degree p-3.  Thus
the congruence is equivalent to

xy(x+y)Q(x,y)  =  0  (mod p)

or, since z=x+y, to

xyz Q(x,y)  =  0  (mod p)

Therefore, if we can show that the congruence Q(x,y)=0 has no integer
solutions (mod p) with x,y, and x+y coprime to p, it follows that
Fermat's equation is insoluable under those conditions.  To illustrate,
consider the p=3, for which we have

(x+y)^3 - x^3 - y^3  =  3xy(x+y)

Here Q(x,y) is a constant 1, so the theorem is obviously true.  For
a slightly less trivial example, take the case p=5, which gives

(x+y)^5 - x^5 - y^5  =  5xy(x+y)(x^2 + xy + y^2)

In this case Q(x,y) = x^2 + xy + y^2 = 0 (mod 5) gives

4(x^2 + xy + y^2)  =  (2x+y)^2 + 3y^2  =  0  (mod 5)

The last equation can be written as

(2x+y)^2  =  -3y^2   (mod 5)

which is plainly impossible, because -3 is not a square modulo 5.  Thus
we see immediately that Case 1 of Fermat's Theorem with exponent p=5
is true.

To illustrate a case where this approach fails, consider the case
p=7, which gives

(x+y)^7 - x^7 - y^7  =  7xy(x+y)(x^2 + xy + y^2)^2

so we must have Q(x,y) = x^2 + xy + y^2 = 0 (mod 7).  However, in
this case we see that -3 IS a square (mod 7), so the congruence has
solutions (such as x=2, y=1), so we can't rule out the exponent p=7
with this argument.

Proceding in this way, we find that Case 1 of Fermat's Last Theorem
is implied by this simple congruence argument for the primes 3, 5,
11, 17, 23, 29, 41, 47, and 53, which includes all the primes of the
conclusion that it settles Case 1 for all prime exponents of the
form 3n-1.  However, for p=59 we find that 1^59 + 3^59 = (1+3)^59
(mod 59^2).  Looking a little further, we find that the following
primes less than 1000 of the form 3k-1 possess non-trivial solutions

59  83  179  227  419  443  701  857  887  911  929  971  977

(There are 17 others less than 2000.)  Is there a simple way of
characterizing these exceptional primes?  What is their density?
(See On the Density of Some Exceptional Primes.)

A slightly more sophisticated, but still completely elementary,
approach to Case I of Fermat's Last Theorem for cubes is to notice
that if  x^3 + y^3 = z^3 then

y^3  =  z^3 - x^3   =  (z-x) [ (z-x)^2 + 3zx ]              (1)

so z-x is a cube if 3 does not divide y.  Similarly we can prove z-y
is a cube since 3 doesn't divide x, and x+y is a cube because 3 doesn't
divide z.  Thus if none of x,y,z is divisible by 3 we have shown that
(x+y), (z-x) and (z-y) must all be cubes, which is impossible because
we have
(x+y-z)^3  =  3(z-x)(z-y)(x+y)                        (2)

and a cube cannot equal 3 times a cube.  (For comparison, see the
general proof of Fermat's Last Theorem for Cubes, which includes
the much more challenging Case 2, where xyz is allowed to be a multiple
of 3.)

We can obviously perform the same kind of factorization for other
prime powers.  If we consider the symmetrical form of the Fermat
equation x^p + y^p + z^p = 0 we can make use of the algebraic
identities such as

(x+y+z)^3 - (x^3 + y^3 + z^3)  =  3(x+y)(x+z)(y+z)

(x+y+z)^5 - (x^5 + y^5 + z^5)

/ x^2 + y^2 + z^2   (x+y+z)^2 \
=  5(x+y)(x+z)(y+z)(  --------------- + ---------  )
\        2              2     /

(x+y+z)^7 - (x^7 + y^7 + z^7)

/ x^4 + y^4 + z^4   (x+y+z)^4             \
=  7(x+y)(x+z)(y+z)(  --------------- + --------- - xyz(x+y+z) )
\        2              2                 /

and so on.  (For more economical expansions, see the note
Sums of Powers in Terms of Symmetric Functions.)  Of course, the
observation that the quantities (x+y), (x+z), and (y+z) must be pth
powers (assuming Case 1) applies to all prime exponents p.  This was
noted by P. Barlow in 1810, who pointed out that if n is prime and
x^n + y^n + z^n = 0 is solveable in coprime integers, then there must
be integers r,s,t such that one of the following four sets of conditions
is satisfied:

Case 1                         Case 2
------     -------------------------------------------------
x+y  =   r^n        n^(n-1) r^n          r^n                r^n
x+z  =   s^n           s^n             n^(n-1) s^n          s^n
y+z  =   t^n           t^n               t^n             n^(n-1) t^n

Barlow certainly wasn't the first person to notice this, nor was
he the last, as amatuers frequently re-discover it.  Unfortunately,
the factorization on the right hand side of (2) for primes greater
than 3 includes more than just those three factors, so the simple
divisibility argument used in Case 1 of p=3 doesn't immediately apply.
This is, however, the essential idea behind what is perhaps the
most important elementary result concerning Case 1 of Fermat's Last
Theorem, namely, Sophie Germain's Theorem.

Sophie Germain showed that if p is an odd prime and m is a prime such
that the congruence x^p + y^p + z^p = 0 (mod m) can only be satisfied
if either x, y, or z is congruent to 0 (mod m), and if there is no
integer x such that x^p = p (mod m), then x^p + y^p + z^p cannot equal
zero in integers x,y,z co-prime to p (nor in integers coprime to m).
She found at least one such "auxiliary prime" m for each p less than
100.

The proof of this can be illustrated by the case p=5 with the auxiliary
prime m=11.  First, notice that we can write

- x^5  =  (z + y) (y^4 - y^3 z + y^2 z^2 - yz^3 + z^4)

and as we discussed above the two factors on the right are mutually
coprime (on the assumption that x,y,z are pairwise coprime and none
of them is divisible by 5).  Therefore, both factors must individually
be 5th powers (by unique factorization), and the same argument applies
to the factorizations of -y^5 and -z^5, so we have integers A,B,C
and a,b,c such that

y + z = A^5
y^4 - y^3 z + y^2 z^2 - yz^3 + z^4 = a^5

z + x = B^5
z^4 - z^3 x + z^2 x^2 - zx^3 + x^4 = b^5

x + y = C^5
x^4 - x^3 y + x^2 y^2 - xy^3 + y^4 = c^5

and of course Aa=-x, Bb=-y, and Cc=-z.

Now, let's look at the 5th powers of integers modulo 11.  (The reason
for choosing the modulus 11 will be clear shortly).

x      x^5 (mod 11)
----    -------------
0           0
1           1
2          -1
3           1
4           1
5           1
6          -1
7          -1
8          -1
9           1
10          -1

Fortuitiously, we see that a fifth power of an integer must be
congruent to 0, +1, or -1 modulo 11.  It immediately follows that
we can only have a solution of  x^5 + y^5 + z^5 = 0  if one of the
numbers x,y,z is a multiple of 11, because otherwise all three of
these 5th powers is either +1 or -1 (mod 11), and there is no
way of adding three such values to get zero (mod 11).  Therefore,
exactly one of the numbers x,y,z must be a multiple of 11.  Since
the three variables are symmetrical, we can assume x=0 (mod 11),
but notice that

(x+y) + (x+z) - (y+z)  =  2x  =  C^5 + B^5 + (-A)^5

so again we have three 5th powers summing to 0 (mod 11), and by the
same reasoning as above, this implies that one of A,B,C must be a
multiple of 11.  However, since x is already divisible by 11, it's
clear than neither B nor C can be divisible by 11 because, because
that would imply that Z or y, respectively, was divisible by 11,
contradicting the fact that x,y,z are pairwise coprime.

This seems to force us to conclude that A must be a multiple of 11,
but this too is in conflict with out assumptions, because if

A  =  y + z  =  0   (mod 11)

then we have z = -y (mod 11), and plugging this into the above
equation for a^5, evaluated modulo 11, gives the congruence

a^5  =  5y^4    (mod 11)

and substituting x=0 (mod 11) into the above equation for c^5
gives
c^5  =  y^4     (mod 11)

Combining these last two congruences gives

a^5 = 5c^5      (mod 11)

which is obviously impossible, because we know the 5th powers
(mod 11) are all 0, +1, or -1, and we can rule out a=c=0 (mod 11)
because z=-Cc and we know z is NOT divisible by 11.  This completes
the proof of Sophie Germain's Theorem for the special case p=5,
using the auxiliar prime m=11.  The proofs for many other prime
exponents are similar.

This theorem raises some interesting questions.  One such question
is whether, given a prime p, we can characterize the primes q such
that the congruence

x^p + y^p + z^p = 0 (mod q)

implies that either x,y, or z must be divisible by q.  For example,
if p=3 we have q = 2, 7, or 13.  (It also appears that setting q = p^2
satisfies the requirements for some, but not all, primes p.)  Here's
a brief table of some q values for small primes

p                     q
----    ----------------------------------------
3:      2     7    13
5:      2    11    41    71   101
7:      2    29    71   113   491
11:      2    23    89   947  1409
13:      2    53   131   443   521
17:      2   137   239   443  1667
19:      2   191   419   647   761  1217  1901  2129
23:      2    47   461   599  1289  1427  1979  3083
3221  3911  4049  4877
29:      2    59   233   929  1103  1277  1451  1973
2843  3539  4409  6323  7193  7541
31:    311  1427  2357  2543  3659  5147  6263
37:    149   593  1259  1481
41:     83   821  1559  2297  2543  2789  3527  4019
43:    173   431   947  1721  1979  2237  2753

This table doesn't necessarily include all the q-primes for any
given p;  it extends only as far as I searched.  However, it's clear
that the list of q-values for any given p is finite.

An interesting application of this approach can be illustrated
by the case of exponent 14.  (Historically this case was the next
to be resolved - by Dirichlet - following Legendre's proof for
exponent 5; it was another seven years before Lame' finally
settled the case of exponent 7.)  We can prove very simply that
if there are integers x,y,z such that  x^14 + y^14 = z^14  then
xyz must be divisible by 71.  This follows because we have
71 = 5*14 + 1  and therefore

x^((71-1)/5)  +  y^((71-1)/5)  =  z^((71-1)/5)

If we assume xyz is coprime to 71 then this equation implies
the congruence

1^(1/5)   +  1^(1/5)   =   1^(1/5)        (mod 71)

It's easy to determine that the 5th roots of 1 (mod 71) are the
residues 1, 5, 25, 54, and 57, and none of these can be expressed
as a sum of two values in this set (even allowing duplicates).
Thus the equation is impossible under the assumption that xyz
is coprime to 71.

In general, if  kn+1 = p  for some prime p, and if the kth roots
of 1 (mod p) are "sum free" in the sense described above, then
the Fermat equation with exponent n is impossible in integers
x,y,z with xyz coprime to p.  (Note that if n=1 or 2 the kth
roots are never sum-free.)

So, to further restrict the possible solutions for exponent 14 (for
example), we could note that 3*14+1 = 43,  and the cube roots of
1 (mod 43) are 1, 6, and 36.  Since these roots are sum-free, we've
shown that xyz must be divisible by 43 (as well as 71).  Similarly
from 2*14+1=29 and the square roots of 1 (mod 29) being 1 and 28,
we can say that xyz must be divisible by 29.

Let's call the prime p a "Germain Prime" relative to the positive
integer n if there exists an integer k such that p=kn+1 and the
equation a+b=c (mod p) has no solutions with a,b,c each a kth root
of 1 (mod p).  Then we know that if  x^n + y^n = z^n  then xyz is
divisible by every Germain Prime relative to n.  For example,
relative to n=2 the only Germain Primes are 3 and 5, so it follows
that for every Pythagorean triple x,y,z we have xyz divisible by
3 and 5.

For another example, the Germain Primes relative to n=7 are 29,
71, 113, and 491, which implies that if x^7 + y^7 = z^7  then
xyz is divisible by (29)(71)(113)(491).  Of course, we know the
Fermat equation with n=7 has no integer solutions, so this
consequence is not terribly important.  Nevertheless, the Germain
Primes seem interesting in their own right.  Following is a table
of all the Germain Primes with k < 400 for integers n (not
necessarily primes as in the above table) from 1 to 13.

n                 Germain Primes relative to n
---  ----------------------------------------------------------------
1    2
2    3    5
3    7   13
4   13   17   41
5   11   41   71  101
6   13   19   43   61   97  157  277
7   29   71  113  491
8   17   41  113
9   19   37   73  181  523  577
10   31   41   71  101  281  401 1181
11   23   89  947 1409
12   37  61  97 109  157  181 193  241  277  313  337  373  769 1201
13   53  131  443  521

It's known that there are only finitely many Germain Primes relative
to any given n, so this approach cannot prove FLT  However, it does
give an elementary way of proving that any solutions of the Fermat
equation for large n must be extremely rare (if they existed).  For
example, we can show that if x^21 + y^21 = z^21 then xyz must be
divisible by the product of all the Germain Primes relative to n=21:

43   211   337   421   463   547   673   967  1051
1093  1303  1429  1471  1597  1933  2437  3319  3361
4327  6091  6133  6217  7603  9619

This obviously implies that any solution would have to consist of
extremely large numbers.

This approach to FLT is actually quite old.  G. Libri wrote about
Germain Primes (although he didn't name them) in 1832.  They were
subsequently discussed by (among others) Pepin (1880), Pellet (1886),
Mathews (1895), Dickson (1909), Cornacchia (1909), and Mantel (1916).
Several of these writers stated (although none ever published a
proof) that the number of Germain Primes relative to any given n is
finite.  As Libri said back in 1832, "hence it is futile to try to
prove  u^n + v^n = z^n  impossible by trying to show that one of
the unknowns must be divisible by an infinitude of primes".

One of the more charming incarnations of this approach was that
of E. Dubouis.  Writing in 1910 he defined a "sophien of n" to
be a prime p of the form kn+1 for which x^n + y^n = 1 (mod p)
is impossible.
```