Чтобы найти и доказать, что два числа являются взаимно простыми, нужно найти их наибольший общий делитель (НОД) и сделать вывод на основании сравнения с единицей. 3

Для этого можно воспользоваться двумя алгоритмами: 4

1. Разложить каждое из чисел на множители и искать общие простые множители. 4 Если такие есть, то числа не являются взаимно простыми. 4 Если общих множителей нет, числа можно считать взаимно простыми. 4
2. Делить каждое из чисел поочерёдно на простые множители. 4 Этот способ проще в исполнении, но не подойдёт для больших чисел, так как проверка может получиться слишком долгой. 4

Относительно друг друга два простых числа всегда будут взаимно простыми. 4 А если одно из чисел делится на другое нацело, то эти числа точно не являются взаимно простыми. 4