Наибольший общий делитель (функция GCD). Наибольший общий делитель в кольце целых чисел.
Для нахождения наибольшего общего делителя чисел (целых, рациональных или гауссовых) в системе Mathematica предусмотрено две функции: GCD и ExtendedGCD.
Функция GCD находит наибольший общий делитель в области целых, рациональных и гауссовых чисел.
Чтобы найти наибольший общий делитель чисел n1, n2,…, можно использовать функцию GCD [ n1, n2,…].
Вот примеры ее применения для нахождения наибольшего общего делителя двух чисел.
GCD[36.45] 9 GCD[2200 + 3, 3300 + 80] 349a = 177 ^ 5 + 30621 * 173 ^ 3 - 173 ^ 5177309584821b = 173 ^ 5 + 30621 * 177 ^ 3 - 177 ^ 5151037867129 c = 173 ^ 4 + 30621 ^ 2 + 177 ^ 4 2814896923GCD[a, b] 30637 GCD[a, c] 30637 GCD[b, c] 30637Пример 6.1. Графики функции GCD.
Давайте теперь построим несколько графиков функции GCD. Поскольку это функция двух аргументов, построим изображения поверхности z = GCDflntegerPart [x], IntegerPart [у] ].
Для этого используем функцию Plot3D.
А вот вид вблизи.
Вот пример нахождения наибольшего общего делителя нескольких чисел.
GCD[Fibonacci[945], Fibonacci[901, Fibonacci[450]] 1134903170Раз уж мы заговорили о числах Фибоначчи, значит, мы не можем обойти случаи, которые традиционно считаются "наихудшими" для алгоритмов нахождения наибольшего общего делителя.