.

Подільність (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
1 2129
Скачать документ

Реферат на тему:

Подільність

Нехай 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

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020