Натуральное число называется простым, если оно не имеет делителей, кроме себя и 1. Натуральное число называется составным, если оно имеет, по крайней мере, два делителя, больших 1.
Утверждение. Любое натуральное число, отличное от 1, можно представить в виде произведения простых чисел.
Утверждение. Для каждого натурального числа существует единственное разложение на простые множители с точностью до следования сомножителей.
Каноническим разложением натурального числа n называется представление числа в виде
где p 1, p 2,…, p k – попарно различные простые числа, a1, a2,…, ak – натуральные числа.
Утверждение (теорема Евклида). Множество простых чисел бесконечно.
Утверждение. Если натуральное число n – составное, то оно имеет хотя бы один делитель, больший 1 и не превосходящий .
Обозначим через НОД(a, b) наибольший общий делитель двух чисел a и b.
Если два числа a и b не имеют общих делителей, они называются взаимно простыми, т.е. НОД(a, b) = 1 или (a, b) = 1.
Обозначим через НОК(a, b) наименьшее общее кратное двух чисел a и b. Для любых двух натуральных чисел a и b наименьшее общее кратное определяется формулой
НОК(a, b) = a b / НОД(a, b).
Если два числа a и b взаимно просты, то НОК(a, b) = a b.