Некоторые свойства наибольшего общего делителя и наименьшего общего кратного

Теорема 1 (О связи НОД и НОК). НОД (а, в) · НОК (а, в) = а · в.

Доказательство.

Пусть и , тогда , используя ассоциативность и коммутативность умножения, перегруппируем множители следующим образом: а × в = , где d _i ≤ t_i, i = 1, 2, …, к.

Т.е. поступили мы так: выбрали и и сравнили a_iи b _i. Если a _i ≥ b _i, то во 2-ой скобке, а – в 1-ой скобке. Но ведь тогда

т.е. а · в =НОД(а, в)·НОК(а, в).

П р и м е р.

Запишем равенство 12 ·240 = 60 · 48, получим 2880 = 2880.

Теорема 2 (облегчающая вычисление НОД и НОК).

1) НОД (а ₁, а ₂, … а _n) =НОД (НОД(а ₁, а ₂), а ₃, …, а_n),

2) НОК (а ₁, а ₂, … а _n) =НОК (НОК(а ₁, а ₂), а ₃, …, а_n).

Теорема позволяет при отыскании НОД и НОК нескольких чисел производить это последовательно, заменяя пару чисел их НОД и НОК.

Доказательство. 1) Пусть даны числа а ₁, а ₂, …, а_n своими каноническими разложениями.

… …….. …….

НОД (а ₁, а ₂) = , где t_i – наименьшее из чисел a _i, b _i, i = 1, 2, …, к.

Обозначим через d _i – наименьшее из чисел a _i, b _i, c_i, …, g _i, тогда d _i является наименьшим из чисел t_i, c_i, …, g _i.

НОД , отсюда

НОД(а ₁, а ₂, …, а_n) = НОД (НОД (а ₁, а ₂), а ₃, а ₄, …, а_n).

2) Точно так же доказывается и вторая часть.

НОК , где r _i – наибольшее из чисел a _i, b _i, i = 1, 2, …, к.

НОК , где m_i – наибольшее из чисел a _i, b _i, c_i, …, g _i и является наибольшим из чисел r_i, c_i, …, g _i, отсюда

НОК (а ₁, а ₂, …, а_n) = НОК (НОК (а ₁, а ₂), а ₃, а ₄, …, а_n).

П р и м е р. Применяя теорему 2, найдем НОД (1320, 3600, 1485).

1320 = 2³ · 3¹ · 5 · 11,

3600 = 2⁴ · 3² · 5² ·11⁰,

1485 = 2⁰ · 3³ · 5 · 11.

НОД (1320, 3600) = 2³ · 3 · 5 = 120,

НОД (120, 1485) = 2⁰ · 3 · 5 = 15.

Значит, НОД (1320, 3600, 1485) = 15.

НОК (1320, 3600) = 2⁴ · 3² · 5² · 11 = 39600

НОК (39600, 1485) = 2⁴ · 3³ · 5² · 11 = 118800.

Значит, НОК (1320, 3600, 1485) = 118800.

Теорема 3. Пусть m – некоторое натуральное число, тогда

НОД (ma₁, ma₂, …, ma_n) = m НОД (а ₁, а ₂, …, а_n),

НОК (ma₁, ma₂, …, ma_n) = m НОК (а ₁, а ₂, …, а_n), то есть общий множитель можно выносить за знак НОД и за знак НОК.

Доказательство. Запишем каноническое разложение чисел ,

НОД (а ₁, а ₂, …, а_n) = , НОК (а ₁, а ₂, …, а_n) = . Ясно, что есть наименьший, а – наибольший среди степеней простого числа p_i, встречающихся в канонических разложениях чисел а ₁, а ₂, …, а_n, но тогда будет наименьшим, а – наибольшим среди степеней простого числа p _i в разложениях чисел mа ₁, mа ₂, …, mа_n. p_i – это любое число из простых множителей чисел а ₁, а ₂, …, а_n. Значит, получили m НОД (а ₁, а ₂, …, а_n) = = = НОД (mа ₁, mа ₂, …, mа_n).