Mathematics desk
< November 20	<< Oct \| November \| Dec >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 21

Conjecture about primes of a special form

I have a conjecture about primes of a certain form:

First a definition:

$SatisfiesCondition(n)={\begin{cases}true&{\mbox{ if }}2^{(n-1)/2}\equiv -1{\pmod {n}}\\false&{\mbox{ if }}otherwise\end{cases}}$

And now the result:

$SpecialPrime(n)={\begin{cases}true&{\mbox{ if }}SatisfiesCondition(n),SatisfiesCondition((n-1)/2)\\false&{\mbox{ if }}otherwise\end{cases}}$

(If your browser isn't capable of displaying the above equations, refer to the image generated at http://mathbin.net/448385)

The conjecture is simply that any number that passes the SpecialPrime test is prime (some primes and all composites fail). The first 10 integers in the sequence are 5, 11, 59, 107, 347, 587, 1019, 1307, 2027, and 2459. Is this a well-known conjecture or theory? Also, I get the feeling that this could be generalized somehow. Any thoughts on this? Counterexamples? -Sebastian Garth (talk) 04:55, 21 November 2013 (UTC)[reply]

I wrote a little program to test this up to 5000000. Assuming my calculations are correct, there are 4259 numbers that pass the test, the last is 4995323, and none are composite. The SatisfiesCondition formula is closely related to Euler pseudoprimes and Euler–Jacobi pseudoprimes.

Yes, the result was independently verified up to 2^64 by a prominent mathematician as well. Still, he did have some reservations that a counterexample might be very large, although he didn't elaborate. Needless to say, I'm anxiously awaiting an explanation from him on that point! -Sebastian Garth (talk) 23:33, 22 November 2013 (UTC)[reply]

There are numbers that satisfy the first condition without being prime, I found 476971, 877099, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 3090091, 3116107 to be the ones under 5000000. They are rare but I assume that if you find enough of them you eventually get a p so that (p-1)/2 is a prime congruent to 3 or 5 mod 8. --RDBury (talk) 17:14, 22 November 2013 (UTC)[reply]

Yes, many composites pass the first condition. -Sebastian Garth (talk) 23:33, 22 November 2013 (UTC)[reply]

If you've already got a specialist in the field working on it then I'm not sure that there would be anything helpful that I could add. Though there is one thing that might be worth mentioning. I bumped my search up to 50000000 to get 37 composites p satisfying the first condition. I then factored the numbers (p-1)/2 on the theory that if there were primes in this set then there would be a good chance that the first condition would apply to them as well. They are all composite and in fact most of them have more factors than you would expect for randomly chosen odd numbers in the range 1 to 25000000. For example 81% were divisible by 3, and 38% were divisible by 5. I'm not sure if this pattern continues beyond 50000000 and I have no idea why it would if it does, but it does seem like an anomaly worth investigating. --RDBury (talk) 17:13, 23 November 2013 (UTC)[reply]