mersenneforum.org > Math Proof of LL theorem
 Register FAQ Search Today's Posts Mark Forums Read

2006-02-11, 00:36   #34
alpertron

Aug 2002
Buenos Aires, Argentina

23·132 Posts

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.

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

Nov 2003

22×5×373 Posts

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.

2006-02-11, 11:27   #36
Numbers

Jun 2005
Near Beetlegeuse

22·97 Posts

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.

 2006-02-11, 17:22 #37 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 111910 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-11, 23:10   #38
Numbers

Jun 2005
Near Beetlegeuse

22×97 Posts

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.

 2006-02-13, 19:02 #39 alpertron     Aug 2002 Buenos Aires, Argentina 23×132 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 23·132 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, 21:30   #41
Numbers

Jun 2005
Near Beetlegeuse

22·97 Posts

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.

 2006-02-13, 23:10 #42 Numbers     Jun 2005 Near Beetlegeuse 6048 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.
2006-02-14, 22:21   #43
alpertron

Aug 2002
Buenos Aires, Argentina

23·132 Posts

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?

2006-02-15, 01:27   #44
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

80416 Posts

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 McPogor Miscellaneous Math 18 2007-10-19 11:40 vtai Math 12 2007-06-28 15:34 bdodson Lounge 6 2007-03-19 17:19 mfgoode Puzzles 9 2006-09-27 16:37 jinydu Math 5 2005-05-21 16:52

All times are UTC. The time now is 06:27.

Sat May 8 06:27:29 UTC 2021 up 30 days, 1:08, 0 users, load averages: 5.37, 4.02, 3.60