Подільність, Детальна інформація

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

Подільність

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

Теорема. Нехай a та b – цілі числа, при чому b > 0. Тоді існують такі числа q та r, які визначаються однозначно, що a = b * q + r, при чому 0 \xF0A3 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 \xF0CE 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