The Fundamental Theorem of Arithmetic & Divisor Algebra
The Fundamental Theorem of Arithmetic (also known as the Unique Factorization Theorem) states that every positive integer n > 1 can be represented uniquely as a product of prime powers:
n = p1a1 ×p2a2 × … ×pkak
where p1 < p2 < … <pk are distinct prime numbers, and ai ≥ 1 are their positive integer multiplicities. This prime decomposition acts as the structural "DNA" of every natural number, completely defining its divisibility, totient, and algebraic properties.
Core Multiplicative Functions Derived from Prime Factors
In analytic number theory, an arithmetic function f is called multiplicative iff(a × b) = f(a) × f(b) whenever gcd(a, b) = 1. The three canonical functions computed by this tool are strictly multiplicative:
| Function | Symbol | Closed Formula | Example for 360 (2³ × 3² × 5¹) |
|---|---|---|---|
| Divisor Count | d(n) or τ(n) | ∏(ai + 1) | (3+1)(2+1)(1+1) = 24 factors |
| Divisor Sum | σ(n) | ∏(piai+1 − 1) / (pi − 1) | (15/1)(26/2)(24/4) = 15 × 13 × 6 = 1,170 |
| Euler's Totient | φ(n) | n × ∏(1 − 1/pi) | 360 × (1/2) × (2/3) × (4/5) = 96 coprime integers |
Computational Complexity: Trial Division vs. Pollard's ρ Heuristic
Factoring arbitrary composite integers is an asymmetric computational problem. While testing whether a number is prime can be accomplished in deterministic polynomial time via Miller-Rabin tests, discovering the prime factors of an unknown composite integer requires exploring vast combinatorial factor spaces:
- Trial Division (O(√n)): Checks successive prime candidates 2, 3, 5, 7, 11… up to √n. While optimal for numbers under 108 or numbers with small prime factors, trial division requires billions of modulo steps on large semiprimes.
- Pollard's ρ Algorithm (O(n1/4)): Deployed by OmniTools for larger composites. Pollard's ρ generates pseudo-random sequences using the polynomial mapping f(x) = (x2 + c) mod n. By the Birthday Paradox, cycle detection (via Brent's or Floyd's algorithm) reveals a collision modulo an unknown prime factor pin approximately O(√p) ≤ O(n1/4) steps, computing gcd(|x − y|, n) > 1 in milliseconds.
Bézout's Identity & The Extended Euclidean Algorithm
The Euclidean Algorithm is one of the oldest numerical algorithms in recorded history (c. 300 BCE), efficiently computing the Greatest Common Divisor (gcd) of two non-negative integers A and B through repeated Euclidean division remainders:
ri−1 = qi × ri + ri+1, 0 ≤ ri+1 < ri
Bézout's Identity establishes that the greatest common divisor can always be expressed as an integer linear combination of A andB:
A × x + B × y = gcd(A, B)
Step-by-Step Worked Walkthrough: A = 1071, B = 462
To compute gcd(1071, 462) and discover the integer Bézout coefficients (x, y), the Extended Euclidean algorithm runs forward divisions followed by backward substitution:
| Step | Euclidean Division | Quotient (q) | Remainder (r) |
|---|---|---|---|
| Step 1 | 1071 = 2 × 462 + 147 | q₁ = 2 | r₁ = 147 |
| Step 2 | 462 = 3 × 147 + 21 | q₂ = 3 | r₂ = 21 |
| Step 3 | 147 = 7 × 21 + 0 | q₃ = 7 | r₃ = 0 → gcd = 21 |
Next, backward substitution expresses remainder 21 in terms of initial inputs 1071 and 462:
Verification: 1071 × (−3) + 462 × 7 = −3213 + 3234 = 21. Thus, Bézout coefficients are x = −3 and y = 7.
Modular Multiplicative Inverse in RSA Cryptography
When gcd(A, M) = 1 (coprime), Bézout's identity simplifies to A × x + M × y = 1. Taking both sides modulo M yields A × x ≡ 1 (mod M). Here, x is precisely the modular multiplicative inverse of A modulo M.
In the RSA public-key cryptosystem, public encryption key e = 17 and totient φ(N) = 3120 require finding private decryption exponent d:
17 × d ≡ 1 (mod 3120) &implies; d = 2753
Verification: 17 × 2753 = 46,801 = (15 × 3120) + 1 ≡ 1 (mod 3120).
Practical Real-World Use Cases
- Deconstruct composite integers into prime powers: Compute the canonical prime factor tree for any integer to solve discrete mathematics and cryptography exercises.
- Calculate Greatest Common Divisor (GCD) and LCM: Compare prime factor sets between two numbers to rapidly determine their GCD and least common multiple.
- Demonstrate RSA public-key mechanics: Illustrate how large semiprime modulus values factor into secret prime components, reinforcing RSA trapdoor function principles.
- Validate factorization algorithms in unit tests: Generate verified prime decompositions to test custom integer factorization algorithms and prime sieve implementations.
Absolute Privacy & Native BigInt Execution
Zero server upload architecture. OmniTools performs all prime factorization, Pollard's ρ polynomial cycles, divisor combinatorial generation, and Extended Euclidean matrix transformations 100% locally inside your web browser engine.
Standard JavaScript Number values use IEEE-754 double-precision floating-point formats, losing integer precision beyond 253 − 1 (9,007,199,254,740,991). OmniTools executes all number-theoretic routines using modern nativeBigInt arbitrary-precision integer representations.
Your entered values, cryptographic seeds, and factoring results never leave your local machine, ensuring complete mathematical confidentiality for researchers, engineers, and competitive programmers.
Frequently Asked Questions
How do I find the prime factorization and all divisors of a number?
Enter any integer (up to 25 digits using native BigInt precision) to decompose it into canonical prime powers (p₁^a₁ × p₂^a₂ × …), list all positive divisors, and compute divisor count d(n), divisor sum σ(n), and Euler’s totient φ(n).
How do you calculate GCD, LCM, and Bézout coefficients for two integers?
Switch to the GCD, LCM & Bézout Identity tab and enter integers A and B. OmniTools runs the Extended Euclidean Algorithm step-by-step to solve A·x + B·y = gcd(A, B), Least Common Multiple (LCM), and modular multiplicative inverses.
How is the total number of divisors d(n) calculated from prime factors?
By the Fundamental Theorem of Arithmetic, if n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ, the total number of positive divisors is d(n) = (a₁ + 1)(a₂ + 1)…(aₖ + 1). For example, 360 = 2³ × 3² × 5¹ has (3+1)(2+1)(1+1) = 24 divisors.