Prime conjecture - Page 2

Batalov · 2012-09-16, 20:20

So it seems to be two tests rolled into one: one 2-PRP and the other a quazi-PRP (2^m-2==0 (MOD m-1)). To pass the second test, the number cannot be divisble by 2 or 3, but quite a few composites pass. Now, need to find a intersection of 2-pseudopromes with the second test.....

science_man_88 · 2012-09-16, 20:57

Quote:

Originally Posted by Batalov

So it seems to be two tests rolled into one: one 2-PRP and the other a quazi-PRP (2^m-2==0 (MOD m-1)). To pass the second test, the number cannot be divisble by 2 or 3, but quite a few composites pass. Now, need to find a intersection of 2-pseudopromes with the second test.....

what I was going on is on is if x mod y=z and x mod a=z x mod ay=z so one we thing we know is for prime m, (2^m-1) mod m = 1 but the 1 mod (m-1) is the hard part, because M_m mod (m-1) will not always be 1 even if m is prime. my reasoning could be a heuristic at best I think.

ATH · 2012-09-16, 21:52

553 cases up to 5*10⁹, all prime.

Code:

Stan · 2012-09-16, 22:02

Quote:

Originally Posted by science_man_88

well reformatting gets to:

M_m = 1 mod (m(m-1))

we know:

M_m = 1 mod m, if m is prime

so M_m would need the correct residue mod (m-1) for this to work.

I can prove the correct residue for particular values of m, should the conjecture be provable.

science_man_88 · 2012-09-16, 22:10

Quote:

Originally Posted by Stan

I can prove the correct residue for particular values of m, should the conjecture be provable.

the residue not already listed must be 1 for your conjecture to work at last check.

science_man_88 · 2012-09-16, 22:37

Quote:

Originally Posted by science_man_88

the residue not already listed must be 1 for your conjecture to work at last check.

just realized that doesn't matter except to tell which m it will find not what type. because M_m mod m =1 is needed for the formula and that only happens if m is prime it proves m is prime. Now what's the proof of the infinitude of the Mersenne primes ?

ewmayer · 2012-09-17, 01:18

A comparison with the Wieferich primes might be fruitful.

LaurV · 2012-09-17, 09:38

This conjecture is false, and a counterexample can be "analytically" computed. You have not so much chance to find a counterexample by trials.

Code:

(16:37:10) gp > Mod(2,(2^43-1)*(2^43-2))^(2^43-1)
%3 = Mod(2, 77371252455309878902128642)
(16:37:16) gp > Mod(2,(2^163-1)*(2^163-2))^(2^163-1)
%4 = Mod(2, 136703170298938245273281389194851335334573089430790701237314721230585174013975804408997831182909442)
(16:37:26) gp >

None of those are primes, and the same for all the numbers in ATH's list which are not exponents of a mersenne prime.

Edit: a nice puzzle should be to find the smallest counterexample (i.e. below 2^43-1).

axn · 2012-09-17, 09:57

Quote:

Originally Posted by LaurV

Edit: a nice puzzle should be to find the smallest counterexample (i.e. below 2^43-1).

With some GPU assist, this should be very doable [Actually, it is doable even w/o GPU, but...]. Perhaps rogue can adopt his wwww code to search for them.

EDIT:- We can just start with the list of base 2 psuedoprimes (as mentioned by SB), duh!

EDIT: This list should be sufficient

Batalov · 2012-09-17, 09:58

You didn't have to check for 2-PRP (obvious for 2^n-1), just for the condition #2:
Mod(2,2^43-2)^(2^43-1)==2
%9 = 1
See post #12.

LaurV · 2012-09-17, 10:21

Yes, sure. And I could use 1<<43-1

(which is faster, but may confuse the OP).
I just wanted to show it clear why is so. Of course I considered the fact that for every prime p, we have Mp is a 2-SPRP. This is how I constructed the counterexample, observing that if p is (using your terminology) quasi-prime, then 2^p-1 is also quasi prime. That is why for all primes p in ATH's list, then 2^p-1 will also be in ATH's list. But except p=3, 7, 127, few others, all remaining have Mp composite, but Mp is 2-SPRP and 2-quasiPrime. So here we are.

I did not "check" for it, I just typed it.

as I said, it is "analytically" constructed.

2012-09-17, 09:38	#19
LaurV Romulan Interpreter Jun 2011 Thailand 10010110001011₂ Posts	This conjecture is false, and a counterexample can be "analytically" computed. You have not so much chance to find a counterexample by trials. Code: (16:37:10) gp > Mod(2,(2^43-1)(2^43-2))^(2^43-1) %3 = Mod(2, 77371252455309878902128642) (16:37:16) gp > Mod(2,(2^163-1)(2^163-2))^(2^163-1) %4 = Mod(2, 136703170298938245273281389194851335334573089430790701237314721230585174013975804408997831182909442) (16:37:26) gp > None of those are primes, and the same for all the numbers in ATH's list which are not exponents of a mersenne prime. Edit: a nice puzzle should be to find the smallest counterexample (i.e. below 2^43-1). Last fiddled with by LaurV on 2012-09-17 at 09:44

2012-09-17, 10:21	#22
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	Yes, sure. And I could use 1<<43-1 (which is faster, but may confuse the OP). I just wanted to show it clear why is so. Of course I considered the fact that for every prime p, we have Mp is a 2-SPRP. This is how I constructed the counterexample, observing that if p is (using your terminology) quasi-prime, then 2^p-1 is also quasi prime. That is why for all primes p in ATH's list, then 2^p-1 will also be in ATH's list. But except p=3, 7, 127, few others, all remaining have Mp composite, but Mp is 2-SPRP and 2-quasiPrime. So here we are. I did not "check" for it, I just typed it. as I said, it is "analytically" constructed. Last fiddled with by LaurV on 2012-09-17 at 10:24

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

2012-09-16, 20:20	#12
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	So it seems to be two tests rolled into one: one 2-PRP and the other a quazi-PRP (2^m-2==0 (MOD m-1)). To pass the second test, the number cannot be divisble by 2 or 3, but quite a few composites pass. Now, need to find a intersection of 2-pseudopromes with the second test.....

2012-09-17, 01:18	#18
ewmayer ∂²ω=0 Sep 2002 República de California 103×113 Posts	A comparison with the Wieferich primes might be fruitful.

2012-09-17, 09:58	#21
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	You didn't have to check for 2-PRP (obvious for 2^n-1), just for the condition #2: Mod(2,2^43-2)^(2^43-1)==2 %9 = 1 See post #12.