Определение. Числа а и b взаимно просты, если НОД (а, b)=1.

Справедливы следующие свойства:

1⁰. Если некоторое число делится на а и b, то оно делится и на их произведение a· b.

2⁰. Если a· n делится на b, то n делится на b.

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

Определение. Целые числа a1,a2,...,ak , каждое из которых взаимно просто со всеми остальными, называют попарно простыми числами.

Так простым примером являются числа 14, 9, 17 и -25 – попарно простые, потому что пары чисел 14 и 9, 14 и 17, 14 и -25, 9 и 17, 9 и -25, 17 и -25 представляют собой взаимно простые числа.

Взаимно простые числа не всегда являются попарно простыми. Так 71, 443, 857, 991 - числа всегда являющиеся и взаимно простыми, и попарно простыми. Стоит отметить, когда речь идет о двух целых числах, то для них понятия «попарно простые» и «взаимно простые» совпадают.