Линейное представление наибольшего
Линейное представление наибольшего общего делителя — функция ExtendedGCD
В ряде задач необходимо найти не только наибольший общий делитель нескольких чисел, но и его представление в виде линейной комбинации этих чисел. Именно эту задачу решает функция ExtendedGCD. Функция ExtendedGCD [ n1, n2, ...] возвращает список {g, { r1 , r2, ...}}, такой, что g= GCD [n1, n2, ...] и g = r1n1+r2n2 + .... Вот примеры.
{g,{r,s}}=ExtendedGCD[n=45,m=36] (9,{!,-!}}{g,{r,s}}=ExtendedGCD[210°+3,З50 + 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[ Dot If[GCD[n, m]==l, Print[n,":",m, ":", ExtendedGCD[fn[n],fn[m]]]],{m,n-l}],(n,10}]
Результаты запишем в виде таблицы .
Заметьте, что довольно часто в данной таблице встречается пара r = 1,5= -2. Это не случайно, поскольку при n = n+1 выполняется равенство -(2n -1)+2-(2(n -1) = -1.
Пример 6.9. Линейное представление наибольшего общего делителя чисел, десятичная запись которых состоит из m единиц и n единиц. Наибольший общий делитель чисел, десятичная запись которых состоит из т единиц и п единиц, является числом того же вида, причем количество единиц в нем равно d = НОД(n, m). Выясним, как он представляется в виде линейной комбинации.
Вот нужные нам определения.
a111[n]:=(10^n-1)/9 d: = GCD[n, m]
Теперь можно написать и программу:
Dot Dot Print[n,":",m,":", ExtendedGCD[alll[n],alll[m]]],{m,n-l}],{n,10}]
Заметьте, что десятичная запись чисел r и s в данной таблице содержит только цифры 0 и 1. Я не удивлюсь, если вы предположите, что это связано с наличием некоторых полиномиальных тождеств и потому значения г и s получаются в результате подстановки 10 (основания системы счисления) в них. Например, строку таблицы
| 9 |
6 |
111 |
1 |
-1000 |
можно истолковать так:
