Основная теорема арифметики. 
Простые и составные числа. 
Наибольший общий делитель и наименьшее общее кратное

Основнамя теоремма арифмемтики утверждает:

Каждое натуральное число можно представить в виде, где — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

Простоме числом — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. При этом натуральные числа, которые больше единицы и не являются простыми, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные.

Наибольшим общим делителем (НОД) для двух целых чисел и называется наибольший из их общих делителей. 1] Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел или не ноль.

Алгоритм Евклида.

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть Тогда НОД (a, b), наибольший общий делитель и, равен, последнему ненулевому члену этой последовательности.

Наимемньшее омбщее крамтное (НОК, lcm) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка.

Если известен наибольший общий делитель, можно использовать его связь с НОК: