mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-09-19, 16:06   #34
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

25018 Posts
Default

Based on the previous post: let n = (22p -2p+1)/3 where p is a prime number, is it true that 2n-1 = 1 (mod n) ?
alpertron is offline   Reply With Quote
Old 2012-09-19, 16:55   #35
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101101011102 Posts
Default

Quote:
Originally Posted by alpertron View Post
Based on the previous post: let n = (22p -2p+1)/3 where p is a prime number, is it true that 2n-1 = 1 (mod n) ?
Nice problem. Proof: let p>2 prime number

Observe that: (2^(2*p)-2^p+1)/3 | 2^(6*p)-1
so it is enough to prove that for p>2: 2^(n-1)==1 mod 2^(6*p)-1
it is equivalent to n-1==0 mod (6*p)
so (2^(2*p)-2^p-2)/3==0 mod (6*p)
(18*p)|2^p*(2^p-1)-2

Let p>3 then it is true mod p (use Fermat's little theorem), 2 also divides, this is trivial since 2^p is even. For 9 use: p=6k+-1 then 2^p=={2,5} mod 9, for the two cases: 2^p*(2^p-1)-2=={0,18}==0 mod 9.
Since 2,9,p are relative prime numbers for p>3 it means that the divisibility is also true for 2*9*p=18*p.
For p=3: 2^(n-1)==1 mod n is also true.
R. Gerbicz is offline   Reply With Quote
Old 2012-09-19, 17:18   #36
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

5×269 Posts
Default

Thanks.
alpertron is offline   Reply With Quote
Old 2021-03-20, 08:03   #37
Mounir
 
Mar 2021

1 Posts
Default

Hi everyone


I know I am a bit late.... BUT I have the answer to your problem:


take N = 2^524287 - 1.



Notice that 524287 = 2^19 - 1, this is a clue for the proof ;)


Indeed, you just need to consider the sequence X(n+1) = 2^X(n) - 1 with X(0) = 19 and proove that all terms of the sequence verify X(n)*X(n+1) divide 2^X(n) - 2.


Have a nice day!
Mounir is offline   Reply With Quote
Old 2021-03-21, 16:14   #38
kijinSeija
 
Mar 2021

1 Posts
Default

Hi

I would like to know if a^(2^n) mod (2^n-1) = a² when a is between 0 and sqrt(2^n-1) and a is an integer when 2^n-1 is prime and only if it's prime ?

I tried this with some Mersenne exposant and it apparently works.

It can't be used to eliminate non-Mersenne exponant quickly ?

Thanks :D
kijinSeija is offline   Reply With Quote
Old 2021-03-21, 22:43   #39
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

23×89 Posts
Default

In My Humble Opinion (IMHO) the even numbers are easier to keep track of
MattcAnderson is offline   Reply With Quote
Old 2021-03-22, 03:03   #40
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

249716 Posts
Default

Quote:
Originally Posted by kijinSeija View Post
Hi

I would like to know if a^(2^n) mod (2^n-1) = a² when a is between 0 and sqrt(2^n-1) and a is an integer when 2^n-1 is prime and only if it's prime ?

I tried this with some Mersenne exposant and it apparently works.

It can't be used to eliminate non-Mersenne exponant quickly ?

Thanks :D
That is a PRP test in disguise. From Fermat theorem, a^p=a (mod p) if p is prime. Amplify with a, you get a^(p+1)=a^2 (mod p). Replace p with Mp and you have your test. Replace a with 3 and that's what P95 and gpuOwl are doing.

Yes, it can be used to eliminate composite Mp's, but not "fast". Well, not faster than we are doing already.
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Twin Prime Conjecture Proof Steve One Miscellaneous Math 53 2019-03-18 00:34
Semi-prime factorization conjecture Alberico Lepore Alberico Lepore 7 2018-02-16 08:27
Conjecture prime numbers, demonstration possible? Godzilla Miscellaneous Math 5 2016-05-16 12:44
Prime abc conjecture b == (a-1)/(2^c) miket Miscellaneous Math 6 2013-05-22 05:26
The Twin Prime Conjecture Song Templus Lounge 9 2006-03-14 16:30

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

Sun Apr 11 23:03:21 UTC 2021 up 3 days, 17:44, 1 user, load averages: 2.48, 2.50, 2.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.