Наибольший общий делитель - Greatest common divisor

В математика, то наибольший общий делитель (gcd) двух или более целые числа, которые не все равны нулю, является наибольшим положительным целым числом, которое разделяет каждое из целых чисел. Для двух целых чисел Икс, у, наибольший общий делитель Икс и у обозначается ${displaystyle gcd (x, y)}$. Например, НОД 8 и 12 равно 4, то есть ${displaystyle gcd (8,12) = 4}$.^[1][2][3]

В названии «наибольший общий делитель» прилагательное «наибольший» может быть заменено на «наивысший», а слово «делитель» может быть заменено на «фактор», чтобы другие имена включали наибольший общий делитель (gcf), так далее.^[4][5][6][7] Исторически сложилось так, что другие названия той же концепции включали наибольшая общая мера.^[8]

Это понятие можно распространить на многочлены (см. Наибольший общий делитель полинома ) и другие коммутативные кольца (видеть § В коммутативных кольцах ниже).

Обзор

Обозначение

В этой статье мы будем обозначать наибольший общий делитель двух целых чисел а и б как gcd (а,б). Некоторые авторы используют (а,б).^[2][3][6][9]

Пример

Какой наибольший общий делитель 54 и 24?

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

${displaystyle 54 imes 1 = 27 imes 2 = 18 imes 3 = 9 imes 6.,}$

Таким образом делители 54 находятся: ${displaystyle 1,2,3,6,9,18,27,54.,}$

По аналогии, делители 24 находятся: ${displaystyle 1,2,3,4,6,8,12,24.,}$

Общие числа в этих двух списках - общие делители из 54 и 24:

${displaystyle 1,2,3,6.,}$

Наибольшее из них - 6. То есть наибольший общий делитель 54 и 24 - 6. Один пишет:

${displaystyle gcd (54,24) = 6.,}$

Копростые числа

Два числа называются взаимно простыми, или совмещать, если их наибольший общий делитель равен 1.^[10] Например, 9 и 28 являются взаимно простыми числами.

Геометрический вид

Прямоугольник 24 на 60 покрыт десятью квадратными плитками 12 на 12, где 12 - это НОД 24 и 60. В общем, а-к-б прямоугольник можно покрыть квадратной плиткой со стороной c только если c является общим делителем а и б.

Например, прямоугольную область 24 на 60 можно разделить на сетку из: квадратов 1 на 1, квадратов 2 на 2, квадратов 3 на 3, квадратов 4 на 4, 6 на -6 квадратов или 12 на 12 квадратов. Следовательно, 12 - это наибольший общий делитель 24 и 60. Таким образом, прямоугольную область 24 на 60 можно разделить на сетку из квадратов 12 на 12, с двумя квадратами вдоль одного края (24/12 = 2) и пять квадратов вдоль другого (60/12 = 5).

Приложения

Уменьшение фракций

Наибольший общий делитель полезен для уменьшения фракции к самые низкие сроки.^[11] Например, gcd (42, 56) = 14, следовательно,

${displaystyle {frac {42} {56}} = {frac {3cdot 14} {4cdot 14}} = {frac {3} {4}}.}$

Наименьший общий множитель

Наибольший общий делитель можно использовать для нахождения наименьшего общего кратного двух чисел, когда известен наибольший общий делитель, используя соотношение^[1]

${displaystyle operatorname {lcm} (a, b) = {frac {| acdot b |} {operatorname {gcd} (a, b)}}.}.}$

Расчет

Использование разложения на простые множители

В принципе, наибольшие общие делители могут быть вычислены путем определения простые факторизации двух чисел и сравнивая множители, как в следующем примере: для вычисления НОД (18, 84) мы находим простые факторизации 18 = 2 · 3² и 84 = 2² · 3 · 7, и поскольку «перекрытие» двух выражений равно 2 · 3, gcd (18, 84) = 6. На практике этот метод применим только для малых чисел; вычисление разложения на простые множители занимает слишком много времени.

Вот еще один конкретный пример, проиллюстрированный Диаграмма Венна. Предположим, нужно найти наибольший общий делитель 48 и 180. Сначала найдите простые множители двух чисел:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5.

Их объединяет две двойки и тройка:

^[12]

Наименьшее общее кратное = 2 × 2 × (2 × 2 × 3) × 3 × 5 = 720

Наибольший общий делитель = 2 × 2 × 3 = 12.

Алгоритм Евклида

Воспроизвести медиа

Анимация, показывающая применение алгоритма Евклида для нахождения наибольшего общего делителя 62 и 36, равного 2.

Намного более эффективный метод - это Евклидов алгоритм, который использует алгоритм деления Такие как длинное деление в сочетании с наблюдением, что НОД двух чисел также делит их разницу.

Например, чтобы вычислить НОД (48,18), разделите 48 на 18, чтобы получить частное 2 и остаток 12. Затем разделите 18 на 12, чтобы получить частное 1 и остаток 6. Затем разделите 12 на 6 чтобы получить остаток от 0, что означает, что 6 - это НОД. Здесь мы проигнорировали частное на каждом шаге, за исключением того, что отметили, когда остаток достиг 0, что означает, что мы пришли к ответу. Формально алгоритм можно описать так:

${displaystyle gcd (a, 0) = a}$

${displaystyle gcd (a, b) = gcd (b, a, mathrm {mod}, b)}$,

куда

${displaystyle a, mathrm {mod}, b = a-bleftlfloor {a over b} ightfloor}$.

Если оба аргумента больше нуля, тогда алгоритм может быть записан в более элементарных терминах следующим образом:

${displaystyle gcd (a, a) = a}$,

${displaystyle gcd (a, b) = gcd (a-b, b) quad,}$ если а > б

${displaystyle gcd (a, b) = gcd (a, b-a) quad,}$ если б > а

Алгоритм Лемера GCD

Алгоритм Лемера основан на наблюдении, что начальные коэффициенты, полученные с помощью алгоритма Евклида, могут быть определены только на основе первых нескольких цифр; это полезно для чисел, которые больше, чем компьютерное слово. По сути, извлекаются начальные цифры, обычно образующие одно или два компьютерных слова, и запускаются алгоритмы Евклида на этих меньших числах, если гарантируется, что частные совпадают с теми, которые были бы получены с исходными числами. Эти частные собираются в небольшую матрицу преобразования 2 на 2 (то есть матрицу однословных целых чисел) для использования их всех одновременно для уменьшения исходных чисел. Этот процесс повторяется до тех пор, пока числа не достигнут размера, для которого двоичный алгоритм (см. Ниже) более эффективен.

Этот алгоритм повышает скорость, поскольку сокращает количество операций с очень большими числами и может использовать скорость аппаратной арифметики для большинства операций. Фактически, большинство частных очень малы, поэтому достаточное количество шагов алгоритма Евклида можно собрать в матрицу 2 на 2 целых чисел из одного слова. Когда алгоритм Лемера встречает слишком большое частное, он должен вернуться к одной итерации алгоритма Евклида с Евклидово деление большого количества.

Бинарный алгоритм GCD

Алгоритм двоичного НОД использует только вычитание и деление на 2. Метод выглядит следующим образом: Пусть а и б быть двумя неотрицательными целыми числами. Пусть целое число d быть 0. Есть пять возможностей:

• а = б.

Как gcd (а, а) = а, желаемый НОД а × 2^d (в качестве а и б изменяются в остальных случаях, и d записывает, сколько раз а и б были оба разделены на 2 на следующем шаге, НОД исходной пары является произведением а и 2^d).

• Обе а и б четные.

Тогда 2 - общий делитель. Разделите оба а и б на 2, увеличить d на 1, чтобы записать, сколько раз 2 - это общий делитель и продолжить.

• а даже и б странно.

Тогда 2 не является общим делителем. Разделять а на 2 и продолжить.

• а это странно и б даже.

Тогда 2 не является общим делителем. Разделять б на 2 и продолжить.

• Обе а и б странные.

Как gcd (а,б) = gcd (б,а), если а < б затем обменять а и б. Номер c = а − б положительно и меньше, чем а. Любое число, которое делит а и б должен также разделить c так что каждый общий делитель а и б также является общим делителем б и c. По аналогии, а = б + c и каждый общий делитель б и c также является общим делителем а и б. Итак, две пары (а, б) и (б, c) имеют одинаковые общие делители, поэтому gcd (а,б) = gcd (б,c). Более того, поскольку а и б оба странные, c четно, процесс можно продолжить с парой (а, б) заменены меньшими числами (c/2, б) без изменения gcd.

Каждый из вышеперечисленных шагов уменьшает хотя бы один из а и б оставляя их неотрицательными и поэтому их можно повторять только конечное число раз. Таким образом, в конечном итоге процесс приводит к а = б, стопорный случай. Тогда НОД а × 2^d.

Пример: (а, б, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1); исходный НОД, таким образом, является продуктом 6 из 2^d = 2¹ и а= б= 3.

Алгоритм двоичного GCD особенно легко реализовать на двоичных компьютерах. Его вычислительная сложность является

${displaystyle O ((log a + log b) ^ {2})}$

Вычислительная сложность обычно выражается длиной п входа. Здесь эта длина ${displaystyle n = log a + log b,}$ и сложность, таким образом,

${displaystyle O (n ^ {2})}$.

Другие методы

${displaystyle gcd (1, x) = y,}$ или функция Тома. Вылупление внизу указывает эллипсы (то есть пропуск точек из-за очень высокой плотности).

Если а и б оба ненулевые, наибольший общий делитель а и б можно вычислить, используя наименьший общий множитель (lcm) из а иб:

${displaystyle gcd (a, b) = {frac {| acdot b |} {имя оператора {lcm} (a, b)}}}$,

но чаще lcm вычисляется из gcd.

С помощью Функция Тома ж,

${displaystyle gcd (a, b) = afleft ({frac {b} {a}} ight),}$

который обобщается на а и б рациональное число или же соизмеримый действительные числа.

Кит Славин показал, что а ≥ 1:

${displaystyle gcd (a, b) = log _ {2} prod _ {k = 0} ^ {a-1} (1 + e ^ {- 2ipi kb / a})}$

это функция, которая может быть оценена для сложных б.^[13] Вольфганг Шрамм показал, что

${displaystyle gcd (a, b) = сумма пределов _ {k = 1} ^ {a} exp (2pi ikb / a) ограничения суммы cdot _ {dleft | aight.} {frac {c_ {d} (k)} { d}}}$

является вся функция в переменной б для всех положительных целых чисел а куда c_d(k) является Сумма Рамануджана.^[14]

Сложность

В вычислительная сложность вычисления наибольших общих делителей широко изучается.^[15] Если использовать Евклидов алгоритм и элементарные алгоритмы умножения и деления, вычисления наибольшего общего делителя двух целых чисел не более п биты является ${displaystyle O (n ^ {2}).}$ Это означает, что вычисление наибольшего общего делителя имеет, с точностью до постоянного множителя, такую ​​же сложность, как и умножение.

Однако если быстро алгоритм умножения , можно изменить алгоритм Евклида для повышения сложности, но вычисление наибольшего общего делителя становится медленнее, чем умножение. Точнее, если умножение двух целых чисел п бит занимает время Т(п), то самый быстрый из известных алгоритмов определения наибольшего общего делителя имеет сложность ${displaystyle Oleft (T (n) log night).}$ Это означает, что самый быстрый из известных алгоритмов имеет сложность ${displaystyle Oleft (n, (log n) ^ {2} log log night).}$

Предыдущие сложности действительны для обычных модели вычислений, конкретно многоленточные машины Тьюринга и машины с произвольным доступом.

Таким образом, вычисление наибольших общих делителей относится к классу задач, разрешимых в квазилинейное время. А тем болеесоответствующие проблема решения принадлежит к классу п задач, решаемых за полиномиальное время. Проблема GCD неизвестна NC, поэтому нет известного способа распараллеливать это качественно; и не известно, чтобы быть P-полный, что означало бы, что эффективное распараллеливание вычислений GCD маловероятно. Shallcross et al. показал, что родственная проблема (EUGCD, определение остаточной последовательности, возникающей во время алгоритма Евклида) NC-эквивалентна проблеме целочисленное линейное программирование с двумя переменными; если какая-либо проблема в NC или это P-полный, другой тоже.^[16] С NC содержит NL, также неизвестно, существует ли компактный алгоритм вычисления НОД, даже для недетерминированных машин Тьюринга.

Хотя не известно, что проблема в NC, параллельные алгоритмы асимптотически быстрее чем существует алгоритм Евклида; самый быстрый из известных детерминированных алгоритмов Чора и Голдрайха, который (в CRCW-PRAM модель) может решить проблему в О(п/бревно п) время с п^{1 + ε} процессоры.^[17] Рандомизированные алгоритмы может решить проблему в О((бревно п)²) время на ${displaystyle exp left (Oleft ({sqrt {nlog n}} ight) ight)}$ процессоры^{[требуется разъяснение ]} (это суперполином ).^[18]

Характеристики

• Каждый общий делитель а и б является делителем gcd (а, б).
• gcd (а, б), куда а и б не равны нулю, могут быть определены альтернативно и эквивалентно как наименьшее положительное целое число d который можно записать в виде d = а⋅п + б⋅q, куда п и q целые числа. Это выражение называется Личность Безу. Числа п и q как это можно вычислить с помощью расширенный алгоритм Евклида.
• gcd (а, 0) = |а|, за а ≠ 0, так как любое число является делителем 0, а наибольший делитель а есть |а|.^[3][6] Обычно это используется как базовый случай в алгоритме Евклида.
• Если а делит продукт б⋅c, и gcd (а, б) = d, тогда а/d разделяет c.
• Если м - целое неотрицательное число, то gcd (м⋅а, м⋅б) = м⋅gcd (а, б).
• Если м любое целое число, то gcd (а + м⋅б, б) = gcd (а, б).
• Если м является положительным общим делителем а и б, тогда gcd (а/м, б/м) = gcd (а, б)/м.
• НОД - это мультипликативная функция в следующем смысле: если а₁ и а₂ относительно простые, то gcd (а₁⋅а₂, б) = gcd (а₁, б) ⋅gcd (а₂, б). В частности, вспоминая, что НОД - положительная целочисленная функция, получаем, что gcd (а, б⋅c) = 1 если и только если gcd (а, б) = 1 и gcd (а, c) = 1.
• НОД - это коммутативный функция: gcd (а, б) = gcd (б, а).
• НОД - это ассоциативный функция: gcd (а, gcd (б, c)) = gcd (gcd (а, б), c).
• Если ни один из а₁, а₂, . . . , а_р равен нулю, то НОД ( а₁, а₂, . . . , а_р ) = gcd (gcd ( а₁, а₂, . . . , а_р-1 ), а_р ).^[19][20]
• gcd (а, б) тесно связан с наименьший общий множитель lcm (а, б): у нас есть

  gcd (а, б) ⋅lcm (а, б) = |а⋅б|.

Эта формула часто используется для вычисления наименьших общих кратных: сначала вычисляется НОД с помощью алгоритма Евклида, а затем произведение заданных чисел делится на их НОД.

• Следующие версии распределенность верно:

  gcd (а, lcm (б, c)) = lcm (gcd (а, б), НОД (а, c))

  lcm (а, gcd (б, c)) = gcd (lcm (а, б), lcm (а, c)).

• Если у нас есть уникальные простые факторизации а = п₁^е₁ п₂^е₂ ⋅⋅⋅ п_м^е_м и б = п₁^ж₁ п₂^ж₂ ⋅⋅⋅ п_м^ж_м куда е_я ≥ 0 и ж_я ≥ 0, затем gcd из а и б является

  gcd (а,б) = п₁^{мин (е₁,ж₁)} п₂^{мин (е₂,ж₂)} ⋅⋅⋅ п_м^{мин (е_м,ж_м)}.

• Иногда полезно определить НОД (0, 0) = 0 и lcm (0, 0) = 0 потому что тогда натуральные числа стать полный распределительная решетка с gcd как встреча и lcm как операция соединения.^[21] Это расширение определения также совместимо с приведенным ниже обобщением коммутативных колец.
• В Декартова система координат, gcd (а, б) можно интерпретировать как количество отрезков между точками с целыми координатами на прямой отрезок присоединение к пунктам (0, 0) и (а, б).
• Для неотрицательных целых чисел а и б, куда а и б не равны нулю, что можно доказать, рассматривая алгоритм Евклида в базовомп:^[22]

  gcd (п^а − 1, п^б − 1) = п^{gcd (а,б)} − 1.

• An личность с участием Функция Эйлера:

  ${displaystyle gcd (a, b) = sum _ {k | a {ext {and}} k | b} varphi (k).}$

Вероятности и ожидаемое значение

В 1972 году Джеймс Э. Ниманн показал, что k целые числа, выбранные независимо и равномерно из {1, ...,п}, взаимно просты с вероятностью 1 /ζ(k) в качестве п уходит в бесконечность, где ζ относится к Дзета-функция Римана.^[23] (Видеть совмещать для вывода.) Этот результат был расширен в 1987, чтобы показать, что вероятность того, что k случайные целые числа имеют наибольший общий делитель d является d^−k/ ζ (k).^[24]

Используя эту информацию, ожидаемое значение функции наибольшего общего делителя можно увидеть (неформально), что она не существует, когда k = 2. В этом случае вероятность того, что НОД равна d является d⁻²/ ζ (2), и поскольку ζ (2) = π²/ 6 имеем

${displaystyle mathrm {E} (mathrm {2}) = sum _ {d = 1} ^ {infty} d {frac {6} {pi ^ {2} d ^ {2}}} = {frac {6} { pi ^ {2}}} сумма _ {d = 1} ^ {infty} {frac {1} {d}}.}$

Это последнее суммирование гармонический ряд, который расходится. Однако когда k ≥ 3, ожидаемое значение четко определено и, согласно приведенному выше аргументу,

${displaystyle mathrm {E} (k) = sum _ {d = 1} ^ {infty} d ^ {1-k} zeta (k) ^ {- 1} = {frac {zeta (k-1)} {zeta (k)}}.}$

За k = 3, это примерно равно 1,3684. За k = 4, это примерно 1,1 · 106.

Если один аргумент gcd зафиксирован на некотором значении ${displaystyle m}$, он станет мультипликативной функцией в другой переменной, и можно показать, что^{[нужна цитата ]}

${displaystyle {frac {1} {N}} lim _ {N o infty} sum _ {n = 1} ^ {N} gcd (n, m) = prod _ {p ^ {alpha} || n} left ( 1 + альфа - {frac {alpha} {p}} ight)}$

Здесь, ${displaystyle prod _ {p ^ {alpha} || n}}$ делает продукт по всем основным полномочиям ${displaystyle p ^ {alpha}}$ такой, что ${displaystyle p ^ {alpha} | n}$ но ${displaystyle p ^ {alpha +1} ot | n}$

В коммутативных кольцах

Понятие наибольшего общего делителя можно в более общем виде определить для элементов произвольной коммутативное кольцо, хотя, как правило, нет необходимости в наличии по одному для каждой пары элементов.

Если р коммутативное кольцо и а и б находятся в р, то элемент d из р называется общий делитель из а и б если он разделяет оба а и б (то есть, если есть элементы Икс и у в р такой, что d·Икс = а и d·у = б).Если d является общим делителем а и б, и каждый общий делитель а и б разделяет d, тогда d называется наибольший общий делитель из а и б.

В этом определении два элемента а и б вполне может иметь несколько наибольших общих делителей или вообще не иметь. Если р является область целостности затем любые два gcd из а и б должно быть ассоциировать элементы, поскольку по определению одно должно разделять другое; действительно, если gcd существует, любой из его партнеров также является gcd. Существование НОД не гарантируется в произвольных областях целостности. Однако если р это уникальная область факторизации, то любые два элемента имеют НОД, и в более общем случае это верно в gcd домены.Если р это Евклидова область в котором евклидово деление дается алгоритмически (как, например, когда р = F[Икс] куда F это поле, или когда р кольцо Гауссовские целые числа ), то наибольшие общие делители могут быть вычислены с использованием формы алгоритма Евклида, основанного на процедуре деления.

Ниже приведен пример целостной области с двумя элементами, не имеющими НОД:

${displaystyle R = mathbb {Z} left [{sqrt {-3}} ,, ight], quad a = 4 = 2cdot 2 = left (1+ {sqrt {-3}} ,, ight) left (1- { sqrt {-3}} ,, ight), quad b = left (1+ {sqrt {-3}} ,, ight) cdot 2.}$

Элементы 2 и 1 +√−3 два максимальные общие делители (то есть, любой общий делитель, кратный 2, связан с 2, то же самое верно для 1 +√−3, но они не связаны, поэтому нет наибольшего общего делителя а иб.

В соответствии со свойством Безу мы можем в любом коммутативном кольце рассматривать набор элементов вида па + qb, куда п и q диапазон над кольцом. Это идеальный создано а и б, и обозначается просто (а, б). В кольце, все идеалы которого главны (a главная идеальная область или PID), этот идеал будет идентичен множеству кратных некоторого кольцевого элемента d; тогда это d является наибольшим общим делителем а и б. Но идеальный (а, б) может быть полезен даже тогда, когда нет наибольшего общего делителя а и б. (В самом деле, Эрнст Куммер использовал этот идеал в качестве замены gcd в своем лечении Последняя теорема Ферма, хотя он представлял его как набор, кратный некоему гипотетическому или идеальный, элемент кольца d, откуда и теоретико-кольцевой член.)

Смотрите также

• Безу домен
• Наименьший общий знаменатель
• Унитарный делитель

Примечания

Рекомендации

• Эндрюс, Джордж Э. (1994) [1971], Теория чисел, Дувр, ISBN  9780486682525
• Харди, Г. Х.; Райт, Э.М. (1979), Введение в теорию чисел (Пятое изд.), Оксфорд: Oxford University Press, ISBN  978-0-19-853171-5
• Лонг, Кальвин Т. (1972), Элементарное введение в теорию чисел (2-е изд.), Лексингтон: Д. К. Хит и компания, LCCN  77171950
• Петтофреццо, Энтони Дж .; Биркит, Дональд Р. (1970), Элементы теории чисел, Энглвудские скалы: Prentice Hall, LCCN  71081766

дальнейшее чтение

• Дональд Кнут. Искусство программирования, Том 2: Получисловые алгоритмы, Третье издание. Аддисон-Уэсли, 1997. ISBN  0-201-89684-2. Раздел 4.5.2: Наибольший общий делитель, стр. 333–356.
• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7. Раздел 31.2: Наибольший общий делитель, стр. 856–862.
• Сондерс Маклейн и Гаррет Биркофф. Обзор современной алгебры, Четвертый выпуск. MacMillan Publishing Co., 1977. ISBN  0-02-310070-2. 1–7: «Евклидов алгоритм».

внешняя ссылка

• Величайшая общая мера: последние 2500 лет, к Александр Степанов