Каноническое разложение

Каноническое разложение натурального числа — это представление числа как произведения простых множителей, записанное в стандартном виде, где простые числа идут в порядке возрастания, а перед каждым простым стоит натуральная степень. Согласно основной теореме арифметики, любое целое число больше единицы имеет такое разложение и оно единственно с точностью до порядка сомножителей. Формально это можно записать так: $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k},\quad p_1<p_2<\dots<p_k$. Такое представление называют также факторизацией по простым множителям или канонической формой числа.

Каноническое разложение широко используется в задачах на делимость и в вычислительной математике. По разложениям легко находить наибольший общий делитель и наименьшее общее кратное двух чисел: если два числа представлены через одни и те же простые основания с показателями степеней, то НОД получается взятием минимальных показателей степени, а НОК — максимальных. Это выражается формулами $\gcd(a,b)=\prod_{i=1}^k p_i^{\min(\alpha_i,\beta_i)}$ и $\operatorname{lcm}(a,b)=\prod_{i=1}^k p_i^{\max(\alpha_i,\beta_i)}$. По каноническому разложению также легко вычислять количество делителей числа и его арифметические функции; например, функция числа делителей даётся формулой $\tau(n)=\prod_{i=1}^k (\alpha_i+1)$, а функция Эйлера выражается как $\varphi(n)=n\prod_{i=1}^k\left(1-\dfrac{1}{p_i}\right)$. Практически это даёт быстрые алгоритмы для проверки простоты, разложения на множители и решения задач, связанных с делимостью и остатками.