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