Линейное представление наибольшего

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

111

-1000

можно истолковать так:

Наибольший общий делитель

Для нахождения наибольшего общего делителя чисел (целых, рациональных или гауссовых) в системе Mathematica предусмотрено две функции: GCD и ExtendedGCD.

Наибольший общий делитель — функция GCD

Функция GCD находит наибольший общий делитель в области целых, рациональных и гауссовых чисел.

Наибольший общий делитель в кольце целых чисел

Чтобы найти наибольший общий делитель чисел n1, n2, ..., можно использовать функцию GCD [ n1, n2, ...]. Вот примеры ее применения для нахождения наибольшего общего делителя двух чисел.
GCD[36,45] 9 GCD[2200 + 3, 3300 + 80] 349 а=177^5+30621*173^3-173^5 177309584821 b=173^5+30621*177^3-177^5+ 151037867129 С=173^4+30621^2+177^4 2814896923 GCD[a,b] 30637 GCD[а,с] 30637 GCD[b,c]30637
Пример 6.1. Графики функции GCD.

Давайте теперь построим несколько графиков функции GCD. Поскольку это функция двух аргументов, построим изображения поверхности z = GCDflntegerPart [x], IntegerPart [у] ]. Для этого используем функцию Plot3D.

Наименьшее общее кратное — функция LCM

Во множестве всех кратных нескольких данных чисел всегда найдется такое, которое является делителем всякого другого общего кратного этих чисел: это — общее наименьшее кратное.

Функция LCM находит наименьшее общее кратное в области целых, рациональных и гауссовых чисел.

Задача нахождения наибольшего общего делителя

Резюме

Задача нахождения наибольшего общего делителя и наименьшего общего кратного нескольких чисел столь важна, что ее приходится решать практически постоянно. Даже занимаясь решением задач вариационного исчисления, математической физики, линейной алгебры, математического анализа, аналитической геометрии или просто решая какие-нибудь дифференциальные уравнения, вам практически не удастся избежать сложения или вычитания дробей — действий, которым учатся в пятом классе. И как только вам приходится выполнять эти действия, вы так или иначе вспоминаете о наибольшем общем делителе и наименьшем общем кратном. К счастью, система Mathematica если и не позволяет забыть об этих двух важнейших понятиях арифметики, то избавляет вас от рутинной работы по их нахождению. В системе Mathematica реализованы весьма эффективные, вполне современные алгоритмы нахождения наибольшего общего делителя и наименьшего общего кратного. Пользуясь ими, вы можете быть уверены, что используете самые современные инструменты. Конечно, их применение целиком зависит от вас. Вы можете составить таблицы, найти тождества, решить неопределенные уравнения...