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

Подільність

Нехай x – дійсне число. Через ?x??будемо позначати найбільше ціле
число, яке не перевищує x.

Теорема. Нехай a та b – цілі числа, при чому b > 0. Тоді існують такі
числа q та r, які визначаються однозначно, що a = b * q + r, при чому 0
? r < q. Число q називається неповною часткою, а r – залишком від ділення a на b. , то це і доводить теорему. b (a ділиться на b). -4, тому що 20 = (-4) * 5. Властивості подільності. Нехай a, b та c – цілі числа. Тоді 1. a | a. 2. Якщо a | b та b | a, то a = ±b. 3. Якщо a | b та b | c, то a | c. 4. Якщо a | b та a | c, то a | (bx + cy) для всіх x, y ? Z. Алгоритм Евкліда Обчислення найбільшого спільного дільника (НСД) двох чисел a та b базується на наступному факті: якщо a та b – додатні цілі числа, a > b,
тоді НСД(a, b) = НСД(b, a mod b). У випадку, коли a < b маємо: НСД(a, b) = НСД(b, a mod b) = НСД(b, a). ВХІД: два невід’ємних числа a та b. ВИХІД: НСД(a, b) int nsd(int a, int b) { int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } Приклад. Обчислення НСД(4864, 3458). 4864 = 1* 3458 + 1406 3458 = 2 * 1406 + 646 1406 = 2 * 646 + 76 114 = 1 * 76 + 38 76 = 2 * 38 + 0 Алгоритм Евкліда можна розширити для знаходження таких цілих чисел x та y, що a * x + b * y = d. ВХІД: два невід’ємних числа a та b, a і b. ВИХІД: d = НСД(a, b) та такі цілі числа x та y, що a * x + b * y = d. void nsdrozsh(int a, int b, int *x, int *y, int *k) { int p, q, r, s, m, n; m = a; n = b; p = 1; q = 0; r = 0; s = 1; while (m!=0 && n!=0) { if (m >= 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.

Похожие записи