primaarifaktorisoinnin

Primaarifaktorisointi (Finnish for primary factorization) is the representation of a positive integer as a product of powers of prime numbers. The process relies on the Fundamental Theorem of Arithmetic, which states that every integer greater than one can be written uniquely as a product of primes, up to the order of the factors. In primaarifaktorisointi the integer \(n\) is expressed in the form \(n = p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\cdot \dots \cdot p_{k}^{e_{k}}\) where each \(p_{i}\) is a distinct prime and each exponent \(e_{i}\) is a positive integer.

The prime factorization of 60, for instance, is \(2^{2}\cdot 3^{1}\cdot 5^{1}\).

Algorithms for primaarifaktorisointi vary in complexity. Simple trial division tests divisibility by each prime up to \(\sqrt{n}\). For large numbers, advanced methods such as Pollard’s Rho algorithm, the quadratic sieve, or the general number field sieve are employed. Even with these, factoring a product of two large primes remains computationally hard, which underpins the security of public‑key cryptographic systems like RSA.

The exponents in a prime factorization reveal properties of the integer: the sum of the exponents indicates the total number of prime factors counted with multiplicity, while the number of distinct primes \(k\) signals the numeric's square‑free nature if all exponents equal one.

Primaarifaktorisointi is also a fundamental tool in number theory for defining functions such as the divisor function, the Möbius function, and the totient function. In algebra, a related concept is the primary decomposition of modules, where modules over a principal ideal domain are written as direct sums of primary submodules. This decomposition parallels the prime factorization of integers and facilitates structural analysis of algebraic objects.