Prime OrchardPrime checker, factorization & GCD/LCM

Prime checker

Is this number prime?

Type any whole number up to 2,000 digits, or an expression such as 2^61 − 1. You get the answer, the reasoning behind it and the nearest primes on either side.

Digits (spaces and commas are ignored), or an expression with + − × ^ ! and brackets, such as 2^61-1 or 20!+1.

Try:

2,147,483,647 (10 digits) is prime

Proven by deterministic Miller–Rabin

Why

  1. No prime below 1,000 divides it (trial division by the first 168 primes).
  2. Write n − 1 = 2s × d with d odd: here s = 1 and d = 1,073,741,823.
  3. The Miller–Rabin test raises each base a to the power d and squares the result up to s − 1 times, mod n. For a prime the sequence must start at 1 or pass through n − 1. It does for all 13 bases 2, 3, 5, … 41.
    1. 2d mod n = 1
  4. Below 3.317 × 1024 that is a proof, not just evidence: the smallest number that fools all 13 bases is 3,317,044,064,679,887,385,961,981 (Sorenson and Webster, 2017).
  5. It is a Mersenne number, 231 − 1. Primes of this form are Mersenne primes; the largest known primes are all of this kind.
Previous prime
2,147,483,62918 below
Next prime
2,147,483,65912 above

How the checker decides

A prime is a whole number greater than 1 whose only divisors are 1 and itself: 2, 3, 5, 7, 11 and so on. Every other number above 1 is composite, a product of smaller primes.

For small numbers the checker uses trial division, dividing by 2, 3, 5, 7 and the primes after them. It can stop at the square root, because if n = a × b then one of a and b is at most √n. For 97 that means trying 2, 3, 5 and 7 (√97 ≈ 9.8); none divides it, so 97 is prime.

For big numbers that would take far too long, so it switches to the Miller–Rabin test, built on Fermat's little theorem: if n is prime, an−1 leaves remainder 1 on division by n. Write n − 1 = 2s × d with d odd. For a prime, the chain ad, a2d, a4d… (mod n) either starts at 1 or reaches n − 1. A base a that breaks this rule is a witness that n is composite, without naming a factor. Below 3.317 × 1024, the thirteen bases 2 to 41 leave no exceptions, so passing them is a proof.

Larger numbers get the Baillie–PSW test (Miller–Rabin base 2 plus a strong Lucas test) and seven extra bases. No composite number is known to pass it, but that is not a proof, so the result says "probable prime".

Sources

More from the orchard

Five more calculators that show their working, from factor trees to perfect numbers.

Questions

Why isn't 1 a prime number?

A prime has exactly two divisors and 1 has only one. Leaving 1 out also keeps factorizations unique: if 1 counted, 6 could be written 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 and so on.

What is a Carmichael number?

A composite number that passes Fermat's test for every base sharing no factor with it. The smallest is 561 = 3 × 11 × 17. Miller–Rabin is stricter than Fermat's test and is not fooled by them.

How big a number can I check?

Up to 2,000 digits. Above 200 digits the test runs in a background worker so the page stays responsive; 1,000 digits takes about a second on a laptop. Neighbouring primes are searched up to 1,000 digits.