GCD, sieves, fast exponentiation — number theory with every intermediate value shown.
5 visualizations
Finds the greatest common divisor by repeatedly replacing (a, b) with (b, a mod b) until b is 0.
Finds all primes up to n by repeatedly crossing out the multiples of each prime.
Computes xⁿ (optionally mod m) in O(log n) multiplications by repeatedly squaring — the engine behind modular exponentiation in cryptography.
Decomposes n into its prime factors by dividing out each candidate 2…√n; whatever remains above 1 is itself prime.
Computes gcd(a, b) plus the Bézout coefficients x, y with a·x + b·y = gcd — the key to modular inverses.