Prime Factorization, HCF & LCM Calculator

Prime Factorization Guide

What should I know about Prime Factorization?

Every integer greater than 1 is either prime or can be written as a unique product of primes (Fundamental Theorem of Arithmetic). Method: divide by smallest prime (2) repeatedly, then 3, then 5, etc. 360 ÷ 2 = 180. 180 ÷ 2 = 90. 90 ÷ 2 = 45. 45 ÷ 3 = 15. 15 ÷ 3 = 5. 5 is prime. 360 = 2³ × 3² × 5. Index notation: use powers. 2³ × 3² × 5¹ = 8 × 9 × 5 = 360. Prime numbers have no factors other than 1 and themselves: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...

What do I need to know about HCF — Highest Common Factor?

HCF = the largest number that divides exactly into all given numbers. Method using prime factors: list prime factors of each number. HCF = product of COMMON prime factors (lowest power). 360 = 2³ × 3² × 5. 84 = 2² × 3 × 7. Common factors: 2² (min of 3 and 2) × 3¹ (min of 2 and 1) = 4 × 3 = 12. HCF(360, 84) = 12. Alternative: Euclidean algorithm. Divide larger by smaller, take remainder, repeat. 360 = 4×84 + 24. 84 = 3×24 + 12. 24 = 2×12 + 0. HCF = 12 (last non-zero remainder). Applications: simplifying fractions to their lowest terms by dividing both numerator and denominator by their HCF.

What should I know about LCM — Lowest Common Multiple?

LCM = smallest number divisible by all given numbers. Method using prime factors: list prime factors. LCM = product of ALL prime factors at their HIGHEST power. 360 = 2³ × 3² × 5. 84 = 2² × 3 × 7. LCM = 2³ × 3² × 5 × 7 = 8 × 9 × 5 × 7 = 2,520. Key relationship: HCF × LCM = product of the two numbers. 12 × 2520 = 30,240 = 360 × 84 ✓. Applications: finding the lowest common denominator when adding fractions. Scheduling problems (two events that repeat every n and m days — when next coincide?). In music theory, LCM is used to work out when rhythmic patterns of different lengths will align back to their starting point together.

What do I need to know about Applications of HCF and LCM?

HCF applications: tiling — what is the largest square tile that fits exactly in a 360cm × 84cm room? HCF(360,84) = 12cm tiles. Simplifying fractions: 84/360 = (84÷12)/(360÷12) = 7/30. Sharing: split 360 items and 84 items into equal groups as large as possible = 12 groups of 30 and 7. LCM applications: when will two buses (one every 15 mins, one every 35 mins) next leave together? LCM(15,35) = 105 minutes. Adding fractions: 1/9 + 1/6 = LCM(9,6) = 18. Denominator = 18. 2/18 + 3/18 = 5/18. Cyclic events — anything that repeats on a fixed schedule, from bus timetables to planetary alignments — rely on LCM to determine when multiple cycles will next coincide.

What should I know about the Fundamental Theorem of Arithmetic?

The Fundamental Theorem of Arithmetic states that every integer greater than 1 is either prime or can be written as a product of primes in exactly one way, apart from the order the factors are written in. For example, 60 can only ever be broken down into 2 × 2 × 3 × 5 — no other combination of primes multiplies to 60. This uniqueness is what makes prime factorization a reliable foundation for other calculations: because there's only one correct factorization, HCF and LCM computed from it are guaranteed consistent, and it's also why 1 is deliberately excluded from the definition of "prime" — if 1 counted as prime, factorizations would no longer be unique, since you could always multiply by extra 1s.

What do I need to know about Using Factor Trees and Division Method?

A factor tree finds a number's prime factorization by repeatedly splitting it into any two factors until every branch ends in a prime. For 84, you might split it as 84 = 4 × 21, then 4 = 2 × 2 and 21 = 3 × 7, giving 84 = 2² × 3 × 7. The division method does the same job more systematically: divide the number by the smallest prime that fits (checking 2, then 3, then 5, and so on), write down that prime, and repeat on the quotient until you reach 1. Both methods always arrive at the same prime factorization regardless of which factors you pick first, which is a direct consequence of the Fundamental Theorem of Arithmetic — there genuinely is only one answer to find.

What should I know about Prime Factorization and RSA Encryption?

Prime factorization, the process of breaking a number into its prime building blocks, is computationally easy for small numbers but becomes extraordinarily difficult for very large numbers with no small factors — and this asymmetry between easy multiplication and hard factorization is the mathematical foundation of RSA encryption, one of the most widely used methods for securing digital communication. RSA works by choosing two large prime numbers, p and q (each hundreds of digits long), and multiplying them to produce a composite number n = p × q, which is made public as part of the encryption key. Multiplying p and q together is computationally trivial even for enormous primes, but reversing the process — factoring the public n back into its two prime factors — is believed to require an impractical amount of computing time using any currently known algorithm, as the number of digits grows large enough. Decrypting an RSA-encrypted message requires knowing p and q individually, not just their product n, so anyone who could efficiently factor very large numbers could break RSA encryption; this is precisely why ongoing research into faster factorization algorithms, and the eventual threat posed by quantum computers (which can factor large numbers efficiently using Shor's algorithm), is closely watched in cryptography and cybersecurity.

Worked Example: Finding HCF and LCM from Prime Factors

Find the HCF and LCM of 84 and 180 using prime factorization. 84 = 2² × 3 × 7 180 = 2² × 3² × 5 For the HCF, take the lowest power of each prime that appears in both factorizations: 2² (lowest power of 2 shared, since both have at least 2²) × 3¹ (lowest shared power of 3, since 84 only has 3¹) = 4 × 3 = 12. For the LCM, take the highest power of every prime that appears in either number: 2² × 3² × 5 × 7 = 4 × 9 × 5 × 7 = 1,260. You can check this with the identity HCF × LCM = the product of the two numbers: 12 × 1,260 = 15,120, and 84 × 180 = 15,120 — they match, confirming the working.

Worked Example: Prime Factorization by Division Ladder

Factorize 2,310 using the division-ladder method: divide repeatedly by the smallest prime that fits. 2310 / 2 = 1155 (2310 is even). 1155 is odd, so skip 2; 1155 / 3 = 385 (digit sum 1+1+5+5=12 is divisible by 3). 385 / 5 = 77 (ends in 5). 77 / 7 = 11. 11 is itself prime, so the ladder stops. Reading off the divisors used: 2310 = 2 × 3 × 5 × 7 × 11. As a check, multiply back: 2×3=6, 6×5=30, 30×7=210, 210×11=2310, confirming the factorization. Interestingly, 2310 is the product of the first five prime numbers, making it the smallest number with exactly five distinct prime factors -- these 'primorial' numbers come up in number theory when studying gaps between primes.

Why Factorization Gets Hard: Trial Division vs. Modern Algorithms

For small numbers, trial division (checking each prime up to the square root of the number) is fast enough to do by hand or with a basic calculator. But the time trial division takes grows roughly with the square root of the number being factored, so it becomes impractical for very large numbers -- factoring a 300-digit number by trial division would take longer than the age of the universe on any computer. This is precisely the gap that RSA encryption relies on: multiplying two large primes together is fast, but factoring the product back into those primes is computationally infeasible without a quantum computer or a fundamentally better classical algorithm. Modern factorization research uses methods like the quadratic sieve and the general number field sieve, which are dramatically faster than trial division for large numbers but still far slower than multiplication -- an asymmetry that underpins the security of most of today's internet encryption.