WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Подільність - Реферат

Подільність - Реферат


Реферат на тему:
Подільність
Нехай x - дійсне число. Через x будемо позначати найбільше ціле число, яке не перевищує x.
Теорема. Нехай a та b - цілі числа, при чому b > 0. Тоді існують такі числа q та r, які визначаються однозначно, що a = b * q + r, при чому 0 r < q. Число q називається неповною часткою, а r - залишком від ділення a на b.
Доведення. Очевидно, що 0 < - < 1 або 0 < a - 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.
Loading...

 
 

Цікаве