Mathematica 9 is now available
SEARCH MATHEMATICA 8 DOCUMENTATION
THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.
Primality Proving Package >
Primality Proving Package SymbolTutorials »|See Also »|More About »

PrimeQCertificate

PrimeQCertificate[n]
gives a certificate that n is prime or that n is composite.
  • PrimeQCertificate uses the Pratt certificate and the Atkin-Morain certificate for primality.
  • A certificate of compositeness is a list of 3 integers, either {a, n-1, n} or {a, 2, n}, with |a|!=1.
  • A prime p always satisfies ap-1Congruent1 mod p. The certificate {a, n-1, n} can be used to show that n is composite by demonstrating that an-1NotCongruent1 mod n.
  • Any number a whose square is 1mod n for n prime must satisfy aCongruent±1 mod n. The certificate {a, 2, n} can be used to show that n is composite by demonstrating that aNotCongruent±1mod n and a2Congruent1 mod n.
  • 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.
EXAMPLESCLOSE ALL
Basic Examples   (2)
A certificate that can be used to prove that 1093 is a prime:
The same certificate can be obtained by using ProvablePrimeQ with the option "Certificate"->True:
A certificate that can be used to prove that 1093 3511 is composite:
The output is a list of 3 integers that indicate 1093 3511 is composite, and that it violates Fermat's little theorem for primes, 2p-1Congruent1 mod p 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 ProvablePrimeQ with the option "Certificate"->True:
In[3]:=
Click for copyable input
Out[3]=
 
Needs["PrimalityProving`"]
A certificate that can be used to prove that 1093 3511 is composite:
In[2]:=
Click for copyable input
Out[2]=
The output is a list of 3 integers that indicate 1093 3511 is composite, and that it violates Fermat's little theorem for primes, 2p-1Congruent1 mod p if p is prime:
In[3]:=
Click for copyable input
Out[3]=
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team