4

Are there primes p=472n+1, where nZ+? Tested for all primes p<100,000,000 without equality.

3
  • I have read at least 2 posts on MSE that demonstrated the difficulties of finding primes in form of an+b by probabilistic arguments. Your case wouldn’t be much easier. Commented Jul 11, 2018 at 4:07
  • 2
    Rather than frame your search for primes by bounding p, it will be more meaningful to state the limit on n used in the search. Commented Aug 2, 2018 at 15:48
  • @hardmath True, but in the experiment I did, I needed fast primes to find numbers like 47. I should have done separate test runings for n=1,2, Commented Aug 4, 2018 at 7:19

2 Answers 2

8

Yes. We can start by quick Maple search, yielding for example n=583 (isprime(47*2^583+1)). Next ones are n=1483 and n=6115, I haven't found any others yet. We can speed up this search by noting that for certain n it is clear that it cannot be prime. For example if n is even, then we have 472n+1220+1=0(mod3). Similarly, if n is odd and n1mod4, then 472n+1221+1=0(mod5). This reduces search to n3(mod4) .

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 10223231172165+1 (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 p=k2n+1 with k odd and k<2n, and if there exists an integer a for which a(p1)/21modp, then p 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 a=3 and p=472583+1 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:
6
  • 1
    I'm not sure whether Maple actually does a primality test for numbers that large, or just a "probable" primality test. Commented Jul 11, 2018 at 4:21
  • There are guaranteed, practical primality tests for numbers of that size. Commented 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. Commented Jul 11, 2018 at 4:54
  • Interestingly, no primes occur for 6116n30000 Commented Dec 7, 2019 at 0:20
  • Update: No primes for 6116n40000 Commented Dec 7, 2019 at 0:24
8

Smallest m0 such that 2mn+1 is prime is tabulated at OEIS. The first "interesting" case is the one under discussion here, n=47; it's at most 8 for n<47, then 583 for n=47. For n=383 it's 6393, for n=2897 it's 9715, and it's known that for infinitely many n there is no such m. See the links at OEIS.

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.