Prime conjecture - Page 3

Batalov · 2012-09-17, 10:33

The answer is 91625794219

Batalov · 2012-09-17, 10:48

I've spent too much time trying to find a Carmichael number with this property. Didn't find one.
Then, the b-list for A001567 turned out to be enough. (too easy!)

Now, tried axn's Galway list. (took some time to fetch!)
==> Just this value and 2^43-1.

LaurV · 2012-09-17, 11:33

Quote:

Originally Posted by Batalov

91625794219

(I was thinking about fetching that list when I get home after work, but I just arrived and sat down and saw your result. Well done! Respect!)

ATH · 2012-09-17, 12:05

Quote:

Originally Posted by Batalov

Now, tried axn's Galway list. (took some time to fetch!)
==> Just this value and 2^43-1.

Tested this list of 31,894,014 SPRP base2 < 2⁶⁴: http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
and found two more composite example:
1557609722332488343
18216643597893471403

So 4 total < 2⁶⁴.

ATH · 2012-09-17, 15:37

I realized I had to test all 118,968,378 base 2 prps below 2⁶⁴ not "just" the strong prps, but this gave no other solutions.

Stan · 2012-09-18, 13:11

Quote:

Originally Posted by LaurV

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).

Trying gp>Mod(2,(2^127-1)*(2^127-2))^(127-1) produced a similar result.
E.g. %1 = Mod(2, a very long even number)
Does this mean 2¹²⁷-1 is not prime, or am I being silly?
What does Mod(2, 77371252455309878902128642) imply?

LaurV · 2012-09-18, 14:37

@Batalov: see? what did I tell you?

@Stan: The "even" number you see is the product of m and m-1, where m=2^43-1. The small program proves that 2^m is equal to 2 (mod m(m-1)) for this particular m, which is composite, therefore your conjecture is false, because I found a composite m for which 2^m=2 (mod m(m-1)). Read the small gp example as:

$2^{2^{43}-1}=2$ when you interpret it (mod $(2^{43}-1)\cdot(2^{43}-1-1)$ ).

The expression "a^b (mod c)" is written in pari/gp as "Mod(a,c)^b".

edit: Regardless of the fact that your expression is wrong, as you only raise the number at 127-1, and not at 2^127-1, in your example m=2^127-1 which is prime, but in mine, 2^43-1 is NOT, and still verifies your conjecture.

Batalov · 2012-09-18, 21:24

Quote:

Originally Posted by Stan

Does this mean 2¹²⁷-1 is not prime, or am I being silly?
What does Mod(2, 77371252455309878902128642) imply?

It implies nothing, because you haven't proven any properties of your "test".

Furthermore, the contributors to this thread proved the opposite of what you sought:
as demonstrated above, both prime and composite numbers can pass the test.
Therefore: passing the test implies nothing about the character of the input number.

Batalov · 2012-09-18, 21:38

Quote:

Originally Posted by LaurV

@Batalov: see? what did I tell you?

I know. I think I gathered that you suggested to speak slowly... and verbously. Ok, this can be done.

Let's do this:

Code:

Suppose 2^m = 2 (MOD m(m-1))
This means: 2^m - 2 = k m(m-1), with some k
This in turn means
1) 2^m - 2 = 0 (MOD m)   
AND
2) 2^m - 2 = 0 (MOD m-1)
 
Now, condition 1) is the 2-PRP test. All primes and composite numbers in sequence A001567 pass it. 
Condition 2) is just some conguence - many prime and composite numbers pass it.
 
Counterexamples 91625794219, 2^43-1 and others demonstrate that 
there exist composites that pass both tests (or equivalently, the original proposed test).
 
Also, many primes do not pass the OP test. 
Therefore, the OP test does not improve on the 2-PRP test 
and if anything, only make the 2-PRP test worse. 
 
P.S. Of course, in the context of Mersenne numbers alone, 2-PRP test is moot: all of them pass it.

LaurV · 2012-09-19, 03:05

Much better than I could say it!

alpertron · 2012-09-19, 13:13

It is interesting to notice that 91625794219 = (2³⁸ - 2¹⁹ + 1)/3

2012-09-18, 14:37	#29
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	@Batalov: see? what did I tell you? @Stan: The "even" number you see is the product of m and m-1, where m=2^43-1. The small program proves that 2^m is equal to 2 (mod m(m-1)) for this particular m, which is composite, therefore your conjecture is false, because I found a composite m for which 2^m=2 (mod m(m-1)). Read the small gp example as: $2^{2^{43}-1}=2$ when you interpret it (mod $(2^{43}-1)\cdot(2^{43}-1-1)$ ). The expression "a^b (mod c)" is written in pari/gp as "Mod(a,c)^b". edit: Regardless of the fact that your expression is wrong, as you only raise the number at 127-1, and not at 2^127-1, in your example m=2^127-1 which is prime, but in mine, 2^43-1 is NOT, and still verifies your conjecture. Last fiddled with by LaurV on 2012-09-18 at 14:58

2012-09-19, 03:05	#32
LaurV Romulan Interpreter Jun 2011 Thailand 7·1,373 Posts	Much better than I could say it! Last fiddled with by LaurV on 2012-09-19 at 03:05 Reason: then -> than (I always make this typo!)

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-17, 10:33	#23
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	The answer is 91625794219

2012-09-17, 10:48	#24
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10010100000101₂ Posts	I've spent too much time trying to find a Carmichael number with this property. Didn't find one. Then, the b-list for A001567 turned out to be enough. (too easy!) Now, tried axn's Galway list. (took some time to fetch!) ==> Just this value and 2^43-1.

2012-09-17, 15:37	#27
ATH Einyen Dec 2003 Denmark C57₁₆ Posts	I realized I had to test all 118,968,378 base 2 prps below 2⁶⁴ not "just" the strong prps, but this gave no other solutions.

2012-09-19, 13:13	#33
alpertron Aug 2002 Buenos Aires, Argentina 556₁₆ Posts	It is interesting to notice that 91625794219 = (2³⁸ - 2¹⁹ + 1)/3