Loading calculator...
Loading calculator...
Factor any number into its prime factors and find GCD and LCM of two numbers with step-by-step working.
Prime Factorization:
Every integer > 1 is either prime or a product of primes (Fundamental Theorem of Arithmetic)
GCD and LCM:
GCD: Euclidean algorithm (repeated division)
LCM(a, b) = (a × b) / GCD(a, b)
Prime factorization expresses a number as a product of prime numbers. For example, 360 = 2³ × 3² × 5. This representation is unique for every integer greater than 1 (Fundamental Theorem of Arithmetic).
A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself. Examples: 2, 3, 5, 7, 11, 13. The number 1 is not prime by convention.
Repeatedly apply: GCD(a, b) = GCD(b, a mod b) until b = 0. Then a is the GCD. For example: GCD(48, 18) → GCD(18, 12) → GCD(12, 6) → GCD(6, 0) = 6.
For two positive integers: GCD(a,b) × LCM(a,b) = a × b. This means LCM(a,b) = (a × b) / GCD(a,b). It is faster to compute LCM this way than by listing multiples.
Prime factorization is used in cryptography (RSA encryption relies on the difficulty of factoring large numbers), simplifying fractions, finding GCD/LCM, and solving Diophantine equations.