Prime factorization

Prime factorization expresses an integer greater than 1 as a product of prime numbers. By the fundamental theorem of arithmetic, this product is unique apart from the order of its factors.

Fundamental theorem of arithmetic: Every integer greater than 1 has a unique prime factorization, apart from the order of its factors. It guarantees that prime factorization gives one definitive set of factors.
Divisibility: The property of one integer being an exact multiple of another. A prime factorization makes an integer's divisors easy to characterize.
Prime number: A natural number greater than 1 with exactly two positive divisors: 1 and itself. Prime numbers are the indivisible factors used in the decomposition.
Factor tree: A branching diagram that repeatedly splits a composite integer into factors. A factor tree shows a route to the primes, while the final prime factorization is independent of the route.
Trial division: A primality-testing method that checks divisibility by successive candidate factors. Repeated trial division finds factors until only primes remain.
Rational number: A number expressible as a ratio of two integers with a nonzero denominator. Prime factors determine whether a fraction reduces and which primes remain in its denominator.
Composite number: A positive integer greater than 1 that has a divisor other than 1 and itself. Composite integers can be split into smaller factors before reaching primes.
Euclidean algorithm: A repeated-division algorithm for finding the greatest common divisor of two integers. It finds common divisors efficiently without requiring full prime factorizations.
Sieve of Eratosthenes: An algorithm that finds all primes up to a chosen limit by crossing out multiples. A precomputed list of primes speeds factorization by trial division.
Perfect power: An integer that equals another integer raised to an integer exponent greater than one. An integer is a perfect power when its prime exponents share a common divisor greater than one.

Linked from 40 pages