Are there primes , where ? Tested for all primes without equality.
-
I have read at least 2 posts on MSE that demonstrated the difficulties of finding primes in form of by probabilistic arguments. Your case wouldn’t be much easier.Lee– Lee2018-07-11 04:07:51 +00:00Commented Jul 11, 2018 at 4:07
-
2Rather than frame your search for primes by bounding , it will be more meaningful to state the limit on used in the search.hardmath– hardmath2018-08-02 15:48:45 +00:00Commented Aug 2, 2018 at 15:48
-
@hardmath True, but in the experiment I did, I needed fast primes to find numbers like . I should have done separate test runings forLehs– Lehs2018-08-04 07:19:53 +00:00Commented Aug 4, 2018 at 7:19
2 Answers
Yes. We can start by quick Maple search, yielding for example (isprime(47*2^583+1)). Next ones are and , I haven't found any others yet. We can speed up this search by noting that for certain it is clear that it cannot be prime. For example if is even, then we have . Similarly, if is odd and , then . This reduces search to .
However as pointed out in comments, Maple performs probabilistic primality tests for such large numbers (one strong pseudo-primality test and one Lucas test per documentation https://www.maplesoft.com/support/help/maple/view.aspx?path=isprime), so there is a chance these could be false positives (although no such counter example has been yet found). Anyway further testing with some deterministic approach would be nice, and fortunately there is one very specific to these numbers! (see below)
It turns out these numbers are special case of what is called Proth numbers, and you are especially interested in Proth primes. In fact these numbers are popular in large prime search, largest currently known non Mersenne prime (as of 2018) is (https://primes.utm.edu/top20/page.php?id=3). The reason is there is very effective way to check their primality, using something called Proth's theorem. Roughly it states:
If with odd and , and if there exists an integer for which , then is a prime.
So this can be turned into an effective algorithm to verify primality of the cases found above by probabilistic test. And indeed, for and we already have a match, e.g.:
a := 3:
p := 47*2^583+1:
is((Power(a, (p-1)/2) mod p) = p-1);
So putting together, we can run something like (which I am sure could be optimized)
m:=1:
do:
n := 4*m+3:
p := 47*2^n+1:
if isprime(p) then
for a from 1 to 10 do
if is((Power(a, (p-1)/2) mod p) = p-1) then
print('n' = n, 'a' = a):
break:
end if:
end do:
end if:
m := m+1
end do:
-
1I'm not sure whether Maple actually does a primality test for numbers that large, or just a "probable" primality test.Gerry Myerson– Gerry Myerson2018-07-11 04:21:55 +00:00Commented Jul 11, 2018 at 4:21
-
There are guaranteed, practical primality tests for numbers of that size.Gerry Myerson– Gerry Myerson2018-07-11 04:27:23 +00:00Commented Jul 11, 2018 at 4:27
-
@GerryMyerson Turn's out there is specific test for these using something called Proth's theorem, see an edited answer.Sil– Sil2018-07-11 04:54:37 +00:00Commented Jul 11, 2018 at 4:54
-
Interestingly, no primes occur forMaximilian Janisch– Maximilian Janisch2019-12-07 00:20:20 +00:00Commented Dec 7, 2019 at 0:20
-
Update: No primes forMaximilian Janisch– Maximilian Janisch2019-12-07 00:24:26 +00:00Commented Dec 7, 2019 at 0:24
Smallest such that is prime is tabulated at OEIS. The first "interesting" case is the one under discussion here, ; it's at most 8 for , then for . For it's , for it's , and it's known that for infinitely many there is no such . See the links at OEIS.