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

В математике , то наибольший общий делитель ( НОД ) двух или более целых чисел , которые не все равны нулю, является самым большим положительным целым числом , которое делит каждый из целых чисел. Для двух целых чисел x , y обозначается наибольший общий делитель x и y . Например, НОД 8 и 12 равны 4, то есть .

В названии «наибольший общий делитель» прилагательное «наибольший» может быть заменено на «наивысший», а слово «делитель» может быть заменено на «фактор», чтобы другие имена включали наивысший общий делитель ( hcf ) и т. Д. Исторически сложилось так, что другие названия одного и того же понятия включали в себя наибольшую общую меру .

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

Обзор

Определение

Наибольший общий делитель (НОД) двух ненулевых целых чисел через и Ь является наибольшим положительным целым числом d таким образом, что d является делителем обоих а и б ; то есть существуют целые числа e и f такие, что a = de и b = df , а d - наибольшее такое целое число. НОД для a и b обычно обозначается gcd ( a , b ) .

Это определение также применяется, когда одно из a и b равно нулю. В этом случае НОД - это абсолютное значение ненулевого целого числа: НОД ( a , 0) = НОД (0, a ) = | а | . Этот случай важен как завершающий шаг алгоритма Евклида .

Приведенное выше определение не может использоваться для определения gcd (0, 0) , поскольку 0 × n = 0 , а значит, ноль не имеет наибольшего делителя. Однако ноль является его собственным наибольшим делителем, если наибольшее значение понимается в контексте отношения делимости, поэтому gcd (0, 0) обычно определяется как 0. Это сохраняет обычные тождества для GCD и, в частности, тождество Безу , а именно, что gcd ( a , b ) порождает тот же идеал, что и { a , b } . Этому соглашению придерживаются многие системы компьютерной алгебры . Тем не менее, некоторые авторы оставляют gcd (0, 0) неопределенным.

НОД элементов a и b является их наибольшим положительным общим делителем в отношении предварительного порядка делимости . Это означает, что общие делители a и b в точности делят их НОД. Обычно это доказывается с помощью леммы Евклида , основной теоремы арифметики или алгоритма Евклида . Это значение слова «величайший», которое используется для обобщения концепции НОД.

Пример

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

Таким образом, полный список делителей 54 равен . Аналогично делители 24 равны . Общие числа этих двух списков являются общими делителями 54 и 24, то есть

Из них наибольшее число равно 6, так что это наибольший общий делитель :

Вычисление всех делителей двух чисел таким способом обычно неэффективно, особенно для больших чисел, у которых много делителей. Более эффективные методы описаны в § Расчет .

Coprime числа

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

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

«Высокий тонкий прямоугольник, разделенный на сетку квадратов. Прямоугольник - два квадрата в ширину и пять квадратов в высоту».
Прямоугольник 24-по-60 покрыт десять 12-по-12 квадратных плитки, где 12 является НОДОМ 24 и 60. В более общем плане , An матрицы с размерностью Ь прямоугольник может быть покрыт квадратными плитками длиной стороны с единственным если c является общим делителем a и b .

Например, прямоугольную область 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).

Приложения

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

Наибольший общий делитель полезен для сокращения дробей до наименьших членов . Например, gcd (42, 56) = 14, следовательно,

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

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

Расчет

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

Наибольшие общие делители могут быть вычислены путем определения разложения двух чисел на простые множители и сравнения множителей. Например, чтобы вычислить gcd (48, 180), мы находим факторизации на простые множители 48 = 2 4  · 3 1 и 180 = 2 2  · 3 2  · 5 1 ; НОД тогда будет 2 мин (4,2)  · 3 мин (1,2)  · 5 мин (0,1) = 2 2  · 3 1  · 5 0 = 12, как показано на диаграмме Венна . Соответствующее НОК тогда равно 2 max (4,2)  · 3 max (1,2)  · 5 max (0,1) = 2 4  · 3 2  · 5 1 = 720.

Наименьшее общее multiple.svg

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

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

Метод, введенный Евклидом для вычисления наибольших общих делителей, основан на том факте, что для двух положительных целых чисел a и b таких, что a > b , общие делители a и b совпадают с общими делителями a - b и b .

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

Например, чтобы вычислить gcd (48,18) , нужно действовать следующим образом:

Итак, gcd (48, 18) = 6 .

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

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

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

Более эффективным методом является алгоритм Евклида , вариант, в котором разность двух чисел a и b заменяется остатком от евклидова деления (также называемого делением с остатком ) числа a на b .

Обозначив этот остаток в виде мод б , алгоритм заменяет ( , б ) по ( б , моды б ) несколько раз , пока пара не является ( г , 0) , где d представляет наибольший общий делитель.

Например, чтобы вычислить gcd (48,18), вычисление выглядит следующим образом:

Это снова дает gcd (48, 18) = 6 .

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

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

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

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

Бинарный алгоритм GCD использует только вычитание и деление на 2. Метод заключается в следующем: пусть a и b - два неотрицательных целых числа. Пусть целое число d равно 0. Есть пять возможностей:

  • а = б .

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

  • И a, и b четные.

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

  • a четное, а b нечетное.

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

  • a нечетное, а b четное.

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

  • И a, и b нечетные.

Поскольку gcd ( a , b ) = gcd ( b , a ), если a < b, то поменяйте местами a и b . Число c = a - b положительно и меньше a . Любое число, которое делит a и b, должно также делить c, поэтому каждый общий делитель a и b также является общим делителем b и c . Аналогично, a = b + c, и каждый общий делитель b и c также является общим делителем a и b . Таким образом, две пары ( a , b ) и ( b , c ) имеют одинаковые общие делители, и, следовательно, gcd ( a , b ) = gcd ( b , c ). Более того, поскольку a и b оба нечетны, c четно, процесс может быть продолжен с заменой пары ( a , b ) меньшими числами ( c / 2, b ) без изменения GCD.

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

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

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

Вычислительная сложность обычно выражается длиной n входных данных. Здесь эта длина и сложность, таким образом,

.

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

или функция Тома. Штриховка внизу указывает на эллипсы (т. Е. Отсутствие точек из-за очень высокой плотности).

Если a и b оба отличны от нуля, наибольший общий делитель a и b может быть вычислен с использованием наименьшего общего кратного (НОК) a и  b :

,

но чаще НОК вычисляется из НОД.

Используя функцию Тома f ,

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

Кейт Славин показал, что для нечетного a  ≥ 1:

которая является функцией, которая может быть вычислена для комплексного b . Вольфганг Шрамм показал, что

- целая функция от переменной b для всех натуральных чисел a, где c d ( k ) - сумма Рамануджана .

Сложность

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

Однако, если используется алгоритм быстрого умножения , можно модифицировать алгоритм Евклида для улучшения сложности, но вычисление наибольшего общего делителя становится медленнее, чем умножение. Точнее, если умножение двух целых чисел по n бит занимает время T ( n ) , то самый быстрый известный алгоритм вычисления наибольшего общего делителя имеет сложность. Это означает, что самый быстрый известный алгоритм имеет сложность

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

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

Хотя проблема не связана с ЧПУ , существуют параллельные алгоритмы, асимптотически более быстрые, чем алгоритм Евклида; Самый быстрый из известных детерминированных алгоритмов разработан Чором и Голдрайхом, который (в модели CRCW-PRAM ) может решить проблему за время O ( n / log n ) с помощью n 1 + ε процессоров. Рандомизированные алгоритмы могут решить проблему за время O ((log n ) 2 ) на процессорах (это суперполином ).

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

  • Каждый общий делитель a и b является делителем gcd ( a , b ) .
  • gcd ( a , b ) , где a и b не равны нулю, может быть определен альтернативно и эквивалентно как наименьшее положительное целое число d, которое может быть записано в форме d = ap + bq , где p и q - целые числа. Это выражение называется личностью Безу . Такие числа p и q можно вычислить с помощью расширенного алгоритма Евклида .
  • gcd ( a , 0) = | а | , при a ≠ 0 , поскольку любое число является делителем 0, а наибольший делитель числа a равен | а |, Обычно это используется в качестве базового случая в алгоритме Евклида.
  • Если a делит произведение bc и gcd ( a , b ) = d , то a / d делит c .
  • Если m - неотрицательное целое число, то gcd ( ma , mb ) = m ⋅gcd ( a , b ) .
  • Если m - любое целое число, то gcd ( a + mb , b ) = gcd ( a , b ) .
  • Если m является положительным общим делителем a и b , то gcd ( a / m , b / m ) = gcd ( a , b ) / m .
  • НОД является мультипликативной функцией в следующем смысле: если a 1 и a 2 взаимно просты, то gcd ( a 1a 2 , b ) = gcd ( a 1 , b ) ⋅gcd ( a 2 , b ) . В частности, вспоминая, что GCD является положительной целочисленной функцией, получаем, что gcd ( a , bc ) = 1 тогда и только тогда, когда gcd ( a , b ) = 1 и gcd ( a , c ) = 1 .
  • НОД - это коммутативная функция: gcd ( a , b ) = gcd ( b , a ) .
  • НОД является ассоциативной функцией: gcd ( a , gcd ( b , c )) = gcd (gcd ( a , b ), c ) . Таким образом, gcd ( a , b , c , ...) может использоваться для обозначения GCD нескольких аргументов.
  • gcd ( a , b ) тесно связан с наименьшим общим кратным lcm ( a , b ) : мы имеем
    gcd ( a , b ) ⋅lcm ( a , b ) = | ab | .
Эта формула часто используется для вычисления наименьших общих кратных: сначала вычисляется НОД с помощью алгоритма Евклида, а затем произведение заданных чисел делится на их НОД.
  • Верны следующие версии дистрибутивности :
    gcd ( a , lcm ( b , c )) = lcm (gcd ( a , b ), gcd ( a , c ))
    lcm ( a , gcd ( b , c )) = gcd (lcm ( a , b ), lcm ( a , c )) .
  • Если у нас есть уникальные разложения на простые множители a = p 1 e 1 p 2 e 2 ⋅⋅⋅ p m e m и b = p 1 f 1 p 2 f 2 ⋅⋅⋅ p m f m, где e i ≥ 0 и f i ≥ 0 , то НОД элементов a и b равен
    gcd ( a , b ) = p 1 min ( e 1 , f 1 ) p 2 min ( e 2 , f 2 ) ⋅⋅⋅ p m min ( e m , f m ) .
  • Иногда полезно определить gcd (0, 0) = 0 и lcm (0, 0) = 0, потому что тогда натуральные числа становятся полной распределительной решеткой с GCD в качестве встречи и LCM в качестве операции соединения. Это расширение определения также совместимо с приведенным ниже обобщением коммутативных колец.
  • В системе декартовых координат , НОД ( , б ) можно интерпретировать как число сегментов между точками с целыми координатами на прямой отрезок прямой , соединяющей точки (0, 0) и ( , б ) .
  • Для неотрицательных целых чисел a и b , где a и b не равны нулю, можно доказать, рассматривая алгоритм Евклида в базе  n :
    НОД ( n a - 1, n b - 1) = n gcd ( a , b ) - 1 .
  • Тождество с участием totient функции Эйлера :

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

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

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

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

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

Если один аргумент GCD зафиксирован на некотором значении , он станет мультипликативной функцией в другой переменной, и можно показать, что

Здесь обозначает произведение по всем степеням простых чисел, таким что, но

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

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

Если R является коммутативным кольцом, а и б находятся в R , то элемент д из R называется общим делителем из и б , если она делит оба A и B (то есть, если есть элементы х и у в R такие, что d · x  =  a и d · y  =  b ). Если d является общим делителем и б , и каждый общий делитель и б делит d , то d называется наибольший общий делитель из и б .

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

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

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

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

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

Примечания

использованная литература

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