Найбільший спільний дільник

Матеріал з Вікіпедії — вільної енциклопедії.

Зміст

1 Означення
2 Властивості
3 Обчислення НСД методом розкладу на прості множники
- 3.1 Приклад
4 НСД в кільці многочленів
- 4.1 Приклад

[ред.] Означення

Найбільшим спільним дільником (НСД) двох цілих чисел a, b, принаймі одне з яких є відмінне від нуля, називаємо найбільше натуральне число, яке є дільником обох цих чисел. Позначаємо НСД(a, b), деколи (a, b), в англомовній літературі GCD(a, b). Означення можна – очевидним способом – узагальнити на довільну кількість аргументів.

[ред.] Властивості

НСД(a, b)= НСД(b, a) (перестановка аргументів не змінює НСД).

$1\le$ НСД(a, b) $\le \min(|a|,|b|)$

НСД(a, b, c, d) = НСД(НСД(a, b), НСД(c, d) )

НСД(a, b) =|ab|/НСК(a, b), де НСК(a, b) найменше спільне кратне чисел a, b.

[ред.] Обчислення НСД методом розкладу на прості множники

Нехай розклад чисел на прості множники:

$a=2^{q_2}\cdot 3^{q_3}\cdot \dots \cdot p_k^{q_{p_k}}$

$b=2^{r_2}\cdot 3^{r_3}\cdot \dots \cdot p_k^{r_{p_k}}$

Тоді

НСД $(a,b)= 2^{\min(q_2;r_2)} \cdot 3^{\min(q_3;r_3)} \cdot \dots \cdot p_k^{\min(q_{p_k};q_{p_k})}$

[ред.] Приклад

Визначимо НСД $(840,396)$ . Розклад на прості множники:

$840 = 2^3 \cdot 3 \cdot 5 \cdot 7$

$396 = 2^2 \cdot 3^2 \cdot 11$ ,

або, подаючи для наглядності нульові степені,

$840 = 2^3 \cdot 3^1 \cdot 5^1 \cdot 7^1 \cdot 11^0$

$396 = 2^2 \cdot 3^2 \cdot 5^0 \cdot 7^0 \cdot 11^1$ ,

Отже,

НСД $(840,396)=2^2\cdot 3^1\cdot 5^0\cdot 7^0 \cdot 11^0=12$

Ефективним алгоритмом обчислення НСД є алгоритм Евкліда

[ред.] НСД в кільці многочленів

В кільці многочленів $K [X]$ над довільним полем $K$ найбільшим спільним дільником многочленів $f (x)$ і $g (x)$ , принаймі один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеню, який ділить обидва многочлени $f (x)$ і $g (x)$ Обчислити НСД можна розкладаючи многочлен на нескоротні множники. Можна застосувати також алгоритм Евкліда.

[ред.] Приклад

Обчислимо НСД двох мночленів над полем дійсних чисел:

$f (x) = 2 x 3 + 6 x 2 + 14 x + 10$
$g (x) = 3 x 2 - 3 x - 6$

Розкладаючи многочлени на нескоротні множники

$f (x) = 2(x + 1)(x 2 + 2 x + 5)$
$g (x) = 3(x + 1)(x - 2)$ ,

отримуємо

НСД $(f (x), g (x)) = x + 1$ .

Найбільший спільний дільник

Матеріал з Вікіпедії — вільної енциклопедії.

Зміст

[ред.] Означення

[ред.] Властивості

[ред.] Обчислення НСД методом розкладу на прості множники

[ред.] Приклад

[ред.] НСД в кільці многочленів

[ред.] Приклад

Перегляди

Особисті інструменти

Навігація

Участь

Пошук

Панель інструментів

Іншими мовами