Натуральные числа a и b называют взаимно простыми, если их наибольший общий делитель равен 1 (НОД(a; b) = 1). Другими словами, если числа a и b не имеют никаких общих делителей, кроме 1, то они взаимно просты.

Примеры пар взаимно простых чисел: 2 и 5, 13 и 16, 35 и 88 и т. п. Можно указать несколько взаимно простых чисел, например, числа 7, 9, 16 – взаимно просты.

Часто взаимно простые числа обозначают так: (a, b) = 1. Например, (23, 30) = 1. Эта запись как бы является сокращенной записью обозначения наибольшего общего делителя двух чисел (НОД(23, 30) = 1), и говорит о том, что их наибольший общий делитель равен 1.

Два соседних натуральных числа всегда будут взаимно просты. Например, 15 и 16 — пара взаимно простых чисел, также как 16 и 17. Это легко понять, если принять во внимание «правило» о том, что если два натуральных числа a и b делятся на одно и то же натуральное число большее 1 (n > 1), то и их разница также должна делится на это число n (здесь имеется в виду, что a, b и их разность делятся нацело, т. е. кратны числу n). Но если a и b два соседних числа (пусть a < b), то b – a = 1; но 1 делится только на 1 (из ряда натуральных чисел). Следовательно, a и b не имеют других общих делителей, кроме 1.

Из определения взаимно простых чисел и простых чисел также следует, что разные простые числа всегда оказываются взаимно простыми. Ведь делителями любого простого числа являются лишь оно само и 1.

Свойства взаимно простых чисел

• Наименьшее общее кратное (НОК) пары взаимно простых чисел равно их произведению. Например, (3, 8) = 1 (это значит взаимно просты), следовательно, их НОК равен 3 × 8 = 24 (НОК(3, 8) = 24). Действительно, вы не найдете меньшее число, чем 24, которое было бы кратно и 3 и 8.
• Если числа a и b взаимно просты и число c кратно как a, так и b, то это число будет кратно и произведению ab. Это можно записать так: если с a и c b, то c ab. Например, (3, 10) = 1, число 60 кратно как 3, так и 10, а также кратно 30 (3 × 10).
• Если числа a и b взаимно просты и взято число c кратное b (c b), то произведение ac также будет также кратно b (ac b). Например, (2, 17) = 1, пусть c = 34. Число 34 кратно b = 17, тогда ac = 2 × 34 = 68. Проверяем: 68 ÷ 17 = 4, т. е. делится нацело, а значит 68 кратно 17.

Обычно выделяют больше свойств, чем приведено здесь. Кроме того, свойства взаимно простых чисел формулируются по разному. Также бывает требуется доказать эти свойства (в данном случае доказательства не приводятся).