5

There is a Wikipedia article about that evil Belphegor's prime, but the references there seem relatively weak. Is this number actually a prime?

Pichi Wuana
  • 923
h22
  • 223
  • 4
    This is small enough that Wolfram can check it, it is prime. – siegehalver Mar 19 '16 at 16:02
  • 4
    Yes. –  Mar 19 '16 at 16:02
  • http://www.wolframalpha.com/input/?i=isprime%5B1000000000000066600000000000001%5D – Sil Mar 19 '16 at 16:02
  • With echo "isprime(1000000000000066600000000000001)" | gp, the answer is %1 = 1. – egreg Mar 19 '16 at 16:04
  • 3
    Wolfram does a probable prime test, unless you have Mathematica with the PrimalityProving package and use ProvablePrimeQ. Pari/GP's isprime(), as @egreg shows, does a proof (BLS75 or APR-CL). You can also put it in http://sti15.com/nt/primality.cgi and get a BLS75 Theorem 5 proof with certificate for this number. – DanaJ Mar 20 '16 at 01:47
  • Mathematica gives a Pratt certificate: {1000000000000066600000000000001, 3, {2, {5, 2, {2}}, {5365487, 5, {2, {7, 3, {2, {3, 2, {2}}}}, {19, 2, {2, {3, 2, {2}}}}, {23, 5, {2, {11, 2, {2, {5, 2, {2}}}}}}, {877, 2, {2, {3, 2, {2}}, {73, 5, {2, {3, 2, {2}}}}}}}}, {931881859, 2, {2, {3, 2, {2}}, {155313643, 2, {2, {3, 2, {2}}, {11, 2, {2, {5, 2, {2}}}}, {37, 2, {2, {3, 2, {2}}}}, {63601, 7, {2, {3, 2, {2}}, {5, 2, {2}}, {53, 2, {2, {13, 2, {2, {3, 2, {2}}}}}}}}}}}}}}, in format explained at http://mathematica.stackexchange.com/q/110549/30771 – Patrick Stevens Mar 20 '16 at 10:15
  • 1
    Curiously it appears that $1000000000000077700000000000001$ is also a prime – Anthony Jun 10 '19 at 17:37

2 Answers2

8

As far as I know, Pari/GP offers a deterministic primality test (contrary to the probability test of Mathematica).

                            GP/PARI CALCULATOR Version 2.7.3 (released)
                    i386 running darwin (x86-64/GMP-6.0.0 kernel) 64-bit version
       compiled: May 24 2015, Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
                                      threading engine: single
                           (readline v6.3 enabled, extended help enabled)

                               Copyright (C) 2000-2015 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY 
WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
? isprime(1000000000000066600000000000001)
%1 = 1

This is confirmed by http://sti15.com/nt/primality.cgi where, choosing “Proof”, we get

Proving... output indicates progress. Certificate and timing at end. $1000000000000066600000000000001$ is DEFINITELY PRIME. Time taken: $0.523$ milliseconds.

[MPU - Primality Certificate]
Version 1.0

Proof for:
N 1000000000000066600000000000001

Type BLS5
N  1000000000000066600000000000001
Q[1]  5
A[0]  3
----

(Thanks to DanaJ for suggesting the site for the certificated primality test.)

egreg
  • 238,574
  • What do Q[1] and A[0] mean? – Nathaniel Bubis Mar 20 '16 at 10:15
  • @nbubis See https://en.wikipedia.org/wiki/Primality_certificate and http://mathworld.wolfram.com/PrimalityCertificate.html – egreg Mar 20 '16 at 10:23
  • @nbubis https://github.com/danaj/Math-Prime-Util-GMP/blob/master/xt/proof-text-format.txt has a description, including reference to the paper. The factors of N-1 used are 2 (implied as Q[0]) and 5. With their multiplicity, that's enough to meet the requirements of the theorem. A[0] says the 'a' value to use for the factor 2 in the theorem is 3 for this number. There are verifiers in C and Perl that parse the text (they also handle Primo certificates). Pari/GP has a way to show similar type (not format) certificates, and has an excellent APR-CL system, but it has no certs. – DanaJ Mar 20 '16 at 10:23
5

Both Mathematica and WolframAlfa confirm that this number is prime:

In[42]:= PrimeQ[1000000000000066600000000000001]

Out[42]= True
Kamil Jarosz
  • 4,984
ahkaissi
  • 51
  • 2
    PrimeQ is a probable prime test. Pari/GP's isprime() does a proof. – DanaJ Mar 20 '16 at 01:43
  • @DanaJ Not entirely true: https://mathematica.stackexchange.com/questions/132670/some-information-about-primeq-function?rq=1 – Klangen Jun 21 '19 at 13:46
  • @Klangen, there is a primality proving package for Mathematica though the documentation says it uses a different function ProvablePrimeQ[]. I don't believe Wolfram Alpha supports this at all (certainly not in the free version). So in reference to ahkaissi's answer that PrimeQ confirm the number this size is prime, I believe my statement is true. – DanaJ May 20 '20 at 10:59