Whether a number is prime, at any size, decided by deterministic Miller-Rabin rather than trial division. Prime factorisation, every divisor, the primes either side and Goldbach pairs.
Initializing in your browser…
The greatest common divisor and lowest common multiple of any whole numbers at any size, with the Euclidean algorithm written out, Bezout coefficients, and the two answers checked against each other.
Exact arithmetic on rationals, with both evaluation conventions named and the precedence table the parser runs on printed on the page.
Plot functions with a real expression parser, poles drawn as gaps, and roots, turning points and integrals found by bracketing with the check printed.
You want to know whether 561 is prime, and then whether 2^127 - 1 is.
Numbers
561, then 170141183460469231731687303715884105727
Result
Not prime: 561 = 3 x 11 x 17. Prime: 2^127 - 1, answered instantly.
561 is a Carmichael number: composite, and it passes a Fermat primality test for every base coprime to it, which is why intuition and a naive test both fail on it. Primality here is Miller-Rabin over the first twelve primes, which Sorenson and Webster proved in 2015 is a DECISION PROCEDURE below 3,317,044,064,679,887,385,961,981, so under that bound the verdict is a proof and not a probability. That is also why the second number is possible at all: trial division would need about 10^19 steps and this takes microseconds. Above the bound the page says the answer is overwhelmingly likely rather than certain.
Whether a number is prime, its prime factorisation, all of its divisors, the primes either side of it and what class it belongs to. There is no upper limit worth mentioning: a twenty-five digit number is settled instantly, and 2^127 - 1 is settled instantly too.
Primality is decided by the Miller-Rabin test run over the first twelve primes as witnesses. That is not a probabilistic answer dressed up: Sorenson and Webster (2015) proved that this witness set is a DECISION PROCEDURE for every number below 3,317,044,064,679,887,385,961,981, which is twenty-five digits. Below that the verdict is a proof; above it the page says so rather than letting you assume otherwise. Trial division, by contrast, needs about 47 million steps for a number near 2^53 and cannot reach a twenty-five digit number at all.
**Why that matters for what you can ask.** The Carmichael numbers (561, 1105, 1729 and the rest) are composite numbers that pass a naive Fermat test, and they are correctly called composite here. 2147483647 and 2^127 - 1 are both prime and both answered in microseconds.
**Factorisation** is trial division on a 2, 3, 5 wheel and then Pollard's rho, which finds a factor of a large semiprime in about the fourth root of it rather than the square root. The factors are always multiplied back together as a check, and a search that runs out of budget says which part it could not finish rather than reporting a wrong answer. From the factorisation come the number of divisors, their sum, the sum of the proper ones (which is what makes a number perfect, abundant or deficient) and Euler's totient, all computed rather than counted, so they are available for numbers far too large to list the divisors of.
**What is not a number.** 0 and 1 are neither prime nor composite, and the page says why rather than just refusing: every number divides zero, and one is excluded so that every number above it has exactly one factorisation into primes. A decimal is refused by name, because only whole numbers are prime or composite.
**Primes in a range** are found by a segmented sieve, which is the right algorithm for the question and is why a window of a hundred numbers a million up is as quick as one at the start. Ranges up to 200,000 wide are sieved and a wider one is refused with its own size named.
Verify a primality claim, get a factorisation you can check, and see the divisor count and totient without listing anything.
The Carmichael numbers are here to be tried: they are composite and they fool a Fermat test. This one gets them right, and says which theorem makes it a proof.
Safe primes and Sophie Germain primes are named, and a number the size of an RSA exponent is answered instantly.
Every prime between 1,000,000 and 1,000,100, sieved rather than tested one at a time.
There is no practical limit. Below 3,317,044,064,679,887,385,961,981 the answer is a proof; above it the page says the answer is overwhelmingly likely rather than certain, which is the honest thing to say.
No, and neither is 0. One is excluded so that every whole number above it factorises into primes in exactly one way, which is the reason rather than a convention with no cause.
A composite number that passes a Fermat primality test for every base coprime to it. 561, 1105 and 1729 are the first three, and this tool calls all of them composite.
Only whole numbers are prime or composite. Reading it as 17 would answer a question you did not ask.
Twins differ by two, like 17 and 19. A Sophie Germain prime p has 2p + 1 prime as well, and that 2p + 1 is the safe prime it makes. Safe primes matter in cryptography.
Because there can be too many to draw. The count, the sum and the totient still come out of the factorisation and are exact.
Every calculation runs locally in your browser. Your numbers and expressions are not transmitted or stored.