Number Theory Toolkit
Factor integers into primes, test primality with Miller–Rabin, compute Euler's totient, GCD and LCM — all instantly in your browser.
Factorize & analyze
Enter a positive integer. Factorization is limited to |n| ≤ 10¹² to stay fast.
GCD & LCM
Greatest common divisor and least common multiple of two integers.
How it works
Prime factorization uses trial division: it tests divisors from 2 up to √n, skipping even numbers after 2. Because the work grows with √n, inputs are capped at 10¹² (√10¹² = 10⁶ divisions — milliseconds in JavaScript; much larger and it would stall your tab).
Primality testing uses the Miller–Rabin test with bases 2, 7 and 61, which is deterministic — not probabilistic — for every n below 2³²: no false "prime" verdicts in that range. Small primes up to 37 are checked by direct division first.
Euler's totient φ(n) counts the integers 1 ≤ k ≤ n that are coprime to n. It is computed from the prime factorization via φ(n) = n·∏(1 − 1/p) over the distinct prime factors p of n — the same formula that underlies RSA key generation. GCD uses Euclid's algorithm; LCM follows from lcm(a, b) = |a·b| / gcd(a, b).
Frequently asked questions
How reliable is the primality test?
Completely reliable below 2³² (about 4.3 billion): with bases 2, 7 and 61, Miller–Rabin is proven to have no false positives in that range. Combined with trial division by small primes first, everyday inputs are classified with certainty.
Why can't I factorize numbers above 10¹²?
Trial division checks every candidate divisor up to √n. For n = 10¹² that is a million divisions — fast. For n = 10¹⁸ it would be a billion — your browser tab would freeze. Serious factorization of huge numbers needs advanced algorithms (Pollard's rho, quadratic sieve) that belong on a server, not a web page.
What is Euler's totient φ(n) good for?
It counts how many numbers below n share no factor with n. Its most famous use is RSA encryption, where φ(p·q) = (p−1)(q−1) for primes p, q determines the public and private keys. It also appears in Euler's theorem: a^φ(n) ≡ 1 (mod n) whenever a and n are coprime.
What does it mean for two numbers to be coprime?
Two integers are coprime when their greatest common divisor is 1 — they share no prime factor. For example, 8 and 15 are coprime, while 48 and 180 are not (they share gcd 12). The calculator tells you either way.