Найбільший спільний дільник

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних цілих чисел — найбільше натуральне число, на яке ці числа діляться без остачі.

Огляд[ред.ред. код]

Позначення[ред.ред. код]

Найбільший спільник дільник двох чисел a і b позначається як НСД(ab), деколи (ab). В англомовній літературі прийнято вживати позначення gcd(ab).

Приклад[ред.ред. код]

Число 54 може бути виражене як добуток двох інших цілих чисел кількома способами:

 54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6. \,

Отже дільниками числа 54 є:

 1, 2, 3, 6, 9, 18, 27, 54. \,

Аналонічно дільниками числа 24 є:

 1, 2, 3, 4, 6, 8, 12, 24. \,

Числа, які знаходяться в обох цих списках, є спільними дільниками чисел 54 та 24:

 1, 2, 3, 6. \,

Найбільшим серед них є число 6. Воно є найбільшим спільним дільником чисел 54 та 24. Можна записати:

 (54,24) = 6. \,

Скорочення дробів[ред.ред. код]

Найбільший спільний дільник використовується для скорочення дробів. Наприклад, НСД(42, 56) = 14, тому,

{42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}.

Властивості[ред.ред. код]

Обчислення НСД методом розкладу на прості множники[ред.ред. код]

Нехай розкладання чисел на прості множники має вигляд:

a=2^{q_2}\cdot 3^{q_3}\cdot \dots \cdot p_k^{q_{p_k}}
b=2^{r_2}\cdot 3^{r_3}\cdot \dots \cdot p_k^{r_{p_k}}

Тоді

НСД(a,b)= 2^{\min(q_2;r_2)} \cdot 3^{\min(q_3;r_3)}
           \cdot \dots \cdot p_k^{\min(q_{p_k};q_{p_k})}

Приклад[ред.ред. код]

Визначимо НСД(840,396) . Розклад на прості множники:

   840 = 2^3 \cdot 3 \cdot 5 \cdot 7
   396 = 2^2 \cdot 3^2 \cdot 11 ,

або, подаючи для наглядності нульові степені,

   840 = 2^3 \cdot 3^1 \cdot 5^1 \cdot 7^1  \cdot 11^0
   396 = 2^2 \cdot 3^2  \cdot 5^0 \cdot 7^0 \cdot 11^1 ,

Отже,

НСД(840,396)=2^2\cdot 3^1\cdot 5^0\cdot 7^0 \cdot 11^0=12

Ефективним алгоритмом обчислення НСД є алгоритм Евкліда

НСД в кільці многочленів[ред.ред. код]

В кільці многочленів K[X] над довільним полем K найбільшим спільним дільником многочленів f(x) і g(x) , принаймі один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеня, який ділить обидва многочлени f(x) і g(x) Обчислити НСД можна розкладаючи многочлен на нескоротні множники. Можна застосувати також алгоритм Евкліда.

Приклад[ред.ред. код]

Обчислимо НСД двох многочленів над полем дійсних чисел:

 f(x)=2x^3+6x^2+14x+10
 g(x)=3x^2-3x-6

Розкладаючи многочлени на нескоротні множники

 f(x)=2(x+1)(x^2+2x+5)
 g(x)=3(x+1)(x-2) ,

отримуємо

НСД (f(x),g(x))=x+1.

Приклади програмної реалізації знаходження НСД[ред.ред. код]

Рекурсивна реалізація:

int gcd(int a, int b)
{
   if (b == 0) return a;
   return gcd(b, a % b);
}

Реалізація без використання рекурсії:

int gcd(int a, int b)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Див. також[ред.ред. код]