Основная теорема арифметики

Каждое натуральное число $n$ представляется в виде $n=p_{1}\cdot \dots \cdot p_{k}$, где $p_{1},\dots ,p_{k}$ суть простые числа. Причем данное представление единственно с точностью до порядка сомножителей.

Как следствие, каждое натуральное число $n$ единственным образом представимо в виде $n=p_{1}^{d_{1}}\cdot \dots \cdot p_{m}^{d_{m}}$, где $p_{1}<\dots <p_{k}$ - простые числа, и $d_{1},\dots ,d_{m}$ - некоторые натульные числа.

Заметим, что подобное представление дает элегантный способ выражения наибольшего общего делителя и наименьшего общего кратного двух чисел. Если $n=p_{1}^{d_{1}}\cdot \dots \cdot p_{m}^{d_{m}}$ и $m=p_{1}^{e_{1}}\cdot \dots \cdot p_{m}^{e_{m}}$, где $p_{1},\dots ,p_{k}$ - различные простые числа, а показатели $d_{1},\dots ,d_{m},e_{1},\dots ,e_{m}$ неотрицательные целые числа, то

$HOD(n,m)=p_{1}^{min(d_{1},e_{1})}\cdot \dots \cdot p_{m}^{min(d_{m},e_{m})}$

$HOK(n,m)=p_{1}^{max(d_{1},e_{1})}\cdot \dots \cdot p_{m}^{max(d_{m},e_{m})}$.

Основную теорему арифметики можно легко распространить также на отрицательные числа, введя в разложение сомножитель равный $-1$.