Proof of LL theorem - Page 4

alpertron · 2006-02-11, 00:36

Quote:

Originally Posted by R.D. Silverman

So let me ask: How much number theory and group theory do you know?
How much algebra do you know? Calculus is irrelevant. I can give a
very short proof (less than 10 lines), but it requires knowing Lagrange's
Theorem, and some stuff about multiplicative sub-groups of a finite field.

The mathematics involved isn't more "advanced" than 1st year calculus.
It is merely different.

Please notice that most people here uses math as a hobby, and showing a proof that does not need college math will be useful to a bigger audience. Anyway, both proofs can be written on the Wiki, because there is no article size limit.

R.D. Silverman · 2006-02-11, 06:33

Quote:

Originally Posted by alpertron

Please notice that most people here uses math as a hobby, and showing a proof that does not need college math will be useful to a bigger audience. Anyway, both proofs can be written on the Wiki, because there is no article size limit.

Even the proof that does not use "college math" requires knowledge of
quadratic reciprocity which is not a high school topic. And the proof is
a meaningless jumble of algebraic manipulations that does not convey
*understanding*. The proof I have in mind gives an immediate "Aha! Of course!" to someone with a little knowledge of algebra. It shows an element
of maximal order in a group of order P+1. And it is a lot shorter.

Numbers · 2006-02-11, 11:27

Quote:

Originally Posted by R.D. Silverman

The proof I have in mind gives an immediate "Aha! Of course!" to someone with a little knowledge of algebra.

Whilst not intending to slight others for their efforts, proofs that genuinely give an immediate "Aha! Of course!" are in very short supply, and all the more appreciated when they are found. I'm sure that I am not alone in saying that I would be extremely grateful if you would be kind enough to post this proof either here, or in the Wiki.

philmoore · 2006-02-11, 17:22

Actually, Dario made some excellent changes to the wiki that clarify the overall structure of the proof, but in the process, some of the constructions used in the first part do not get introduced until the second part. I plan to take those constructions out and place them before both the necessity and sufficiency proofs, so that those two proofs may be read in either order.

As for the suggestion of Bob Silverman, I think it would also be a great addition to this section of the Wiki. But there is still a role for this proof which seems to require relatively little in the way of prerequisites.

By the way, I thought the explanation of quadratic reciprocity on the wiki was well-written and should be helpful to anyone needing help understanding the LL test proof.

Numbers · 2006-02-11, 23:10

Quote:

Originally Posted by Numbers

Whilst not intending to slight others for their efforts, proofs that genuinely give an immediate "Aha! Of course!" are in very short supply,

I would just like to make it absolutely clear that I was talking about proofs in general, rather than about any specific proof, author or publisher of proofs.

alpertron · 2006-02-13, 19:02

I think that in the Proof of Necessity of Lucas-Lehmer test MersenneWiki article, we would have to first state that 3 is not a quadratic residue modulo Q and then start working with numbers of the form $a+b\sqrt{3}$ , in order to show that the number $sqrt{3}\,\pmod{Q}$ is being added to the field of numbers modulo Q, like we add the number $i$ to the integers to generate the Gaussian Integers. What do you think?

alpertron · 2006-02-13, 19:19

Suppose that we need to prove that $x^4 + y^4 = z^4$ does not have solutions for positive integers x, y, z. What proof do you like?

1) Since Wiles' proof of the Last Theorem shows that $x^n + y^n = z^n$ has no solutions for positive integers x, y, z when n>2, then when n=4, the proof follows.

2) Use original Fermat proof:

Proposition: There are no integer solutions of $x^4 + y^4 = z^2$ .

PROOF: Suppose there are integers x,y,z such that $x^4 + y^4 = z^2$ .

This can be written as a Pythagorean triple $(x^2)^2 + (y^2)^2 = z^2$ , from which it follows that $y^2 = 2pq$ , $x^2 = p^2 - q^2$ , and $z = p^2 + q^2$ .

Since $2pq$ is a square, we know that either $p$ or $q$ is even.

Thus, from the Pythagorean triple $x^2 + q^2 = p^2$ we
have $x = r^2 - s^2$ , $q = 2rs$ , and $p = r^2 + s^2$ .

Also, since $2pq$ is a square we can set $q = 2u^2$ and $p = v^2$ .

Now, since $2u^2 = 2rs$ , we have $r=g^2$ and $s=h^2$ .

These, along with $p = v^2$ , can be substituted back into $p = r^2 + s^2$ to give $v^2 = g^4 + h^4$ , where v is smaller than z, contradicting the fact that there must be a smallest solution.

Notice that the first proof is only two lines long, and the second one is about 15 lines long. But the first one requires Wiles' proof that is about 100 pages long. When we include the proof of all theorems needed in its demonstration recursively (so it can be followed by someone that has only high-school math education) we will need probably about 10000 pages (this is a wild guess).

In the second proof we would have 15 lines plus other 15 in order to show the form of Pythagorean triples.

Well, what demonstration do you finally prefer?

This is the same case when we use high-level languages in computing science. A 3-line source code can generate a 1 MB executable file while a 1000-line source code can generate a 10 KB executable file, because the first one uses a function that needs a very large library.

Numbers · 2006-02-13, 21:30

Quote:

Originally Posted by Alpertron

This can be written as a Pythagorean triple $(x^2)^2 + (y^2)^2 = z^2$ , from which it follows that $y^2 = 2pq$

I'm afraid that this does not follow at all.

Let's suppose that $y^2 = 2pq$ .
Then you say that:

Quote:

Originally Posted by Alpertron

Since $2pq$ is a square, we know that either $p$ or $q$ is even.

Okay, let's suppose that $p$ is even.

Now make $y = 3$ . This gives $y^{2}\,=\,9$ , $pq\,=\, 4\frac{1}{2}$ and $q\,=\,2\frac{1}{4}$ . And yet you then go on to claim that $q=2rs$ where, I'm afraid, the unavoidable impression is that we are no longer looking at an integer solution of anything.

At which point I gave up.

This is the sort of proof that definitely does not give that "Aha!" moment that Mr Silverman was talking about. It just leaves me frustrated that even after studying 16 hours a week I still cannot make head or tail of what you are talking about.

Numbers · 2006-02-13, 23:10

It is of course perfectly possible that the above says more about my ability to study than it says about your ability to write proofs.

alpertron · 2006-02-14, 22:21

Quote:

Originally Posted by Numbers

Quote:

Originally Posted by alpertron

This can be written as a Pythagorean triple $(x^2)^2 + (y^2)^2 = z^2$ , from which it follows that $y^2 = 2pq$ .

I'm afraid that this does not follow at all.

A Pythagorean triple has the form $u^2 + v^2 = w^2$ , so if there is a triplet (x,y,z) such that $x^4 + y^4 = z^4$ then it follows that $u = x^2$ , $v = y^2$ , $w = z^2$ , so the number $v = y^2$ has the form $2pq$ for the Pythagorean triples as shown in my previous post.

Quote:

Originally Posted by Numbers

Let's suppose that $y^2 = 2pq$ .
Then you say that:

Quote:

Originally Posted by alpertron

Since $2pq$ is a square, we know that either $p$ or $q$ is even.

Okay, let's suppose that $p$ is even.

Now make $y = 3$ . This gives $y^{2}\,=\,9$ , $pq\,=\, 4\frac{1}{2}$ and $q\,=\,2\frac{1}{4}$ . And yet you then go on to claim that $q=2rs$ where, I'm afraid, the unavoidable impression is that we are no longer looking at an integer solution of anything.

At which point I gave up.

But we don't know a priori the value of $y$ . You set arbitrarily the value y=3, that does not give integer values for $p$ and $q$ . For example if $p=8$ and $q=9$ we could get $y^2=2pq=2*8*9=144$ , so $y=12$ . But notice that the proof states that $q$ should be even, so we would have to exchange the values of $p$ and $q$ .

Quote:

Originally Posted by Numbers

This is the sort of proof that definitely does not give that "Aha!" moment that Mr Silverman was talking about. It just leaves me frustrated that even after studying 16 hours a week I still cannot make head or tail of what you are talking about.

Have you ever seen a proof by contradiction?

mfgoode · 2006-02-15, 01:27

Quote:

Originally Posted by alpertron

values of $p$ and $q$ .

----------snip
Have you ever seen a proof by contradiction?

If Numbers is not content then try this URL.
http://homepages.cwi.nl/~dik/mathematics/jsh2.html

Mally

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Proof of Fermat's Last Theorem	McPogor	Miscellaneous Math	18	2007-10-19 11:40
help with a proof	vtai	Math	12	2007-06-28 15:34
Proof (?!) that RH is false?	bdodson	Lounge	6	2007-03-19 17:19
A proof with a hole in it?	mfgoode	Puzzles	9	2006-09-27 16:37
A Second Proof of FLT?	jinydu	Math	5	2005-05-21 16:52

2006-02-11, 17:22	#37
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3×373 Posts	Actually, Dario made some excellent changes to the wiki that clarify the overall structure of the proof, but in the process, some of the constructions used in the first part do not get introduced until the second part. I plan to take those constructions out and place them before both the necessity and sufficiency proofs, so that those two proofs may be read in either order. As for the suggestion of Bob Silverman, I think it would also be a great addition to this section of the Wiki. But there is still a role for this proof which seems to require relatively little in the way of prerequisites. By the way, I thought the explanation of quadratic reciprocity on the wiki was well-written and should be helpful to anyone needing help understanding the LL test proof.

2006-02-13, 19:02	#39
alpertron Aug 2002 Buenos Aires, Argentina 2·683 Posts	I think that in the Proof of Necessity of Lucas-Lehmer test MersenneWiki article, we would have to first state that 3 is not a quadratic residue modulo Q and then start working with numbers of the form $a+b\sqrt{3}$ , in order to show that the number $sqrt{3}\,\pmod{Q}$ is being added to the field of numbers modulo Q, like we add the number $i$ to the integers to generate the Gaussian Integers. What do you think?

2006-02-13, 19:19	#40
alpertron Aug 2002 Buenos Aires, Argentina 2×683 Posts	Suppose that we need to prove that $x^4 + y^4 = z^4$ does not have solutions for positive integers x, y, z. What proof do you like? 1) Since Wiles' proof of the Last Theorem shows that $x^n + y^n = z^n$ has no solutions for positive integers x, y, z when n>2, then when n=4, the proof follows. 2) Use original Fermat proof: Proposition: There are no integer solutions of $x^4 + y^4 = z^2$ . PROOF: Suppose there are integers x,y,z such that $x^4 + y^4 = z^2$ . This can be written as a Pythagorean triple $(x^2)^2 + (y^2)^2 = z^2$ , from which it follows that $y^2 = 2pq$ , $x^2 = p^2 - q^2$ , and $z = p^2 + q^2$ . Since $2pq$ is a square, we know that either $p$ or $q$ is even. Thus, from the Pythagorean triple $x^2 + q^2 = p^2$ we have $x = r^2 - s^2$ , $q = 2rs$ , and $p = r^2 + s^2$ . Also, since $2pq$ is a square we can set $q = 2u^2$ and $p = v^2$ . Now, since $2u^2 = 2rs$ , we have $r=g^2$ and $s=h^2$ . These, along with $p = v^2$ , can be substituted back into $p = r^2 + s^2$ to give $v^2 = g^4 + h^4$ , where v is smaller than z, contradicting the fact that there must be a smallest solution. Notice that the first proof is only two lines long, and the second one is about 15 lines long. But the first one requires Wiles' proof that is about 100 pages long. When we include the proof of all theorems needed in its demonstration recursively (so it can be followed by someone that has only high-school math education) we will need probably about 10000 pages (this is a wild guess). In the second proof we would have 15 lines plus other 15 in order to show the form of Pythagorean triples. Well, what demonstration do you finally prefer? This is the same case when we use high-level languages in computing science. A 3-line source code can generate a 1 MB executable file while a 1000-line source code can generate a 10 KB executable file, because the first one uses a function that needs a very large library.

2006-02-13, 23:10	#42
Numbers Jun 2005 Near Beetlegeuse 184₁₆ Posts	It is of course perfectly possible that the above says more about my ability to study than it says about your ability to write proofs.