Number Theory Toolbox – Primes, Factorization & Modular Arithmetic
Explore the arithmetic of integers with an interactive number theory lab. Factor numbers, test primality, list divisors, compute Euler’s totient and the Möbius function, find GCD/LCM, Bézout coefficients, and work in modular arithmetic – all in one place.
Interactive number theory toolbox
Positive or negative integer, |n| ≤ 1,000,000,000 recommended.
Optional, used for GCD, LCM and Bézout coefficients.
Positive integer ≥ 2, used for n mod m and modular inverses.
For n
For n and m
Modular arithmetic
Prime factorization & arithmetic functions
Decompose n into its prime factors and compute classic multiplicative functions: number of divisors, sum of divisors, Euler’s totient φ(n), and the Möbius function μ(n).
–
Enter n and click “Factor & arithmetic functions” to see its arithmetic profile. For large n, this may take a moment; extremely large or prime-like numbers may be rejected.
GCD, LCM & Bézout coefficients for n and m
Compute the greatest common divisor (GCD), least common multiple (LCM), and integers x, y such that gcd(n, m) = x·n + y·m (Bézout’s identity).
–
–
If both n and m are zero, gcd and lcm are undefined. If exactly one is zero, gcd is |the other|, and lcm is 0 by convention in this tool.
Modular arithmetic: reduction & inverses
Work in the ring of integers modulo m. Reduce n modulo m and, when gcd(n, m) = 1, compute the modular inverse of n (so that n·n⁻¹ ≡ 1 mod m).
–
–
A modular inverse exists if and only if gcd(n, m) = 1. In that case, the toolbox finds an integer n⁻¹ such that n·n⁻¹ ≡ 1 (mod m), reported in the range 0 ≤ n⁻¹ < m.
What is number theory?
Number theory is the study of integers and their arithmetic properties. It covers topics such as divisibility, prime numbers, congruences, Diophantine equations, and arithmetic functions. Many modern applications – from cryptography and coding theory to computer algebra and random number generation – rely deeply on number-theoretic tools.
This page focuses on a practical core: prime factorization, arithmetic functions (like Euler’s totient), greatest common divisors, and modular arithmetic. The calculator is designed to help you experiment with these objects and build intuition.
Prime factorization and arithmetic functions
Any non-zero integer \(n\) can be written (up to sign and ordering) as a product of prime powers:
Once we know the prime factorization of \(|n|\), many number-theoretic functions become easy to compute:
- The number of positive divisors \(d(n)\) (also written \(\tau(n)\)) is \[ d(n) = (e_1 + 1)(e_2 + 1)\cdots(e_k + 1). \]
- The sum of positive divisors \(\sigma(n)\) is \[ \sigma(n) = \prod_{i=1}^{k} \frac{p_i^{e_i+1} - 1}{p_i - 1}. \]
- Euler’s totient \(\varphi(n)\), the number of integers in \([1,n]\) that are coprime to \(n\), satisfies \[ \varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right). \]
-
The Möbius function \(\mu(n)\) equals:
- \(0\) if any prime divides \(n\) with exponent at least 2,
- \(1\) if \(n\) is a product of an even number of distinct primes,
- \(-1\) if \(n\) is a product of an odd number of distinct primes,
- and by convention \(\mu(1) = 1\).
The toolbox implements these formulas directly from the factorization of \(|n|\). Negative inputs are handled by separating the sign; divisors are always listed as positive divisors of \(|n|\).
GCD, LCM and Bézout’s identity
Given two integers \(n\) and \(m\), their greatest common divisor \(\gcd(n, m)\) is the largest integer that divides both. Their least common multiple \(\operatorname{lcm}(n, m)\) is the smallest positive integer divisible by both.
If at least one of \(n, m\) is non-zero, then \[ \gcd(n, m)\cdot \operatorname{lcm}(n, m) = |n m|. \]
Bézout’s identity states that there exist integers \(x, y\) such that \[ \gcd(n, m) = x n + y m. \]
The toolbox uses the (extended) Euclidean algorithm to compute \(\gcd(n, m)\), \(\operatorname{lcm}(n, m)\), and one specific pair \((x, y)\) of Bézout coefficients, then verifies the identity numerically.
Modular arithmetic and inverses
In modular arithmetic we work with congruence classes modulo a positive integer \(m\). Two integers \(a\) and \(b\) are congruent modulo \(m\) if their difference is divisible by \(m\):
The reduction of \(n\) modulo \(m\) is the unique integer \(r\) with \(0 \le r < m\) such that \(n \equiv r \pmod{m}\).
An integer \(n\) has a multiplicative inverse modulo \(m\) if there exists an integer \(n^{-1}\) with:
A modular inverse exists exactly when \(\gcd(n, m) = 1\). In this case the toolbox uses the extended Euclidean algorithm to find such an \(n^{-1}\) and reports it in reduced form \(0 \le n^{-1} < m\).
Worked example
Take \(n = 360\) and \(m = 84\).
- Factorization: \[ 360 = 2^3 \cdot 3^2 \cdot 5. \] The toolbox reports this factorization and lists all positive divisors.
- Arithmetic functions: \[ d(360) = (3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24, \] \[ \varphi(360) = 360\left(1-\frac{1}{2}\right) \left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right) = 96. \]
- GCD/LCM and Bézout: \[ \gcd(360, 84) = 12, \quad \operatorname{lcm}(360, 84) = 2520. \] The tool also provides integers \(x, y\) such that \(12 = x\cdot 360 + y\cdot 84\).
- Modular arithmetic: with modulus \(m = 17\), \(360 \equiv 3 \pmod{17}\). Since \(\gcd(360, 17) = 1\), the calculator finds the unique inverse \(360^{-1} \pmod{17}\).
FAQ – using the number theory toolbox
What happens if I enter a very large integer?
Factoring large integers is computationally hard in general. This toolbox uses straightforward methods suitable for integers up to about one billion in absolute value. Beyond that, it may reject the input or take too long. For cryptographic sizes (hundreds or thousands of bits), specialized libraries are required.
Are the results exact or approximate?
All integer quantities (factors, divisor counts, GCD, LCM, totient, Möbius, modular inverses) are computed exactly using integer arithmetic. There is no rounding error for these values, as long as they fit within JavaScript’s safe integer range (±9,007,199,254,740,991).
Why do I sometimes get “no modular inverse”?
A modular inverse exists only when n and the modulus m are coprime, meaning gcd(n, m) = 1. If gcd(n, m) > 1, the equation n·x ≡ 1 (mod m) has no solution, and the toolbox reports that no inverse exists in the ring ℤ/mℤ.
Can I use this to generate primes for cryptography?
No. This toolbox is not intended as a cryptographically secure prime generator or key generator. It is a teaching and exploration tool for small to medium-sized integers. Cryptographic applications require specialized, audited libraries with strong randomness guarantees.