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

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

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

Пример 6.7.
Единица как линейная комбинация чисел Ферма. Так как числа Ферма являются взаимно простыми, их наибольший общий делитель равен единице. Выясним, как единица представляется в виде линейной комбинации соседних чисел Ферма.

Вот нужная нам функция.

Теперь можно написать и программу.

Результаты запишем в виде таблицы.

Заметьте, что в таблице при n>1 числа r_n заканчиваются цифрой 8, а числа s_n – цифрой 1.

Пример 6.8.
Единица как линейная комбинация чисел 2_n-1 и 2_m-1 при взаимно простых пит. Так как числа 2ⁿ -1 и 2^m -1 взаимно просты, если взаимно просты n и m, то единицу можно представить в виде линейной комбинации чисел 2ⁿ -1 и 2^m -1 при взаимно простых пит. Выясним, до какого номера n(предполагая, что т<п) система Mathematica сможет в приемлемое время проверить взаимную простоту этих чисел.

Вот нужная нам функция.

Теперь можно написать и программу.

Результаты запишем в виде таблицы.

Заметьте, что довольно часто в данной таблице встречается пара r = 1.5= -2. Это не случайно, поскольку при n = n+1 выполняется равенство -(2ⁿ -1)+2-(2(ⁿ -1) = -1.