Podstawowe twierdzenie arytmetyki:

Każda liczba całkowita n > 2 może być przedstawiona jako iloczyn dodatnich całkowitych potęg liczb pierwszych:

gdzie Pi są różnymi liczbami pierwszymi. Ponadto takie przedstawienie (faktoryzacja) jest jedyne (oprócz możliwości zmiany kolejności czynników).

Jeżeli a =pi" p₂ ... p_k i b = p,^f p₂^p ... p_k^p. gdzie e_t>0 \J)>0. to:

gcd(a, b) _p2mm(e2.f2) __pkmmfek.fk)

km (a, b) = p, p₂ ■“"«...

(funkcja min (x, y) ma wartość równą mniejszej z pary liczb (x, y), zaś funkcja max (x, y) ma wartość równą większej z pary liczb (x, y))

Przykład:

Niech a = 4864 = 2^S 19 i b = 3458 = 2 '7 13 19 .

Wtedy:

gcd(4864, 3458) = 2''7° 13° 19¹ = 38 lcm(4864, 3458) =2 ^S 7^I13^I 19¹ = 442624