Линейное представление наибольшего общего делителя (функция ExtendedGCD)
В ряде задач необходимо найти не только наибольший общий делитель нескольких чисел, но и его представление в виде линейной комбинации этих чисел. Именно эту задачу решает функция ExtendedGCD. Функция ExtendedGCD [ n1, n2,…] возвращает список {g, { r1, r2,…}}, такой, что g= GCD [n1, n2,…] и g = r1n1+r2n2 +…. Вот примеры.
{g,{r,s}} = ExtendedGCD[n = 45, m = 36] (9,{1,-1}}{g,{r,s}} = ExtendedGCD[210 + 3, 350 + 8] {1,{62013782892351778750374,-109502757290992473821761130785} }Пример 6.7.
Единица как линейная комбинация чисел Ферма. Так как числа Ферма являются взаимно простыми, их наибольший общий делитель равен единице. Выясним, как единица представляется в виде линейной комбинации соседних чисел Ферма.
Вот нужная нам функция.
FermatNumber[n_] := 2 ^ (2 ^ n) - NТеперь можно написать и программу.
Do[Print[n, ":", ExtendedGCD[FermatNumber[n + 1], FermatNumber[n]]], {n, 10}]Результаты запишем в виде таблицы.
Заметьте, что в таблице при n>1 числа rn заканчиваются цифрой 8, а числа sn – цифрой 1.
Пример 6.8.
Единица как линейная комбинация чисел 2n-1 и 2m-1 при взаимно простых пит. Так как числа 2n -1 и 2m -1 взаимно просты, если взаимно просты n и m, то единицу можно представить в виде линейной комбинации чисел 2n -1 и 2m -1 при взаимно простых пит. Выясним, до какого номера n(предполагая, что т<п) система Mathematica сможет в приемлемое время проверить взаимную простоту этих чисел.
Вот нужная нам функция.
fn[n_] := 2 ^ n - 1Теперь можно написать и программу.
Do[Do[If[GCD[n, m] == 1, Print[n, ":", m, ":", ExtendedGCD[fn[n], fn[m]]]], {m, n - 1}], (n, 10}]Результаты запишем в виде таблицы.
Заметьте, что довольно часто в данной таблице встречается пара r = 1.5= -2. Это не случайно, поскольку при n = n+1 выполняется равенство -(2n -1)+2-(2(n -1) = -1.