Понятия теории чисел

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

Утверждение. Любое натуральное число, отличное от 1, можно представить в виде произведения простых чисел.

Утверждение. Для каждого натурального числа существует единственное разложение на простые множители с точностью до следования сомножителей.

Каноническим разложением натурального числа n называется представление числа в виде

где p ₁, p ₂,…, p _k – попарно различные простые числа, a₁, a₂,…, a_k – натуральные числа.

Утверждение (теорема Евклида). Множество простых чисел бесконечно.

Утверждение. Если натуральное число 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.