Пусть даны натуральные числа: \(n_1,n_2,...,n_k\). Если каждое из этих чисел делится на натуральное число a, то его называют общим делителем этих чисел.
 Наибольший из общих делителей чисел \(n_1,n_2,...,n_k\) называется их наибольшим делителем и обозначается НОД \((n_1,n_2,...,n_k)\).
 Если числа не имеют общих делителей кроме единицы, то они называются взаимно простыми. Например, числа 7 и 5 – взаимно простые.
 Схема отыскания НОД:

1. разложить каждое из чисел на простые множители;
2. составить произведение из всех общих простых множителей.

Пример 1. Найдите НОД чисел 190 и 360.

1. Находим разложения чисел на простые множители:

Следовательно, \(190=2\cdot 5 \cdot 19 \cdot 1,\) \(360=2^3\cdot 3^2 \cdot 5 \cdot 1.\)

2. Составляем произведение из всех общих простых множителей, получаем НОД(190, 360) = 2·5 = 10.

Наибольший общий делитель чисел n и m можно находить, используя алгоритм Евклида.
 Пусть для определенности n > m, тогда при делении n на m с остатком имеем:

\(n=mk+r,0<r<m.\)

 По свойству делимости суммы все общие делители чисел n и m являются и делителями числа r. Тогда и все общие делители чисел n и m являются общими делителями чисел n и r , в том числе и их наибольшие общие делители, т.е. НОД(n, m) = НОД(m, r), поскольку r < m, то находить НОД(m, r) проще чем НОД(n, m). Если НОД(m, m) не найден, то процесс продолжается далее, т.е. выполняется деление чисел m и r с остатком и т.д.

\(m=rk_1+r_1,0<r_1<r;r=r_1k_2+r_2,0<r_2<r_1;\)

\(r_1=r_2k_2+r_3,0<r_3<r_2;...r_{n-2}=r_{n-1}k_{n-1}+r_n,\)

\(0<r_n<r_{n-1};r_{n-1}=r_nk_n.\)

Алгоритм заканчивается при получении нулевого остатка. Тогда НОД(n, m)=\(НОД(r_{n-1},r_n)=r_n.\)

Пример 2. Сократите дробь \(\frac{1547}{2873}.\).
Решение. Для сокращения дроби потребуется найти НОД(1547, 2873). Применим алгоритм Евклида.

 2873 = 1547 · 1 + 1326;
 1547 = 1326 · 1 + 221;
 1326 = 221 · 6 + 0.

Имеем НОД(2873, 1547) = НОД(1547, 1326) = НОД(1326, 221) = 221.
Следовательно, дробь сократима на 221, т.е. \(\frac{1547}{2873}=\frac{7}{13}.\)

Если число b кратно числам \(m_1,m_2,...,m_k,\) то есть делится на каждое из них нацело, то оно называется общим кратным этих чисел. Наименьшим общим кратным чисел \(m_1,m_2,...,m_k\) называется наименьшее число, кратное всем из указанных чисел, обозначается: \(HOK(​m_1,m_2,...,m_k).\).
 Схема отыскания НОК:

1. разложить каждое из чисел на простые множители;
2. составить произведение из всех простых множителей разложения одного числа и недостающих множителей из разложений других чисел;
3. вычислить произведение.

Пример 3. Найдите НОК чисел 360 и 190.

1. Имеем: \(360=2^3 \cdot 3^2 \cdot 5 \cdot 1;\)

\(190=2\cdot 5 \cdot 19 \cdot 1;\)

2. \(HOK(360;190)=2^3 \cdot 3^2 \cdot 5 \cdot 1=6840.\)

!!! Для любых натуральных чисел n и m имеет место равенство:

\(НОК(n,m)\cdot НОД(n,m)=n \cdot m.\)