This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

PrimeQCertificate

PrimeQCertificate[n]
gives a certificate that n is prime or that n is composite.
  • uses the Pratt certificate and the Atkin-Morain certificate for primality.
  • A certificate of compositeness is a list of 3 integers, either or , with .
  • A prime p always satisfies . The certificate can be used to show that n is composite by demonstrating that .
  • Any number a whose square is for n prime must satisfy . The certificate can be used to show that n is composite by demonstrating that and .
  • A certificate of primality consists of a recursive list of certificates which prove that n is a prime if one or more smaller numbers are prime as well.
A certificate that can be used to prove that 1093 is a prime:
The same certificate can be obtained by using with the option True:
A certificate that can be used to prove that is composite:
The output is a list of 3 integers that indicate is composite, and that it violates Fermat's little theorem for primes, if p is prime:
Needs["PrimalityProving`"]
A certificate that can be used to prove that 1093 is a prime:
In[2]:=
Click for copyable input
Out[2]=
The same certificate can be obtained by using with the option True:
In[3]:=
Click for copyable input
Out[3]=
 
Needs["PrimalityProving`"]
A certificate that can be used to prove that is composite:
In[2]:=
Click for copyable input
Out[2]=
The output is a list of 3 integers that indicate is composite, and that it violates Fermat's little theorem for primes, if p is prime:
In[3]:=
Click for copyable input
Out[3]=