--- title: "Prime Number Checker: Is It Prime? | Prime Orchard" description: "Check whether any number up to 2,000 digits is prime and see why: the factor found or the Miller–Rabin proof, plus the next and previous primes." url: https://primeorchard.top/ --- 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. 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](https://www.mersenne.org/primes/); the largest known primes are all of this kind. ## 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 - Sorenson J, Webster J. Strong pseudoprimes to twelve prime bases. *Mathematics of Computation* 86 (2017), 985–1003: the smallest strong pseudoprime to the first 13 prime bases, 3,317,044,064,679,887,385,961,981, as listed in [OEIS A014233](https://oeis.org/A014233). - Rabin MO. Probabilistic algorithm for testing primality. *Journal of Number Theory* 12 (1980), 128–138; overview in [Miller–Rabin primality test](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test). - Baillie R, Wagstaff SS. Lucas pseudoprimes. *Mathematics of Computation* 35 (1980), 1391–1417; the strong Lucas test with Selfridge's parameters and its record: [Baillie–PSW primality test](https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test). - Great Internet Mersenne Prime Search, [list of known Mersenne primes](https://www.mersenne.org/primes/). ## More from the orchard Five more calculators that show their working, from factor trees to perfect numbers. - [Prime factorization](https://primeorchard.top/prime-factorization/): Any number broken into primes, with exponents, a drawn factor tree and the division ladder. - [GCD & LCM calculator](https://primeorchard.top/gcd-lcm-calculator/): Two or more numbers, with every step of Euclid's algorithm and Bézout's identity. - [Prime numbers list](https://primeorchard.top/prime-numbers-list/): Sieve any range up to 1014, count the primes, then copy or download them. - [Nth prime calculator](https://primeorchard.top/nth-prime-calculator/): The 100th, millionth or 50-millionth prime, and how many primes lie below any number. - [Divisors calculator](https://primeorchard.top/divisors-calculator/): Every divisor of a number, their count and sum, and whether it is perfect, abundant or deficient. ## Recommended Two free services from outside the orchard, useful when maths takes you online. Disposable email · no sign-up ### CleanTempMail Maths forums, puzzle sites and course platforms often want an email address before you can download a worksheet or post a question. CleanTempMail gives you a free temporary inbox at once, with no sign-up, a random or custom address on hundreds of domains, and messages deleted automatically after 3 days. [Open a temporary inbox](https://cleantempmail.com/) Disposable cloud browser · free checks ### WebTraceCheck Found a "prime number generator" download or a homework-help link you are not sure about? WebTraceCheck opens it in a disposable cloud browser on an isolated desktop that is deleted after each session, and its free DNS and domain lookup shows who is behind a site. [Try WebTraceCheck](https://webtracecheck.com/) ## 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.