mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2013-11-15, 20:22   #23
literka
 
literka's Avatar
 
Mar 2010

3008 Posts
Default

Quote:
Originally Posted by Batalov View Post
Exactly.


What proof? What are you talking about?



Sorry, no more answers. I am insulted all the time and when I defend myself I am moved to Misc. I made last attempt to be here. Batalov, still I wish you good luck. Bye.
literka is offline   Reply With Quote
Old 2013-11-15, 23:08   #24
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2D6916 Posts
Default An alternative "proof by dilemma"

Quote:
Originally Posted by Batalov View Post
What proof? What are you talking about?
It seems he's talking about Euler's famous - and untrustworthy, because it relied on Herr Euler's "computation" - proof that 641 divides F5, thus (allegedly and untrustworthily) 'disproving' Fermat's conjecture that all Fn are prime.

Allow me to present a simplified version of CRGreathouse's post #2 "untrustworthy alternative computer-aided proof" - this one can more easily be done by hand, as it breaks things down into a "powering via repeated doubling and addition of 1 to result" step (Lemma 1) and a "multiplication of one number by another" step (Lemma 2). The mathematically fancy-pantsy around here may have heard of "proof by contradiction" (as in "you're wrong, thus I'm right.") ... the structure of my proof below is in the form of 2 lemmas - not to be confused with those furry little critters who famously and counterfactually have a reputation for mass cliff-diving (and which are close relatives of gerbils, as it happens) - thus "proof by dilemma", as it were.

I hope that said decomposition will make it easier for the mathematical community to organize the extensive independent double-checking effort needed to satisfy the OP of the validity of the (allegedly and untrustworthy) alternative proof.

Lemma 1: Let n = 2^7. Then n = 128, and F7 := 2^n+1 = 340282366920938463463374607431768211457.

Lemma 2: F7 = 59649589127497217 x 5704689200685129054721 .

QED

Is that at all understandable? Perhaps we should organize a special conference - is it too late to propose this as a last-minute add-on to this year's WCNTC at Asilomar?

Last fiddled with by ewmayer on 2013-11-16 at 00:06
ewmayer is offline   Reply With Quote
Old 2013-11-15, 23:21   #25
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

6A216 Posts
Default

Quote:
Originally Posted by Batalov View Post
Exactly.


What proof? What are you talking about?
I think he's talking about this paragraph from http://en.wikipedia.org/wiki/Fermat_numbers:

Quote:
The fact that 641 is a factor of F5 can be easily deduced from the equalities 641 = 27×5+1 and 641 = 24 + 54. It follows from the first equality that 27×5 ≡ −1 (mod 641) and therefore (raising to the fourth power) that 228×54 ≡ 1 (mod 641). On the other hand, the second equality implies that 54 ≡ −24 (mod 641). These congruences imply that −232 ≡ 1 (mod 641).
This does show what it's trying to with only arithmetic on numbers no bigger than 641, which is admittedly somewhat clever. However, I don't think this can claim to be any more of a proof than simply multiplying the two factors.
jyb is offline   Reply With Quote
Old 2013-11-15, 23:31   #26
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

222558 Posts
Default

Quote:
Originally Posted by jyb View Post
However, I don't think this can claim to be any more of a proof than simply multiplying the two factors.
Exactly.

Similarly, here's a "proof", that 9=3*3.
"Proof": 3*3=(1+2)^2=1^2+2*1*2+2^2=9.
Alleged added value of the "proof": it operates only with numbers no more than 2. While direct multiplication deals with larger numbers (i.e. 3).
Batalov is offline   Reply With Quote
Old 2013-11-16, 00:49   #27
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3·53·31 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Lemma 2: F7 = 59649589127497217 x 5704689200685129054721 .
I have through exhaustive labors succeeded in verifying part 2 of my proof by dilemma. We first tabulate multiples of the larger (purported) multiplicand by 0-9: 5704689200685129054721 x ____ =
Code:
0	                      0
1	 5704689200685129054721
2	11409378401370258109442
3	17114067602055387164163
4	22818756802740516218884
5	28523446003425645273605
6	34228135204110774328326
7	39932824404795903383047
8	45637513605481032437768
9	51342202806166161492489
And here is the resulting (no FFTs, DWTs or other suspicious 3-letter-initialism-denoted computer flummery allowed here) multiplication rhombus, with blank spaces denoting 0s. Columnwise addition gives - someone please double-check my carries! - the indicated sum, matching the desired result:
Code:
59649589127497217 x 5704689200685129054721:

5:   28523446003425645273605
9: +  51342202806166161492489
6: +   34228135204110774328326
4: +    22818756802740516218884
9: +     51342202806166161492489
5: +      28523446003425645273605
8: +       45637513605481032437768
9: +        51342202806166161492489
1: +          5704689200685129054721
2: +          11409378401370258109442
7: +           39932824404795903383047
4: +            22818756802740516218884
9: +             51342202806166161492489
7: +              39932824404795903383047
2: +               11409378401370258109442
1: +                 5704689200685129054721
7: +                 39932824404795903383047
--------------------------------------------
Sum= 340282366920938463463374607431768211457
[Nonzero Carries as noted:
     11112332345456777777886775664432332    ]
Whew! I need a beer. Lemma 1 may need to wait a few days. Hey, even Hercules [or "Herakles" to the OP] needed to rest between his famous labors, I'll bet.
ewmayer is offline   Reply With Quote
Old 2013-11-16, 00:57   #28
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41·229 Posts
Default

...and if you did it in octal, you would have been done already, because calculation of 2^128+1 in octal doesn't need a separate calculation (no Lemma 1!).
Code:
First, prepare multiples of 3237257607274243001:
 3237257607274243001 (x1)
 6476537416570506002 (x2)
11736017226064751003 (x3)
15175277035361214004 (x4)
20434556644655457005 (x5)
23674036454151722006 (x6)
27133316263446165007 (x7)

Now, add them in a staircase
                            3237257607274243001
                      1152401672664431414535001 *
                      _________________________
                            3237257607274243001
                        20434556644655457005
                       11736017226064751003
                      20434556644655457005
                     15175277035361214004
                     3237257607274243001
                   15175277035361214004
                   3237257607274243001
                 11736017226064751003
                15175277035361214004
               15175277035361214004
              23674036454151722006
             23674036454151722006
             6476537416570506002
           27133316263446165007
          23674036454151722006
          3237257607274243001
       15175277035361214004
       6476537416570506002
     20434556644655457005
     3237257607274243001
    3237257607274243001
_______________________________________________
    4000000000000000000000000000000000000000001
Batalov is offline   Reply With Quote
Old 2013-11-16, 01:01   #29
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1162510 Posts
Default

There you go, invoking mysterious and highly untrustworthy "computational magic" again. :)
ewmayer is offline   Reply With Quote
Old 2013-11-16, 01:28   #30
literka
 
literka's Avatar
 
Mar 2010

110000002 Posts
Default

Your posts are real eyes opener for me. In fact I learned today much more about people of this forum than in the past 3 years.
Batalov, you quoted me wrongly. You wrote 255 instead of 2^55. Someone could think that I made a mistake. Of course you cannot correct it, but be careful next time.

BTW. No matter how much you write these proofs (i.e. about F5, F6, and F7) will stay my proofs and the only thing left for you it will be to write how you can divide 2 numbers or to multiply 2 numbers.

Last fiddled with by literka on 2013-11-16 at 01:30
literka is offline   Reply With Quote
Old 2013-11-16, 01:42   #31
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41·229 Posts
Default

Of course, they will. They will stay a monument to how one can scratch one's left ear not simply with the right hand, but more elegantly -- with the toe on one's right foot.

On to the same Herculean task for F8, then? Is it already in the plans?
Batalov is offline   Reply With Quote
Old 2013-11-16, 02:09   #32
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41×229 Posts
Default

Here's how one "scratches left ear with the left hand".
(All you need is a pencil and one sheet of paper for up to F7 and if your handwriting is neat enough, with space to spare for the F8.)

Code:
Lemma 5A. 641 divides 2^32+1.
Proof: 2^8 = 256. 
Let's square this value two more times modulo 641, and compare to 641-1.
(256^2)%641 = 154
(154^2)%641 = 640. QED.

Lemma 6A. 274177 divides 2^64+1.
Proof: 2^16 = 65536. 
Let's square this value two more times modulo 274177, and compare to 274177-1.
(65536^2)%274177= 258768.
(258768^2)%274177= 274176. QED.

Lemma 7A and so on. Same thing over and over again.

Last fiddled with by Batalov on 2013-11-16 at 02:11 Reason: don't need (mod N)
Batalov is offline   Reply With Quote
Old 2013-11-16, 02:18   #33
literka
 
literka's Avatar
 
Mar 2010

19210 Posts
Default

Quote:
Originally Posted by Batalov View Post
Of course, they will. They will stay a monument to how one can scratch one's left ear not simply with the right hand, but more elegantly -- with the toe on one's right foot.

On to the same Herculean task for F8, then? Is it already in the plans?

I wrote "no more answers". I can make exception this time. For a while I thought I had similar proof for largest known factor of F12. You might notice that proofs for F6 and F7 are based on the same concept.
I noticed some regularities.
Since there are high degree polynomials let me introduce some abbreviations: Instead of a polynomial (-3)*x^2+4*x-5 I will write (-3)(4)(-5). Take 2 polynomials
{1){0}(-1)(1)(1)(-1)(0)(1)(0)(-1)(0)(2)(-2)(2)(-1)(1)(-1)(1)(0)(1)(0)(0)(0)(1)
and
(1)(0)(1)(-1)(0)(-1)(0)(0)(0)(1)

Product of these polynomials is
(1)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(-1)(5)(-5)(5)(-5)(5)(-5)(4)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(1)

The value of the last polynomial for the point x=4 is F6. Hence values of first 2 polynomials must be factors of F6.
What nice in this it is that last polynomial is nice looking almost symmetric polynomial.
literka is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
On Fermat's Last Number c10ck3r Miscellaneous Math 14 2012-11-29 20:36
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28
Fermat number and Modulo for searching divisors CyD Factoring 4 2011-05-31 11:24
Fermat number factors Citrix Math 35 2007-01-23 23:17
New Fermat number divisor! ET_ Factoring 1 2004-10-08 03:34

All times are UTC. The time now is 08:30.

Tue Apr 13 08:30:43 UTC 2021 up 5 days, 3:11, 1 user, load averages: 1.29, 1.39, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.