Tuesday, August 30, 2005

Sophie's Proof

Sophie's Proof is the proof discovered by Sophie Germain that later led to the proof of Fermat's Last Theorem for n =5. The proof is very important historically in that it represents a new approach to the problem. Rather than demonstrating that no solution exists, Sophie shows for certain values of n, n must divide x,y, or z.

After this proof, it became traditional to divide Fermat's Last Theorem into two parts:

Case I: None of the three values x,y,z is divisible by n.
Case II: n divides 1 of the three values x,y,z.

Here is Sophie Germain's Theorem:

Theorem: If xn + yn = zn and n is a prime ≥ 3 and 2n+1 is a prime, then n must divide xyz.

(1) We can assume that x,y,z are relatively prime to each other. [See here]

(2) So, let's assume that n doesn't divide xyz.

(3) Since n is odd, we can set z' to -z and get:
xn + yn + (z')n = 0.

(4) We can rewrite this to be [see here for details]
-xn = (y+z)(y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1))

(5) From this, we can show that:
y+z and y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1) are relatively prime since:

(a) Assume that they are not relatively prime.
(b) Then, there exists a prime p such that p divides y+z and p divides y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1).
(c) from this, we know that z ≡ -y (mod p).
(d) Using the fact that they are congruent (see here), we get:
y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1)
y
(n-1) - y(n-2)(-y) + ... -y(-y)(n-2) + (-y)(n-1)
y(n-1) + y(n-1) + ... + y(n-1) + y(n-1) ≡ (n)y(n-1)
(e) So from Euclid's Lemma, p either divides n or it divides y(n-1).
(f) But p doesn't divide n since:
(i) n is prime so p would equal n (a prime is only divisible by itself or 1)
(ii) And then n would divide (-x)n
(iii) Which means that it would divide x (from Euclid's Generalized Lemma)
(iv) But this impossible by step #2.
(g) And p doesn't divide y(n-1) because then p would divide y (Euclid's Generalized Lemma) and p would also divide z (since it divides y and it divides y+z), but this is impossible by step #1.
(h) So we have a contradiction and we reject our assumption.

(6) From Step #5 (see here), we can conclude that there exists a such that:
y + z = an

(7) But we can make this same argument for z+x and x + y where:
-yn = (x + z)(x(n-1) - x(n-2)z + ... -xz(n-2) + z(n-1))
-zn = (x + y)(x(n-1) - x(n-2)y + ... -xy(n-2) + y(n-1))

(8) So we know that there exists b,c where:
z + x = bn
x + y = cn

(9) We also know that any value un ≡ ±1 or 0 (mod 2n + 1) since:

(a) Assume that 2n+1 doesn't divide un [ we only need to consider the case where it is not congruent to 0]
(b) Since 2n+1 is a prime, we can apply Fermat's Little Theorem to get:
u2n ≡ 1 (mod 2n+1)
(c) And this means that:
(un)2 ≡ 1 (mod 2n + 1)
(d) So that un ≡ ± 1 (mod 2n+1) [See here for review of modular arithmetic]

(10) From this, we can conclude that (2n+1) divides xyz' since:

(a) Assume 2n+1 doesn't divide xyz'.
(b) Then, from step #9, we have:
xn ≡ ± 1
yn ≡ ± 1
zn ≡ ± 1
(c) But this is impossible since:
xn + yn + (-z)n ≡ 0 (mod 2n+1)
but
± 1 ± 1 ± 1 cannot be congruent to 0 (mod 2n+1)
(d) So, we reject(a).

(11) Let's assume that (2n+1) divides x. (We will be able to make the same type of argument if it divides y or z')

(12) Then 2x = bn + cn + (-a)n since from step #6 and step #8, we know that:
2x = z + x + x + y -y - z = bn + cn + (-a)n

(13) And we can conclude that (2n+1) divides acb since;

(a) We assumed that 2n+ 1 divides x. This gives us:
bn + cn + (-a)n ≡ 0 (mod 2n+1)

(b) Now, we can apply the same argument as Step #10 since:

(i) Assume that 2n+1 doesn't divide acb

(ii) From step #9 and (i) above, we can conclude that bn, cn, (-a)n ≡ ± 1.

(iii) But this is impossible since:
± 1 ± 1 ± 1 cannot be congruent to 0 (mod 2n+1)

(iv) So we can reject our assumption in (i) and conclude that 2n+1 divides acb.

(14) But (2n+1) can't divide abc since:

(a) (2n+1) can't divide b since:

(i) 2n+1 divides b → 2n+1 divides bn → 2n+1 divides z + x [since by step #8, z + x = bn.]
(ii) We know that 2n+1 divides x, so if it divides z+x, it must also divide z.
(iii) But this is impossible since x,z have no common factors by step #1.

(b) (2n+1) can't divide c for the same reason as above. That is, x,y have no common factors by step #1.

(c) (2n+1) can't divide a since:

(i) Assume (2n+1) divides a.
(ii) Then (2n+1) divides y + z which means that z ≡ -y (mod 2n+1)
(iii) We know from Step #5, there exists a value d, e such that:
dn = y(n-1) - y(n-2)z + ... - yz(n-2) + z(n-1).
en = x(n-1) - x(n-2)y + ... -xy(n-2) + y(n-1).

(iv) Applying (ii) gives us:
dn ≡ (n)y(n-1) (mod 2n+1) [See Step #5d]

(v) Since we know that x ≡ 0 (mod 2n + 1) [from Step #11], we get:
en ≡ (0)(n-1) - (0)(n--2)y + ... -(0)y(n-2) + y(n-1) ≡ y(n-1) (mod 2n+1)

(vi) Appyling (iv), this gives us:
dn ≡ (n)en (mod 2n+1)

(vii) From Step #9, we know that dn,en are 0,1, or -1. This means that they must both be equal to 0 since this is the only way that 0 ≡ n*0.

(viii) But if 2n+1 divides both dn,en, then it divides both d,e from Euclid's Lemma

(ix) But 2n+1 divides e implies that it also divides y (from (v).)

(x). But then it divides both x,y which goes against step #1.

(xi). So we have a contradiction and we reject (i).

(15) And this means that step #14 contradicts step #13 so we reject Step #2.

QED

Corollary: x5 + y5 = z5 → 5 divides xyz.

This is true by above since 5 is a prime and 2*5+1 = 11 is a prime.

QED

References

12 comments:

  1. it says here that you set z' to -z so x^5+y^5=(-z')^5 and so x^5+y^5-(-z')^5 or am I mistaken?

    ReplyDelete
  2. The idea here is that:
    z^5 = -(-z)^5

    This is done so that we can change:
    x^5 + y^5 = z^5

    into

    x^5 + y^z + [-(-z)^5] = 0

    If this is what you meant, then you are correct.

    The reason for this is so that we have a symmetric equation of the form:

    x^5 + y^5 + z^5 = 0

    In this symmetric equation, we can make an argument about x^5 and know that it could just as well apply to y^5 and z^5.

    ReplyDelete
  3. yeah - I've worked through it now - I think there is just a sign wrong on one line of the proof but the rest seems right.

    ReplyDelete
  4. On which step, do you see a mistake in the sign? I will be glad to change it if there is a typo.

    -Larry

    ReplyDelete
  5. step 3 I think it should say
    x^5+y^5-(-z')^5 or x^5+y^5+(z')^5

    ReplyDelete
  6. Step (10c):
    There is an errant zero:
    x^n + y^n + (-z)^n0 ≡ 0 (mod 2n+1)
    Instead of:
    x^n + y^n + (-z)^n ≡ 0 (mod 2n+1)

    Step (14a)(i):
    2n+1 divides b^(2n+1)
    Should be:
    2n+1 divides b^n ?

    ReplyDelete
  7. Hi Rob,

    You are right on both counts. I have made the changes to the blog.

    Thanks for noticing! :-)

    -Larry

    ReplyDelete
  8. Hey. ... I dont understand somethin. Sophie Germains proof of FSS, was that n was a prime larger than 2 but less than 100.
    but this proof doesnt say anything about that ?or?

    ReplyDelete
  9. Is this blog still active?
    I'm doing a project for school, and I'm having a hard time understanding how you set z' to -z in order to have the equation: x^n+y^n+(z')^n=0
    But when you move on with the proof you leave out the prime-symbol. Why is this?

    ReplyDelete
  10. Hi Annika,

    This blog is not very active any more but I still monitor comments and occasionally answer comments. :-)

    The idea of setting z' to -z is about introducing another variable.

    Let's say we have x^n + y^n = z^n where n=1 (which has a solution. We need n to be odd for this to work).

    In this case: 3^1 + 4^1 = 7^1

    Let us define a new variable which I will call z'= -z (but I could also call it w -- it's math so the name doesn't matter so much).

    Since z' = -z, it follows that z' = -7.

    Now we can say that:

    3^1 + 4^1 + (-7)^1 = 0

    So, it follows that x^n + y^n + (z')^n = 0

    Once it is clear that we can do this, we can for all purposes, analyze the problem of x^n + y^n = z^n in the form of x^n + y^n + z^n = 0. Yes, each time we say z, we really mean z' but since this is clear, just to keep it cleaner, I only refer to it as z.

    What I probably should have done to make this point clear is to have a separate lemma where I write:

    If x^n + y^n = z^n has a solution then there exists a,b,c where a^n + b^n + c^n = 0 (and a = x, b = y, c = -z)

    ReplyDelete
  11. This comment has been removed by the author.

    ReplyDelete