Реферат на тему:
Подільність
Нехай x – дійсне число. Через ?x??будемо позначати найбільше ціле
число, яке не перевищує x.
Теорема. Нехай a та b – цілі числа, при чому b > 0. Тоді існують такі
числа q та r, які визначаються однозначно, що a = b * q + r, при чому 0
? r b,
тоді НСД(a, b) = НСД(b, a mod b). У випадку, коли a = n)
{ m = m – n; p = p – r; q = q – s; }
else
{ n = n – m; r = r – p; s = s – q; }
}
if (m == 0)
{ *k = n; *x = r; *y = s; }
else
{ *k = m; *x = p; *y = q; }
}
Приклад. Розширений алгоритм Евкліда. Обчислення НСД(4864, 3458).
Q r x y a b x2 x1 y2 y1
4864 3458 1 0 0 1
1 1406 1 1 3458 1406 0 1 1 1
2 646 2 3 1406 646 1 2 1 3
2 114 5 7 646 114 2 5 3 7
5 76 27 38 114 76 5 27 7 38
1 38 32 45 76 38 27 32 38 45
2 0 91 128 38 0 32 91 45 128
Результат: НСД(4864, 3458) = 38, при цьому 4864 * 32 + 3458 * (-45) =
38.
Для обчислення найменшого спільного кратного (НСК) можна використати
формулу:
a * b = НСД(a, b) * НСК(a, b).
Приклад. Знайти НСК(12, 18). Скориставшись наведеним алгоритмом,
знайдемо, що НСД(12, 18) = 6. Отже 12 * 18 = 6 * НСК(12, 18). Звідки
НСК(12, 18) = (12 * 18) / 6 = 36.
Нашли опечатку? Выделите и нажмите CTRL+Enter
