Взаимно простые числа
Числа называются взаимно простыми, если они не имеют общих делителей кроме 1. Иными словами, числа a и b взаимно простые, если НОД (a, b) = 1. Можно сказать и так: числа a и b взаимно простые тогда и только тогда, когда дробь 
несократима.
Например, числа 8 и 15 взаимно простые. Числа 9 и 15 не являются взаимно простыми — у них имеется общий делитель 3.
Числа взаимно простые тогда и только тогда, когда их канонические разложения состоят из непересекающихся наборов простых чисел. Например, числа 
и 
являются взаимно простыми.
Свойства взаимно простых чисел
Пусть числа a и b взаимно просты. Тогда справедливы следующие утверждения:
1) Если некоторое число делится на a и b, то оно делится и на их произведение ab.
2) Если an делится на b, то n делится на b. (Вы легко поймёте, почему так получается, если представите себе «непересекающиеся» канонические разложения чисел a и b и вдобавок вспомните, что каноническое разложение делителя служит «частью» канонического разложения делимого числа).
Согласно утверждению 1, например, если некоторое число делится на 8 и на 15, то оно делится на 8 · 15 = 120. То, что числа взаимно простые, — важное условие. Так, 12 делится на 4 и на 6, но не делится на 4 · 6 = 24.
Упражнение
Какие цифры можно вставить вместо звёздочек в записи 35 ∗ 4 ∗, чтобы полученное пятизначное число делилось на 45?
Утверждение 2 обычно работает в ситуациях типа следующей:
Пусть, например, 5n = 9m. Так как 5n делится на 9 и числа 5 и 9 взаимно простые, то n делится на 9. По той же самой причине m делится на 5.