Арифметика: наибольший общий делитель и наименьшее общее кратное
Наибольший общий делитель (функция 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 находит наименьшее общее кратное в области целых, рациональных и гауссовых чисел.