Factor Calculator

How to Use the Factor Calculator

This calculator offers four powerful modes to explore the divisibility and factorization of any positive integer up to 10,000,000,000 (10 billion):

• Mode 1 — All Factors of a Single Number: Enter any positive integer to instantly get a complete sorted list of all its divisors (factors), displayed as a flat list and as factor pairs (n = a × b). The tool also outputs the total count of factors τ(n), the sum of factors σ(n), and classifies the number as prime, perfect, abundant, or deficient.
• Mode 2 — Prime Factorization: Enter a number to see its unique prime factorization n = p1a₁ × p2a₂ × … × pkaₖ using trial division up to √n. The output includes the canonical prime form with exponents, and all derived properties (number of factors, sum, Euler's totient φ(n), prime or composite).
• Mode 3 — GCF/GCD of Two Numbers: Enter two positive integers to find their Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD). The tool uses the Euclidean algorithm for speed, then displays the full prime factorizations of both numbers. Also computes the LCM (Least Common Multiple) via GCF × LCM = n₁ × n₂.
• Mode 4 — LCM of Two Numbers: Find the Least Common Multiple of any two positive integers, with step-by-step prime factorization method and the formula relationship LCM(a,b) = a×b / GCF(a,b).

What Are Factors and How to Find Them

A factor (also called a divisor) of a positive integer n is any positive integer that divides n with remainder zero. In notation: d is a factor of n if n ÷ d = k for some positive integer k, equivalently n mod d = 0.

• Trial Division Method: To find all factors of n, test every integer d from 1 to √n. If d divides n, then both d and n/d are factors. This gives at most 2√n candidate divisions. Example: n = 36. Test d = 1: 36/1 = 36 ✓. d = 2: 36/2 = 18 ✓. d = 3: 36/3 = 12 ✓. d = 4: 36/4 = 9 ✓. d = 5: 36/5 = 7.2 ✗. d = 6: 36/6 = 6 ✓ (stop at √36 = 6). Factors: {1, 2, 3, 4, 6, 9, 12, 18, 36}. Count: 9 factors.
• Factor Pairs: Each factorization d × (n/d) = n is a factor pair. For n = 36: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Note: when n is a perfect square, the middle pair has equal factors (√n × √n).
• Number of Factors Formula (τ function): Given the prime factorization n = p1a₁ × p2a₂ × … × pkaₖ, the number of positive divisors is: τ(n) = (a₁+1)(a₂+1)…(aₖ+1). Example: 360 = 2³ × 3² × 5¹. τ(360) = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24. Each divisor independently chooses 0, 1, …, a₁ copies of p1, giving (a₁+1) choices per prime. A highly composite number has more divisors than any smaller positive integer.
• Sum of Factors Formula (σ function): The sum of all positive divisors is σ(n) = [(p1a₁+1−1)/(p1−1)] × [(p2a₂+1−1)/(p2−1)] × … This is a multiplicative arithmetic function. Example: σ(12) = σ(2² × 3) = (1+2+4)(1+3) = 7 × 4 = 28. Verify: 1+2+3+4+6+12 = 28 ✓. For a prime power pa: σ(pa) = 1 + p + p² + … + pa = (pa+1−1)/(p−1).

Prime Factorization: The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every positive integer greater than 1 has a unique prime factorization (up to ordering of factors). This is the basis of all number theory and cryptography.

• Trial Division Algorithm: To factorize n, divide by the smallest prime 2 as many times as possible, then 3, 5, 7, 11, 13, … (only test primes up to √n). If no prime ≤ √n divides n, then n itself is prime. Example: n = 360. 360 ÷ 2 = 180 ÷ 2 = 90 ÷ 2 = 45 (three 2s). 45 ÷ 3 = 15 ÷ 3 = 5 (two 3s). 5 is prime. Result: 360 = 2³ × 3² × 5. Time complexity: O(√n) worst case.
• Reading Prime Factorizations: The form n = 2a × 3b × 5c × 7d × … is the canonical (standard) representation. Examples: 1024 = 210, 2048 = 211, 6 = 2¹ × 3¹ (first perfect number), 360 = 2³ × 3² × 5 (highly composite, 24 divisors), 720 = 24 × 3² × 5 (smallest with 30 divisors), 5040 = 24 × 3² × 5 × 7 (τ(5040) = 60).
• Euler's Totient Function φ(n): Counts integers from 1 to n that are coprime to n. Formula: φ(n) = n × ∏(1 − 1/p) for each prime p dividing n. Example: φ(12) = 12 × (1 − ½) × (1 − ⅓) = 4. The numbers coprime to 12 in {1…12}: {1, 5, 7, 11}. φ(p) = p − 1 for any prime p. The totient is crucial in RSA encryption: a ciphertext c = me mod n can be decrypted because mφ(n) ≡ 1 (mod n) by Euler's theorem.
• Radical of n — rad(n): Product of distinct prime factors of n. rad(360) = 2 × 3 × 5 = 30. The ABC conjecture concerns rad(a × b × c) when a + b = c.
• Powerful numbers: n is powerful if every prime factor appears with exponent ≥ 2. Examples: 4 = 2², 8 = 2³, 9 = 3², 36 = 2² × 3², 72 = 2³ × 3². These relate to perfect squares and perfect cubes.

GCF and LCM: Applications and Methods

• Euclidean Algorithm for GCF: The most efficient method. GCF(a, b) = GCF(b, a mod b), with base case GCF(a, 0) = a. Example: GCF(48, 36): GCF(48, 36) → GCF(36, 12) → GCF(12, 0) = 12. This is O(log(min(a, b))) steps. By Lamé's theorem, the number of steps never exceeds 5 × the number of digits in the smaller number.
• Prime Factorization Method for GCF: GCF = product of shared primes with minimum exponents. Example: 360 = 2³ × 3² × 5, 504 = 2³ × 3² × 7. GCF(360, 504) = 2min(3,3) × 3min(2,2) = 2³ × 3² = 8 × 9 = 72. LCM = product of all primes with maximum exponents: LCM = 2³ × 3² × 5¹ × 7¹ = 2520. Verify: 360 × 504 = 181,440 = 72 × 2520 ✓.
• GCF × LCM = a × b: This fundamental identity holds for any two positive integers. It follows from prime factorization: each prime p contributes pmin+max = pexp_a + exp_b per prime, giving a × b overall. Therefore GCF × LCM = a × b always.
• Coprime numbers: Two integers are coprime (relatively prime) if GCF(a, b) = 1. Example: 8 and 9 are coprime because 8 = 2³, 9 = 3², no shared primes. The probability that two random integers are coprime is 6/π² ≈ 60.79% (the Basel problem result, connecting factor theory to the Riemann zeta function: ζ(2) = π²/6).
• Applications of GCF: (1) Simplifying fractions: 24/36 = 2/3, since GCF(24, 36) = 12. (2) Tiling: A 6 × 4 m floor can be tiled with the largest square tiles of side GCF(6, 4) = 2 m. (3) Rhythm: Two patterns of period 8 and 12 beats sync every LCM(8, 12) = 24 beats. (4) Gear ratios: Gears with 24 and 36 teeth repeat every LCM/24 = 3 turns of gear 1.

Number Classification: Prime, Perfect, Abundant, Deficient

• Prime Numbers: n is prime if it has exactly two factors: 1 and itself (τ(n) = 2). The first primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. The prime number theorem: π(x) ~ x/ln(x). There are infinitely many primes (Euclid's proof). Our Exponent Calculator can help compute values like 2p−1 when checking Mersenne prime candidates.
• Composite Numbers: n > 1 with τ(n) > 2. The smallest composite: 4. The number 1 is neither prime nor composite. Semiprimes (products of exactly two primes): 4, 6, 9, 10, 14, 15, 21, 22, 25, … RSA encryption depends on the difficulty of factoring large semiprimes.
• Perfect Numbers: n is perfect if σ(n) = 2n (the proper divisors sum to n). Known perfect numbers: 6, 28, 496, 8128, 33,550,336. For 6: 1+2+3 = 6 ✓. For 28: 1+2+4+7+14 = 28 ✓. Euler proved every even perfect number has the form 2p−1(2p−1) where 2p−1 is a Mersenne prime. Whether odd perfect numbers exist is an open problem.
• Abundant Numbers: σ(n) − n > n (proper divisors sum exceeds n). First abundant: 12 (1+2+3+4+6 = 16 > 12). All multiples of an abundant number are abundant. Approximately 24.76% of positive integers are abundant.
• Deficient Numbers: σ(n) − n < n. All primes are deficient. Powers of 2 are deficient: σ(2k) − 2k = (2k+1−1) − 2k = 2k−1 < 2k. Approximately 75.24% of integers are deficient.
• Highly Composite Numbers: Numbers with more divisors than any smaller positive integer: 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040. Used as time units (60 s, 60 min, 24 h, 360°) because their many factors make division convenient. τ(360) = 24, τ(720) = 30, τ(5040) = 60.

Divisibility Rules and Quick Factoring Shortcuts

• Divisibility by 2: Last digit is even (0, 2, 4, 6, 8). Example: 4,386 ends in 6 — divisible by 2.
• Divisibility by 3: Sum of digits divisible by 3. Example: 4386: 4+3+8+6 = 21, 21/3 = 7 ✓. So 4386 = 3 × 1462.
• Divisibility by 4: Last two digits form a number divisible by 4. Example: 4,816 — last two digits 16, 16/4 = 4 ✓.
• Divisibility by 5: Last digit is 0 or 5. Example: 1,235 ends in 5 ✓.
• Divisibility by 6: Divisible by both 2 and 3 (last digit even AND digit sum divisible by 3).
• Divisibility by 7: Double the last digit and subtract from the remaining digits. Repeat. Example: 343 → 34 − 3×2 = 28, 28/7 = 4 ✓.
• Divisibility by 8: Last three digits divisible by 8. Example: 1,024 — last 3 digits 024 = 24, 24/8 = 3 ✓.
• Divisibility by 9: Sum of digits divisible by 9. Example: 729: 7+2+9 = 18 ✓.
• Divisibility by 11: Alternating digit sum divisible by 11. Example: 1,584: 1−5+8−4 = 0 ✓.
• Perfect Squares shortcut: If τ(n) is odd, n is a perfect square. Example: τ(36) = 9 (odd) → 36 = 6² ✓. The square root factor √n pairs with itself, giving an odd total count.

Real-World Applications of Factoring

• RSA Cryptography: Public key encryption depends on the difficulty of factoring large semiprimes. A 2048-bit RSA key is the product of two ~309-digit primes. Our Exponent Calculator handles the modular exponentiation used in RSA: c = me mod n (encryption), where decryption uses d = e⁻¹ mod φ(n) because mφ(n) ≡ 1 (mod n) by Euler's theorem.
• Fraction Simplification: To simplify 252/360: GCF(252, 360) = 36. Result: 7/10. Prime factorizations: 252 = 2² × 3² × 7, 360 = 2³ × 3² × 5. GCF = 2² × 3² = 36. See also: Remainder Calculator for modular arithmetic.
• Music Theory: Musical intervals are frequency ratios. A perfect fifth is 3:2. The equal temperament system divides the octave into 12 equal semitones because 12 = 2² × 3, which has many divisors (6 divisors), giving clean approximate integer ratios.
• Computer Science — Hash Tables: Hash table sizes are chosen as primes to minimize collisions in modular hashing: h(k) = k mod tableSize. Common prime sizes: 251, 509, 1021, 2053, 4093, 8191 (near powers of 2). The Exponent Calculator helps verify 2k−1 Mersenne prime candidates for hash table sizing.
• Scheduling and Calendars: LCM finds when periodic events coincide. Traffic lights of cycles 80 s and 120 s sync every LCM(80, 120) = 240 s. The Mayan Calendar Round: 260-day tzolkʼin and 365-day haab cycle together repeat every LCM(260, 365) = 18,980 days = 52 years.
• Division of Resources: To divide 48 apples and 36 oranges into maximum equal shares: GCF(48, 36) = 12 shares, each with 4 apples and 3 oranges. Generally, share n₁ items and n₂ items equally using GCF(n₁, n₂).

Related Calculators

• Exponent Calculator — When n = pa, the factors are exactly 1, p, p², …, pa: a total of a+1 factors. The sum σ(pa) = 1 + p + … + pa = (pa+1−1)/(p−1) is a geometric series. Mersenne primes (of the form 2p−1) are found by computing 2p−1 then primality-testing. RSA uses modular exponentiation me mod n, where n is a semiprime whose factorization determines the encryption's security.
• Remainder Calculator — The factor d divides n if and only if n mod d = 0. Fermat's little theorem: ap−1 ≡ 1 (mod p) for any prime p not dividing a — the foundation of the Miller–Rabin primality test. The Chinese Remainder Theorem reconstructs a number from its remainders modulo pairwise coprime moduli.
• Triangle Area Calculator — All primitive Pythagorean triples (a, b, c with a² + b² = c²) are generated by (m²−n², 2mn, m²+n²) where m > n > 0 and gcd(m, n) = 1. Finding triples for a given hypotenuse c requires factoring c. So triangle geometry and number factoring are intertwined whenever working with integer right triangles.
• Average Calculator — The arithmetic mean of all divisors of n is σ(n)/τ(n). The geometric mean of all divisors is always exactly √n (because factors pair as d and n/d with product n). The arithmetic, geometric, and harmonic means of divisors all have closed forms involving σ(n) and τ(n).
• Pythagorean Theorem Calculator — Every primitive triple is (m²−n², 2mn, m²+n²) with m, n coprime and not both odd. A prime p appears as a primitive hypotenuse if and only if p ≡ 1 (mod 4). So 5 (5 ≡ 1 mod 4) is the hypotenuse of (3, 4, 5), but 7 (7 ≡ 3 mod 4) never is. The Factor Calculator determines which primes divide a number and their congruence class mod 4.