Элементарная математика. Алгебра.

Алгебра

Глава 1. Натуральные числа

1.6. Наибольший общий делитель и наименьшее общее кратное

Наибольший общий делитель чисел $a_1, a_2, ... , a_n$ обозначают $(a_1, a_2, ... , a_n)$, а наименьшее общее кратное — $[a_1, a_2, ... , a_n]$. В частности, $(a, b)$ — НОД чисел $a$ и $b$, а $[a, b]$ — НОК этих чисел.
Отметим, что

● НОД $(a;b)$ = НОД $(a; a +b)$;

● НОД $(a;b)$ = НОД $(a; a -b)$.

Определение

Числа $a_1, a_2, ... , a_n$ называются взаимно простыми, если $(a_1, a_2, ... , a_n)=1$ и попарно взаимно простыми, если любые два из них взаимно просты, т.е. $(a_i,a_j)=1$ при $i\neq j$.

Попарно взаимно простые числа являются взаимно простыми (в совокупности). Обратное утверждение неверно: числа $n_1=3, n_2=2\cdot 3, n_3= 2\cdot 5, n_4=3\cdot 5$ не являются взаимно простыми, а $(n_1, n_2, n_3, n_4)=1$.

Утверждение

Если целые числа $a$ и $b$ взаимно просты, то их сумма $a + b$ и произведение $ab$ также являются взаимно простыми числами.

Утверждение

Если целые числа $a$ и $b$ являются взаимно простыми, то НОД $(a+b;a-b)$ равен $1$ или $2$.

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

Положим НОД$(a+b;a-b)=d$. Тогда $(a+b)$ делится на $d$, $(a-b)$ делится на $d$. Следовательно, сумма и разность чисел $a+b$ и $a-b$, равные соответственно $2a$ и $2b$ делятся на $d$. Но числа $a$ и $b$ по условию взаимно просты, поэтому $2$ делится на $d$. Отсюда $d=1$ или $d=2$. Оба эти случая возможны. Действительно, $d=1$, если числа $a$ и $b$ разной четности, и $d=2$, если они нечетны.

Утверждение доказано.

Утверждение

Любые два последовательных натуральных числа взаимно просты.

Утверждение

Наибольший общий делитель любых двух последовательных четных натуральных чисел равен $2$.

Утверждение

Любые два последовательных нечетных натуральных числа взаимно просты.

Утверждение

Если целые числа $a$ и $b$ являются взаимно простыми, то НОД$(a+b; a^2-ab+b^2)$ равен $1$ или $3$.

Утверждение

Если натуральные числа $m$ и $n$ взаимно просты, то НОД$(m+n; m^2+n^2)$ равен $1$ или $2$.

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

Пусть $d$ – общий делитель чисел $m+ n$ и $m^2 + n^2$. Тогда на $d$ делится также число $(m+n)^2$, а значит, и число $(m+ n)^2 - (m^2+n^2 )= 2mn$. Итак, $d$ является общим делителем чисел $m+n$ и $2mn$. Но $m+ n$ и $m$ не могут иметь общих делителей, отличных от 1 (так как $m$ и $n$ взаимно просты), и тоже справедливо для чисел $m+ n$ и $n$. Следовательно, $d$ является делителем числа $2$, т.е. $d = 1$ или $d = 2$.

Утверждение доказано.

Теорема

Пусть $n$ — натуральное число и $n= p_1^{k_1}\cdot p_2^{k_2}\cdot ... \cdot p_s^{k_s}$ его каноническое разложение на простые множители. Тогда каждый натуральный делитель $d$ числа $n$ может быть записан в виде $d=p_1^{m_1}\cdot p_2^{m_2}\cdot ... \cdot p_s^{m_s}$, где $m_i$ целые числа, удовлетворяющие условиям $0\leq m_1 \leq k_1, ... ,0\leq m_s \leq k_s$.

Доказательство:
Пусть $d$ — какой- либо делитель натурального числа $n$ . Так как каждый простой делитель числа $d$ является делителем числа $n$, тогда в разложении $d$ на простые множители могут встречаться только числа из множества ${ p_1, p_2, ... , p_s}$. Поэтому число $d$ представимо в виде $d=p_1^{m_1}\cdot p_2^{m_2}\cdot ... \cdot p_s^{m_s}$.

Теорема доказана.

Теорема

Пусть даны два натуральных числа $a$ и $b$ , а $p_1, p_2, ... , p_s$ — простые числа, входящие в канонические разложения $a$ и $b$ . Представим числа $a$ и $b$ в виде $a= p_1^{k_1}\cdot p_2^{k_2}\cdot ... \cdot p_s^{k_s}$ и $b=p_1^{m_1}\cdot p_2^{m_2}\cdot ... \cdot p_s^{m_s}$ где $m_i\geq 0, k_i\geq 0$ — целые числа.
Тогда
$(a, b) =p_1^{min(k_1,m_1)}\cdot p_2^{min(k_2,m_2)}\cdot ... \cdot p_s^{min(k_s,m_s)}$,
$[a, b] =p_1^{max(k_1,m_1)}\cdot p_2^{max(k_2,m_2)}\cdot ... \cdot p_s^{max(k_s,m_s)}$.

Например, пусть $a=2^3\cdot 3^2\cdot 7$, $b=2^4\cdot 3\cdot 5^2\cdot 11$. Запишем их в виде $a= 2^3\cdot 3^2\cdot 5^0 \cdot7^1\cdot 11^0$ , $b= 2^4\cdot 3^1\cdot 5^2 \cdot 7^0\cdot 11^1$. Тогда $(a,b)=2^3 \cdot 3^1= 24$, $[a, b] = 2^4 \cdot 3^2 \cdot 5^2 \cdot 7^1 \cdot 11^1 = 277 200$.

Замечание. Справедливо равенство $(a, b) \cdot [a, b] = a \cdot b$.