Разложим 64 и 75: 64 = 2 · 2 · 2 · 2 · 2 · 2, 75 = 3 · 5 · 5. Общих простых множителей нет, поэтому НОД(64, 75) = 1. Числа, наибольший общий делитель которых равен 1, называют взаимно простыми.
Взаимно простыми могут быть и составные числа, как 64 и 75. Любые два соседних натуральных числа взаимно просты: их общий делитель делил бы и их разность 1.