mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2009-02-05, 16:26   #1
Dougal
 
Dougal's Avatar
 
Jan 2009
Ireland

2728 Posts
Default Lucas-Lehmer

Can someone please explain the test to me because i dont understand it properly.For example M3, works like this, (4^2)-2 mod 7, so thats 14/7=2,no remainder,so its prime

But wikipedia shows this

On the other hand, M11 = 2047 = 23 × 89 is not prime. To show this, we start with s set to 4 and update it 11−2 = 9 times, taking the results mod 2047:
  • s ← ((4 × 4) − 2) mod 2047 = 14
What i dont understand is where the 14 comes from

Thanks
Dougal is offline   Reply With Quote
Old 2009-02-05, 16:32   #2
10metreh
 
10metreh's Avatar
 
Nov 2008

91216 Posts
Default

Quote:
Originally Posted by Dougal View Post
Can someone please explain the test to me because i dont understand it properly.For example M3, works like this, (4^2)-2 mod 7, so thats 14/7=2,no remainder,so its prime

But wikipedia shows this


On the other hand, M11 = 2047 = 23 × 89 is not prime. To show this, we start with s set to 4 and update it 11−2 = 9 times, taking the results mod 2047:
  • s ← ((4 × 4) − 2) mod 2047 = 14
What i dont understand is where the 14 comes from

Thanks
((4 x 4) - 2) = 14
(14) mod 2047 = 14

Do you understand what "mod" means? (And it's not "moderator" in this case.)
10metreh is offline   Reply With Quote
Old 2009-02-05, 16:44   #3
Dougal
 
Dougal's Avatar
 
Jan 2009
Ireland

18610 Posts
Default

i checked it on wikipedia and it said something about A mod N means the remainder of a/n.so what i thought it meant was 2047/14 and the remainder was 14,but that isnt possible,however i understand it now,its (4^2)-2=14,then you do this 11-2 times and when you get that far if,lets say x doesnt divide 2047 evenly then the number isnt prime.would that be right?(if you can make any sense out of my rambling).for mersenne numbers,you start with 4^2-2,how do you get the starting number for the llr test?

Actually i looked further through it and it appears i still dont have a clue

Thanks

Last fiddled with by Dougal on 2009-02-05 at 16:49
Dougal is offline   Reply With Quote
Old 2009-02-05, 17:14   #4
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

2×112×19 Posts
Default

Quote:
Originally Posted by Dougal View Post
Actually i looked further through it and it appears i still dont have a clue

Thanks
Does George's example here help: http://www.mersenne.org/various/math.php
petrw1 is offline   Reply With Quote
Old 2009-02-05, 17:25   #5
Dougal
 
Dougal's Avatar
 
Jan 2009
Ireland

2×3×31 Posts
Default

Sorry petrw1,doesnt seem to help much,maybe if i understood mod i'd understand it.Thanks anyway.i've done alot of messing about on a calculator and i now understand it.dont understand how you find out what number you start of with for llr.

Last fiddled with by Dougal on 2009-02-05 at 18:13
Dougal is offline   Reply With Quote
Old 2009-02-05, 18:19   #6
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by Dougal View Post
i thought it meant was 2047/14 and the remainder was 14
You have it backwards. 14 mod 2047 is the remainder of 14/2047.

Last fiddled with by Mr. P-1 on 2009-02-05 at 18:19
Mr. P-1 is offline   Reply With Quote
Old 2009-02-05, 19:05   #7
Dougal
 
Dougal's Avatar
 
Jan 2009
Ireland

2·3·31 Posts
Default

sorry,thats what i meant,i understand it now,just not the riesel version of it.
Dougal is offline   Reply With Quote
Old 2009-02-05, 20:40   #8
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by Dougal View Post
sorry,thats what i meant,i understand it now,just not the riesel version of it.
I advise you, as a beginner, to just skip the parts about Riesel or LLR and not worry about it.

GIMPS is concerned with Mersenne (that's the "M" in "GIMPS"!) numbers. Riesel numbers are something else; some folks in GIMPS may also be interested in Riesel numbers, but there's no "R" in "GIMPS", so it's a side subject.

(There is a connection between Mersenne numbers and Riesel numbers ... but there are connections between all numbers!!)

Last fiddled with by cheesehead on 2009-02-05 at 20:44
cheesehead is offline   Reply With Quote
Old 2009-02-06, 00:05   #9
Dougal
 
Dougal's Avatar
 
Jan 2009
Ireland

2·3·31 Posts
Default

Thanks cheesehead(i think).
Well if you think it would be a bit advanced for me then il leave it a while,But if anyones willing to try teach me id appreciate it.
Dougal is offline   Reply With Quote
Old 2009-02-06, 10:25   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22×13×59 Posts
Default

M11:

S0=4
S1=(42-2) mod 2047 = 14 mod 2047 = 14
S2=(142-2) mod 2047 = 194 mod 2047 = 194
S3=(1942-2) mod 2047 = 37634 mod 2047 = 788
S4=(7882-2) mod 2047 = 620942 mod 2047 = 701
S5=(7012-2) mod 2047 = 491399 mod 2047 = 119
S6=(1192-2) mod 2047 = 14159 mod 2047 = 1877
S7=(18772-2) mod 2047 = 3523127 mod 2047 = 240
S8=(2402-2) mod 2047 = 57598 mod 2047 = 282
S9=(2822-2) mod 2047 = 79522 mod 2047 = 1736

Since Sn-2=S9 != 0 then M11 is not prime.
ATH is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas-Lehmer Primes henryzz And now for something completely different 42 2019-06-03 14:09
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
lucas-lehmer theorem Robot2357 Math 6 2013-06-15 03:10
lucas lehmer outstretch science_man_88 Miscellaneous Math 7 2010-07-14 12:35
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32

All times are UTC. The time now is 03:42.

Sun Apr 11 03:42:50 UTC 2021 up 2 days, 22:23, 1 user, load averages: 0.92, 1.25, 1.36

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.