Prime Factorization & Number Theory

Decompose any integer into prime factors (p₁^a₁ × p₂^a₂), list all positive divisors, and compute GCD, LCM, Euler totient φ(n), and Bézout coefficients.

Input Integer

Presets:

About Number Theory Tools

Computes canonical prime factorization (p₁^a₁ × p₂^a₂...), all positive divisors, divisor count d(n), divisor sum σ(n), and Euler's totient φ(n) using pure client-side BigInt arithmetic.

Classification:COMPOSITE NUMBER
Canonical Prime Factorization:
360 = 2^3 × 3^2 × 5
Divisor Count d(n)
24
Total positive factors
Divisor Sum σ(n)
1170
Sum of all divisors
Euler's Totient φ(n)
96
Integers coprime to n

All Positive Divisors (24)

1234568910121518202430364045607290120180360

Prime Neighborhood

Previous Prime: 359
Next Prime: 367
Prime Gap: 8

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:

FunctionSymbolClosed FormulaExample for 360 (2³ × 3² × 5¹)
Divisor Countd(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:

StepEuclidean DivisionQuotient (q)Remainder (r)
Step 11071 = 2 × 462 + 147q₁ = 2r₁ = 147
Step 2462 = 3 × 147 + 21q₂ = 3r₂ = 21
Step 3147 = 7 × 21 + 0q₃ = 7r₃ = 0 → gcd = 21

Next, backward substitution expresses remainder 21 in terms of initial inputs 1071 and 462:

21 = 462 − 3 × (147)
21 = 462 − 3 × (1071 − 2 × 462)
21 = 1071 × (−3) + 462 × (7)

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.