НОД и НОК

1. Записваме $a$ и $b$ с едни и същи прости числа (някои показатели може да са 0): $a = p_1^{a_1} \cdots p_k^{a_k}$, $b = p_1^{b_1} \cdots p_k^{b_k}$. Делителите на $a$ са числата $p_1^{c_1} \cdots p_k^{c_k}$ с $c_i \le a_i$ (виж урока „Делимост и прости числа“).
2. Общ делител има $c_i \le a_i$ и $c_i \le b_i$, т.е. $c_i \le \min(a_i,\ b_i)$. Най-голям е при $c_i = \min(a_i,\ b_i)$ – това е НОД.
3. Общо кратно има показатели $\ge a_i$ и $\ge b_i$; най-малкото е с показатели $\max(a_i,\ b_i)$ – това е НОК.
4. За всеки две числа $\min(x,\ y) + \max(x,\ y) = x + y$. Затова при умножаване на НОД и НОК показателите се събират до $a_i + b_i$ и $\text{НОД} \cdot \text{НОК} = ab$. Проверка: $12 \cdot 360 = 4320 = 72 \cdot 60$.

∎

1. Нека $a = bq + r$. Ако $d \mid a$ и $d \mid b$, то $d \mid a - bq = r$. Обратно, ако $d \mid b$ и $d \mid r$, то $d \mid bq + r = a$. Значи двойките $(a,\ b)$ и $(b,\ r)$ имат едни и същи общи делители – и еднакъв най-голям общ делител.
2. Остатъците намаляват строго: $b > r_1 > r_2 > \ldots \ge 0$. Естествените числа не могат да намаляват безкрайно, затова след най-много $b$ стъпки остатъкът става 0.
3. Ако последната стъпка е $r_{n-1} = q \cdot r_n + 0$, то $\text{НОД}(r_{n-1},\ r_n) = r_n$, а по първата стъпка НОД не се е променял през целия път. Значи $\text{НОД}(a,\ b) = r_n$.

∎

1. Разглеждаме всички положителни числа от вида $ax + by$ с цели $x,\ y$ (такива има – например $a^2 + b^2$). Нека $d = ax_0 + by_0$ е най-малкото от тях.
2. Делим $a$ на $d$ с остатък: $a = dq + r$, $0 \le r < d$. Тогава $r = a - dq = a(1 - qx_0) + b(-qy_0)$ също е от вида $ax + by$. Ако $r > 0$, той би бил по-малък от $d$ – противоречие. Значи $r = 0$ и $d \mid a$. По същия начин $d \mid b$.
3. Всеки общ делител на $a$ и $b$ дели $ax_0 + by_0 = d$, следователно не е по-голям от $d$. Значи $d = \text{НОД}(a,\ b)$.
4. Числата $ax + by$ са точно кратните на $d$: всяко такова число се дели на $d$ (защото $d \mid a$ и $d \mid b$), а $kd = a(kx_0) + b(ky_0)$.

∎

1. Ако има решение, $d \mid a$ и $d \mid b$ дават $d \mid ax + by = c$. Обратно, ако $c = kd$, от Безу $ax_0 + by_0 = d$ и $(kx_0;\ ky_0)$ е решение.
2. Нека $(x_0;\ y_0)$ и $(x;\ y)$ са решения. Изваждаме: $a(x - x_0) = -b(y - y_0)$. Делим на $d$ и означаваме $a_1 = \frac{a}{d}$, $b_1 = \frac{b}{d}$: $$a_1(x - x_0) = -b_1(y - y_0)$$
3. Числата $a_1$ и $b_1$ са взаимно прости (ако $e$ дели и двете, то $de$ дели $a$ и $b$, значи $e = 1$). Щом $b_1$ дели $a_1(x - x_0)$, по лемата на Евклид (приложена за всеки прост делител на $b_1$) $b_1 \mid x - x_0$, т.е. $x = x_0 + b_1 t$.
4. Заместваме: $a_1 b_1 t = -b_1(y - y_0)$, откъдето $y = y_0 - a_1 t$. Обратно, всяка такава двойка е решение: $a(x_0 + b_1 t) + b(y_0 - a_1 t) = c + \frac{ab}{d}t - \frac{ab}{d}t = c$.

∎