Свойства

Числа a и b взаимно просты тогда и только тогда, когда их наибольший общий делитель равен единице, или, иными словами, если существуют целые x и y такие, что (см. соотношение Безу).

Любые два простых числа взаимно просты.

Если a — делитель bc, и a взаимно просто с b, то a — делитель c.

Если числа a1,…, an — попарно взаимно простые числа, то НОК(a1,…, an) = |a1·…·an|.

Простые числа не имеют других делителей, кроме единицы и самого себя. Если p простое число, то его можно представить в виде произведения двух натуральных чисел только следующим образом: p = p*1. Числа, не являющиеся простыми, называются составными. Понятно, что всякое составное число имеет не меньше двух делителей отличных от 1. Кроме того, любое составное число N можно представить в виде следующего произведения:

N = p1q1 * p2q2 * … * pmqm, где pi – простые числа, m ≥ 1, qi ≥ 1 (при m = 1 q1 > 1, при qi =1 m > 1).