Давайте подумаем, в каких границах может находиться НОД двух чисел.

Первое свойство.

У любых двух чисел есть хотя бы один общий делитель, и это число 1.

И здесь мы введем понятие взаимно простых чисел.

Два числа называются взаимно простыми, если их наибольший общий делитель равен единице.

Что это значит? Это значит, что на самом деле у них нет других общих делителей, кроме единицы. Какие примеры взаимно простых чисел мы можем привести?

Например, числа 2 и 3, которые мы рассматривали выше. Числа 3 и 7 также взаимно простые.

Очень важно не путать понятия взаимно простых чисел, и простых чисел.

Из того что числа взаимно простые еще не следует, что они простые.

Например, . Тем не менее ни 9, ни 10 не являются простыми числами, но они взаимно простые.

Второе свойство.

Как вы думаете, если даны два числа и , причем нацело делится на (), чему тогда равен ?

– такое наибольшее число, на которое делятся и , и . Логично, что наибольшее число, на которое делится – , а – по условию.

Значит, .

Например, ;

Аналогично ;

, потому что и больше 1 результат быть не может.

Теперь давайте найдем удобный способ нахождения НОД.