> [!NOTE] Definiton (Prime factorisation) > The prime factorisation of a [[Natural Numbers|natural number]] is the product of [[Prime numbers|primes]] that equals the given number. # Properties **Uniqueness**: The [[Fundamental theorem of arithmetic|FTA]] asserts that every natural number can be expressed uniquely as a product of primes. **Algorithms:** The problem of finding the [[Prime Factorisation|prime factorisation]] of a natural is a computational problem. See [[PPF Algorithm]]. # Applications Finding the [[Number of Divisors of a Natural Number|number of divisors]] of a natural number: If $n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\dots p_{s}^{\alpha_{s}}$ then $n$ has $(\alpha_{1}+\alpha_{2}+\dots+\alpha_{s})$ divisors. Finding the [[Greatest Common Divisor (GCD)|GCD]] and [[Lowest Common Multiple (LCM)|LCM]] of two natural numbers: If $a=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\dots p_{k}^{\alpha_{k}}$ and $b=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}\dots p_{k}^{\beta_{k}}$ then $\gcd(a,b)=p_{1}^{\min(\alpha_{1},b_{1})} p_{2}^{\min(\alpha_{2},\beta_{2})}\dots p_{k}^\min(\alpha_{k},\beta_{k})$ and $\text{lcm}(a,b)=p_{1}^{\max(\alpha_{1},b_{1})} p_{2}^{\max(\alpha_{2},\beta_{2})}\dots p_{k}^\max(\alpha_{k},\beta_{k}).$