Иллюстрированный самоучитель по Mathematica 5

Арифметика: наибольший общий делитель и наименьшее общее кратное

• Наибольший общий делитель (функция GCD). Наибольший общий делитель в кольце целых чисел.

  Для нахождения наибольшего общего делителя чисел (целых, рациональных или гауссовых) в системе Mathematica предусмотрено две функции: GCD и ExtendedGCD. | Функция GCD находит наибольший общий делитель в области целых, рациональных и гауссовых чисел.

• "Наихудшие" случаи для алгоритмов нахождения наибольшего общего делителя

  "Наихудшим" случаем для классического алгоритма Евклида нахождения наибольшего общего делителя считается случай соседних чисел Фибоначчи. Чтобы оценить быстродействие, попытаемся, например, определить, при каком n будет заметна задержка при вычислении: | GCD[Fibonacci[n + 2] Fibonacci[n + 1]] | Возьмем, например, следующую программу.

• Наибольший общий делитель в области рациональных и гауссовых чисел

  Как мы уже сообщали ранее, функция GCD находит наибольший общий делитель в области целых, рациональных и гауссовых чисел. | Наибольший общий делитель в поле рациональных чисел | Наибольший общий делитель рациональных чисел r1, r2,… определяется как наибольшее рациональное число г, такое, что все числа r1/r, r2 /r,… являются целыми. | Вот пример.

• Линейное представление наибольшего общего делителя (функция ExtendedGCD)

  В ряде задач необходимо найти не только наибольший общий делитель нескольких чисел, но и его представление в виде линейной комбинации этих чисел. Именно эту задачу решает функция ExtendedGCD. Функция ExtendedGCD [ n1, n2,…] возвращает список {g, { r1, r2,…}}, такой, что g= GCD [n1, n2,…] и g = r1n1+r2n2 +…. Вот примеры.

• Наименьшее общее кратное (функция LCM)

  Во множестве всех кратных нескольких данных чисел всегда найдется такое, которое является делителем всякого другого общего кратного этих чисел: это – общее наименьшее кратное. | Функция LCM находит наименьшее общее кратное в области целых, рациональных и гауссовых чисел.