Відмінності між версіями «Найбільший спільний дільник»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
м (Обчислення НСД методом розкладу на прості множники: вікіфікація)
(правопис)
 
(Не показані 13 проміжних версій 9 користувачів)
Рядок 1: Рядок 1:
'''Найбі́льший спі́льний дільни́к''' (НСД) двох або більше невід'ємних [[Ціле число|цілих чисел]] — найбільше [[натуральне число]], на яке ці числа [[Подільність|діляться]] без [[Остача|остачі]].
+
'''Найбі́льший спі́льний дільни́к''' (НСД) двох або більше невід'ємних чисел — найбільше [[натуральне число]], на яке ці числа [[Подільність|діляться]] без [[Остача|остачі]].
   
 
== Огляд ==
 
== Огляд ==
Рядок 14: Рядок 14:
   
 
Аналогічно дільниками числа 24 є:
 
Аналогічно дільниками числа 24 є:
  +
: <math> 24 \times 1 = 12 \times 2 = 8 \times 3 = 6 \times 4. \, </math>
 
: <math> 1, 2, 3, 4, 6, 8, 12, 24. \, </math>
 
: <math> 1, 2, 3, 4, 6, 8, 12, 24. \, </math>
   
Рядок 56: Рядок 57:
   
 
== НСД в кільці многочленів ==
 
== НСД в кільці многочленів ==
В [[Кільце (алгебра)|кільці]] многочленів <math>K[X] </math> над довільним [[Поле (алгебра)|полем]] <math>K</math> найбільшим спільним дільником [[многочлен]]ів <math>f(x) </math> і <math>g(x) </math>, принаймі один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеня, який ділить обидва многочлени <math>f(x) </math> і <math>g(x) </math>
+
В [[Кільце (алгебра)|кільці]] многочленів <math>K[X] </math> над довільним [[Поле (алгебра)|полем]] <math>K</math> найбільшим спільним дільником [[многочлен]]ів <math>f(x) </math> і <math>g(x) </math>, принаймні один з яких є відмінний від нуля, називаємо нормований многочлен найвищого степеня, який ділить обидва многочлени <math>f(x) </math> і <math>g(x) </math>
 
Обчислити НСД можна [[Многочлен#Розкладання многочлена на нескоротні множники|розкладаючи многочлен на нескоротні множники]]. Можна застосувати також [[алгоритм Евкліда]].
 
Обчислити НСД можна [[Многочлен#Розкладання многочлена на нескоротні множники|розкладаючи многочлен на нескоротні множники]]. Можна застосувати також [[алгоритм Евкліда]].
   
Рядок 85: Рядок 86:
 
Реалізація без використання рекурсії:
 
Реалізація без використання рекурсії:
   
<syntaxhighlight lang = "csharp">
+
<syntaxhighlight lang="csharp">
 
int gcd(int a, int b)
 
int gcd(int a, int b)
 
{
 
{
  +
if (a == 0) return b;
 
while (b != 0)
 
while (b != 0)
 
{
 
{
int r = a % b;
+
if( a > b ){
  +
int r = a % b;
  +
} else {
  +
int r = b % a;
  +
}
 
a = b;
 
a = b;
 
b = r;
 
b = r;
Рядок 100: Рядок 106:
 
== Див. також ==
 
== Див. також ==
 
* [[Алгоритм Евкліда]]
 
* [[Алгоритм Евкліда]]
  +
* [[Найменше спільне кратне]]
   
 
[[Категорія:Елементарна математика]]
 
[[Категорія:Елементарна математика]]

Поточна версія на 15:06, 17 серпня 2018

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

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

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

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

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

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

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

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

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

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

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

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

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

  • НСД є комутативною функцією: НСД(ab)= НСД(ba).
  • НСД(ab)
  • НСД(abcd) = НСД(НСД(ab), НСД(cd))
  • НСД(ab) =|ab|/НСК(ab), де НСК(ab) найменше спільне кратне чисел ab.

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

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

Тоді

НСД

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

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

,

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

,

Отже,

НСД

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

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

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

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

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

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

,

отримуємо

НСД .

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

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

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

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

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

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