My Math Forum Conjecture about primes of a special form

 Number Theory Number Theory Math Forum

 November 20th, 2013, 09:46 AM #1 Member   Joined: Jul 2010 Posts: 83 Thanks: 2 Conjecture about primes of a special form $SatisfiesCondition(n) = \begin{cases}true&\mbox{ if } 2^{(n-1)/2}\equiv-1\pmod n\\ false&\mbox{ if } otherwise\end{cases}$ $SpecialPrime(n) = \begin{cases}true&\mbox{ if } SatisfiesCondition(n), SatisfiesCondition((n-1)/2)\\ false&\mbox{ if } otherwise\end{cases}$ In other words, some primes and all composites fail the test. 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?
 November 20th, 2013, 09:13 PM #2 Member   Joined: Jul 2010 Posts: 83 Thanks: 2 Re: Conjecture about primes of a special form I just realized something else: all of the above appear to be a subset of the safe primes!
 November 21st, 2013, 12:11 AM #3 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Conjecture about primes of a special form I think it's likely to be false, but the first counterexample might be large since even most primes fail these conditions. Indeed, there is no counterexample below 2^64.
November 21st, 2013, 01:09 AM   #4
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Re: Conjecture about primes of a special form

Quote:
 Originally Posted by CRGreathouse I think it's likely to be false, but the first counterexample might be large since even most primes fail these conditions. Indeed, there is no counterexample below 2^64.
Yes, but what of the fact that every number in the sequence happens to be a safe prime (I've done much searching and haven't found a single one yet that wasn't)? Just seems unlikely to be a mere coincidence, from a heuristic standpoint at least (speaking of heuristics, the primitive root of a safe prime is always either 2 or -2, and in the case of the sequence in question it's always the former). Also, I wonder if the quadratic non-residues thereof have anything to do with the seemingly "picky" selection of certain safe primes? I'll look into that... Anyway, thanks for the response. You have a pretty good intuition and grasp about these sorts of matters - I know well not to take your advice lightly.

 November 21st, 2013, 11:25 AM #5 Member   Joined: Jul 2010 Posts: 83 Thanks: 2 Re: Conjecture about primes of a special form Whoops, there was an error in my safe prime identification code. Having fixed it, it turns out that n=32140859 passes the SpecialPrime test but in that case (n-1)/2 is not a Sophie-Germaine, so the assumption that every value in the sequence is a safe prime is false. Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
November 21st, 2013, 11:46 AM   #6
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Conjecture about primes of a special form

Quote:
 Originally Posted by Sebastian Garth Yes, but what of the fact that every number in the sequence happens to be a safe prime (I've done much searching and haven't found a single one yet that wasn't)? Just seems unlikely to be a mere coincidence, from a heuristic standpoint at least (speaking of heuristics, the primitive root of a safe prime is always either 2 or -2, and in the case of the sequence in question it's always the former). Also, I wonder if the quadratic non-residues thereof have anything to do with the seemingly "picky" selection of certain safe primes? I'll look into that... Anyway, thanks for the response. You have a pretty good intuition and grasp about these sorts of matters - I know well not to take your advice lightly.
Better is to look at pseudoprimes, because any counterexample is of necessity a 2-pseudoprime congruent to 3 mod 4.

November 21st, 2013, 11:54 AM   #7
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Conjecture about primes of a special form

Quote:
 Originally Posted by Sebastian Garth Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
Unless you're checking above 18446744073709551616, don't bother...!

November 21st, 2013, 01:00 PM   #8
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Re: Conjecture about primes of a special form

Quote:
Originally Posted by CRGreathouse
Quote:
 Originally Posted by Sebastian Garth Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
Unless you're checking above 18446744073709551616, don't bother...!
Interesting. So why do you proffer that particular constant?

November 21st, 2013, 01:16 PM   #9
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Re: Conjecture about primes of a special form

Quote:
Originally Posted by CRGreathouse
Quote:
 Originally Posted by Sebastian Garth Yes, but what of the fact that every number in the sequence happens to be a safe prime (I've done much searching and haven't found a single one yet that wasn't)? Just seems unlikely to be a mere coincidence, from a heuristic standpoint at least (speaking of heuristics, the primitive root of a safe prime is always either 2 or -2, and in the case of the sequence in question it's always the former). Also, I wonder if the quadratic non-residues thereof have anything to do with the seemingly "picky" selection of certain safe primes? I'll look into that... Anyway, thanks for the response. You have a pretty good intuition and grasp about these sorts of matters - I know well not to take your advice lightly.
Better is to look at pseudoprimes, because any counterexample is of necessity a 2-pseudoprime congruent to 3 mod 4.
Right, good point.

November 22nd, 2013, 03:38 PM   #10
Member

Joined: Jul 2010

Posts: 83
Thanks: 2

Re: Conjecture about primes of a special form

[quote=Sebastian Garth]
Quote:
Originally Posted by CRGreathouse
Quote:
 Originally Posted by "Sebastian Garth":ds17ebf9 Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
Unless you're checking above 18446744073709551616, don't bother...!
Interesting. So why do you proffer that particular constant?[/quote:ds17ebf9]

Oh, right...2^64.

 Tags conjecture, form, primes, special

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post goodjobbro Number Theory 2 December 1st, 2013 11:38 PM Al7-8Ex5-3:Fe#!D%03 Number Theory 3 September 30th, 2013 05:52 PM miket Number Theory 5 May 15th, 2013 06:35 PM ibougueye Number Theory 1 August 13th, 2012 09:24 PM Bogauss Number Theory 32 March 1st, 2012 07:30 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top