THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.

DOCUMENTATION CENTER SEARCH

PRIMALITY PROVING PACKAGE SYMBOL

PrimeQCertificate

PrimeQCertificate[n]
gives a certificate that n is prime or that n is composite.

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

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`"]