НОД - наибольший общий делитель - наибольшее число на которое делятся все данные числа без остатка. В случае если НОД двух чисел равен 1, то такие числа называют взаимно простыми.
Примеры:
6 и 3
НОД (6 и 3) = 3
5 и 3
НОД (5 и 3) = 1
12 и 9
НОД (12 и 9) = 3