Prime Factorization Calculator

About This Tool

The Prime Factorization Calculator decomposes any positive integer into its prime factors, displaying them with exponents in a clean, readable format. Beyond the factorization itself, it computes the number of divisors, the sum of all divisors, and Euler's totient function. It also lists every divisor of the number and shows a step-by-step division process. This tool is invaluable for number theory students, competitive programmers, cryptography enthusiasts, and anyone who needs to understand the structure of integers.

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. For example, 360 = 2³ × 3² × 5, and no other combination of primes produces 360. This uniqueness is not trivial to prove and forms the bedrock of number theory. The theorem guarantees that prime factorization is a well-defined operation, which is why it appears as a fundamental tool in mathematics and computer science.

Number of Divisors Formula

If a number n has the prime factorization p1ᵉ₁ × p2ᵉ₂ × ... × pkᵉᵏ, then the total number of positive divisors is (e1+1)(e2+1)...(ek+1). For 360 = 2³ × 3² × 5¹, the number of divisors is (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24. This formula works because each divisor is formed by choosing an exponent from 0 to ei for each prime pi, giving independent choices that multiply together.

Sum of Divisors and Perfect Numbers

The sum of divisors function, denoted σ(n), adds up all positive divisors of n. For 360, this sum is 1170. A number is called perfect if the sum of its proper divisors (all divisors except itself) equals the number. The first few perfect numbers are 6, 28, 496, and 8128. Perfect numbers have fascinated mathematicians since antiquity. Euler proved that every even perfect number has the form 2ᵖ⁻¹(2ᵖ - 1) where 2ᵖ - 1 is a Mersenne prime. Whether any odd perfect numbers exist remains one of the oldest unsolved problems in mathematics.

Euler's Totient Function

Euler's totient function φ(n) counts how many integers from 1 to n are coprime to n (share no common factor other than 1). It is computed as φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk). For 360, φ(360) = 360 × (1/2) × (2/3) × (4/5) = 96. The totient function is central to RSA encryption, where it determines the modular inverse used in the private key. It also appears in Euler's theorem: aᵗᵒᵗᵉⁿᵗ ≡ 1 (mod n) for any a coprime to n.

Applications in Cryptography

Modern cryptography, particularly RSA encryption, relies on the difficulty of factoring large numbers. While factoring small numbers is fast (as this calculator demonstrates), factoring a number with hundreds of digits that is the product of two large primes is computationally infeasible with current technology. This asymmetry between multiplication (easy) and factorization (hard) is the security foundation of RSA. Understanding prime factorization is therefore essential for anyone studying information security, blockchain technology, or secure communications.