Нод двух функций как найти - Исправление недочетов и поиск решений вместе с Examum.ru

Исходный полином f(x) (его коэффициенты)

Делим на следующий полином / многочлен

Первый многочлен

Второй многочлен

Остатки от деления двух полиномов

Рассматривается вычисление наибольшего общего делителя (НОД) двух многочленов. Принцип который используется, такой же как и для нахождения НОД обычных чисел.

Отличие нашего калькулятора в том, что

1. Он показывает промежуточные остатки при вычислении

2. Многочлены могут быть комплексными, то есть содержать мнимые числа.

Теории больше не будет, и сразу перейдем к примерам вычисления, и вы поймете, как это вычисляется.

Найти НОД двух многочленов

$g(x)%20=%202*x^{3}-*x^{2}-2*x+2$

Сначала выбираем тот полином у которого степень выше и коэффицент при этой степени наибольший.

Делим один на другой f(x) на g(x). Можно делать это руками а можно воспользоваться калькулятором деления многочлена на многочлен.

Получаем остаток

Теперь делим уже g(x) на полученный остаток

получаем

Еще раз проделываем процедуру

получаем остаток

Если мы еще раз проведем такую же процедуру то получим в остатке ноль.

Закончили деление и смотрим на результат.

Предпоследнее значение от деления двух многочленов и есть значение НОД.

То есть наш ответ

Кто хочет получить результат в виде дроби то стоит обратить внимание на Непрерывные, цепные дроби онлайн которая нам это значение в виде дроби и окончательный красивый ответ есть

НОД двух функций

$g(x)%20=%202*x^{3}-*x^{2}-2*x+2$

равен $-frac{81}{1600}$

Как же пользоватся ботом?

Выписыаем коэффициенты полиномов в строку разделяя их пробелом.

Получили

1 1 -4 0 5 это у нас первый полином

2 -1 -2 2 а это второй

Вводим их в соответсвующие поля и нажимаем рассчитать.

Смотрим результат

Первый многочлен

Второй многочлен

Остатки от деления двух полиномов

То есть всё то что мы делали руками.

Замечание: Как видно, в остаток всегда «примешивается» какая то мелкая погрешность. Это надо учитывать, в окончательном оформлении своего решения.Но это не всегда так. Если коэффициенты при старших степенях полиномов на любом этапе вычислений равны единицы, то погрешность результата нулевая.

Попробуем найти НОД комплексных многочленов

Пишем любые коэффициенты с мнимыми значениями и получаем

Первый многочлен

Второй многочлен

Остатки от деления двух полиномов

Еще один пример, с «нюансом»

Первый многочлен

Второй многочлен

Остатки от деления двух полиномов

Смотрите!! НОД не равен так как на предыдущей строке, уже получается ноль, правда с погрешность после 11 знака после запятой, но мы то с Вами понимаем (!!!) что это все равно ноль.

И наш правильный ответ или вынеся за скобку общий множитель получаем что НОД равен

Да, некоторые возразят «Ну, тут еще и думать надо..» Хотелось бы возразить, но не буду, так как согласен с ними что «Думать надо!»

Надеюсь, Ваши расчеты стали еще проще и быстрее!

Источник

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

Определение. Если каждый из
двух многочленов делится без остатка
на третий, то он называется общим
делителем первых двух.

Наибольшим общим делителем (НОД)
двух многочленов называется их
общий делитель наивысшей степени.

НОД можно находить с помощью разложения
на неприводимые множители или с помощью
алгоритма Евклида.

Пример 40 Найти НОД многочленови.

Решение. Разложим оба многочлена
на множители:

Из
разложения видно, что искомым НОДом
будет многочлен (х– 1).

Пример 41 Найти НОД многочленови.

Решение. Разложим оба многочлена
на множители.

Для многочлена
возможными рациональными корнями будут
числа1,2,3 и6.
С помощью подстановки убеждаемся, чтох= 1 является корнем. Разделим
многочлен на (х– 1) по схеме Горнера.

	1	–6	11	–6
1	1	1 – 6 = –5	–5 + 11 = 6	6 – 6 = 0

Следовательно,
,
где разложение квадратного трехчленабыло произведено по теореме Виета.

	1	0	–7	6
1	1	1 – 0 = 1	1 – 7 = –6	–6 + 6 = 0

Следовательно,
,
где разложение квадратного трехчленабыло произведено по теореме Виета.

Сравнив разложение многочленов на
множители, находим, что искомым НОДом
будет многочлен (х– 1)(х– 2).

Аналогично
можно находить и НОД для нескольких
многочленов.

Тем не менее, метод нахождения НОДа
путем разложения на множители доступен
не всегда. Способ, позволяющий находить
НОД для всех случаев, называется
алгоритмом Евклида.

Схема алгоритма Евклида такова. Один
из двух многочленов делят на другой,
степень которого не выше степени
первого. Далее, за делимое всякий раз
берут тот многочлен, который служил в
предшествующей операции делителем, а
за делитель берут остаток, полученный
при той же операции. Этот процесс
прекращается, как только остаток
окажется равным нулю. Покажем этот
алгоритм на примерах.

Рассмотрим многочлены, использовавшиеся
в двух предыдущих примерах.

Пример 42 Найти НОД многочленови.

Решение. Разделимна«уголком»:

Теперь
разделим делитель
на остатокх– 1:

x+ 1

Так как
последнее деление произошло без остатка,
то НОДом будет х– 1, т. е. многочлен,
использовавшийся в качестве делителя
при этом делении.

Пример 43 Найти НОД многочленови.

Решение. Для нахождения НОД
воспользуемся алгоритмом Евклида.
Разделимна«уголком»:

Произведем
второе деление. Для этого пришлось бы
разделить предыдущий делитель
на остаток,
но так как=,
для удобства будем делить многочленне на,
а на.
От такой замены решение задачи не
изменится, так как НОД пары многочленов
определяется с точностью до постоянного
множителя. Имеем:

Остаток
оказался равным нулю, значит, последний
делитель, т. е. многочлен

и будет искомым НОДом.

Дробно-рациональные функции

Определения и утверждения к 2.5 можно
найти в [1, с. 206-208].

Дробно-рациональной функцией с
действительными коэффициентами
называется выражение вида
,
гдеи‑ многочлены.

Дробно-рациональная функция (в дальнейшем
будем называть ее «дробь») называется
правильной, если степень многочлена,
стоящего в числителе, строго меньше
степени многочлена, стоящего в
знаменателе. В противном случае она
называетсянеправильной.

Алгоритм приведения неправильной дроби
к правильной называется «выделением
целой части».

Пример 44 Выделить целую часть дроби:.

Решение. Для того, чтобы выделить
целую часть дроби необходимо разделить
числитель дроби на ее знаменатель.
Разделим числитель данной дроби на
ее знаменатель «уголком»:

Так как
степень получившегося многочлена
меньше степени делителя, то процесс
деления закончен. В итоге:

=.
Получившаяся в результате дробьявляется правильной.

Дробь вида
называется простейшей, если φ(x
) – неприводимый многочлен, а
степеньменьше степени φ(x ).

Замечание. Обратите внимание, что
сравниваются степени числителя и
неприводимого многочлена в знаменателе
(без учета степени α).

Для дробей с действительными коэффициентами
существует 4 вида простейших дробей:

Любая правильная дробь
может быть представлена в виде суммы
простейших дробей, знаменатели которых
есть всевозможные делители.

Алгоритм
разложения дроби на простейшие:

Если
дробь – неправильная, то выделяем
целую часть, а на простейшие раскладываем
получившуюся правильную дробь.
Раскладываем
знаменатель правильной дроби на
множители.
Записываем
правильную дробь в виде суммы простейших
дробей с неопределенными коэффициентами.
Приводим
к общему знаменателю сумму дробей в
правой части.
Находим
неопределенные коэффициенты:

— либо приравнивая коэффициенты при
одинаковых степенях у левого и правого
приведенных числителей;

— либо подставляя конкретные (как правило
корни общего их знаменателя) значения
x.

Записываем
ответ с учетом целой части дроби.

Пример 45 Разложить на простейшие.

Решение. Так как данная
дробно-рациональная функция является
неправильной, выделим целую часть:

= 1 +.

Разложим
получившуюся дробь
на простейшие. Вначале разложим на
множители знаменатель. Для этого найдем
его корни по стандартной формуле:

Запишем
разложение дробно-рациональной функции
на простейшие, используя неопределенные
коэффициенты:

Приведем
правую часть равенства к общему
знаменателю:

Составляем
систему, приравнивая коэффициенты при
одинаковых степенях в числителях левой
и правой дробей:

Ответ:
.

Пример 46 Разложить на простейшие.

Решение. Так как данная дробь
является правильной (т. е. степень
числителя меньше степени знаменателя),
выделять целую часть не надо. Разложим
знаменатель дроби на множители:.

Запишем
разложение данной дроби на простейшие,
используя неопределенные коэффициенты:

.
По утверждению, знаменатели простейших
дробей должны бытьвсевозможнымиделителями знаменателя дроби:

.
(2.2)
Можно было бы составить систему
уравнений, приравняв числители левой
и правой дробей, но в данном примере
вычисления будут слишком громоздки.
Упростить их поможет следующий прием:
подставим в числители по очереди корни
знаменателя.

При х = 1:

Прих= ‑1:

Теперь для
определения оставшихся коэффициентов
АиСдостаточно будет приравнять
коэффициенты при старшей степени и
свободные члены. Их можно найти, не
раскрывая скобок:

В левой части первого уравнения стоит
0, так как в числителе левой дроби в
(2.2) нет слагаемого с,
а в правой дроби у слагаемого скоэффициентA + C.
В левой части второго уравнения стоит
0, так как в числителе левой дроби в
(2.2) свободный член равен нулю, а у
числителя правой дроби в (2.2) свободный
член равен (‑A +
B + C
+ D). Имеем:

Ответ:.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Калькулятор вычисляет наибольший общий делитель (НОД) двух многочленов методом Евклида. Коэффициенты многочлена могут быть целыми, простыми дробями или комплексными числами с целыми или дробными коэффициентами. Результатом является полином, который делит оба исходных полинома без остатка или единица, если такого полинома не нашлось.

Наибольший общий делитель (НОД) двух многочленов

Алгоритм корректировки остатков (псевдо-остатков)

Оценка метода вычисления остатков

Вычисляет НОД коэффициентов на каждом шаге.

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Проблема взрывного роста коэффициентов остатков

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

Максимальное сокращение коэффициентов можно получить, поделив, коэффициенты остатка на общий НОД коэффициентов, но этот способ может быть вычислительно сложным для полиномов больших степеней со сложными коэффициентами.

В качестве компромиссного варианта используют алгоритмы на основе вычисления субрезультанта псевдоостатков полиномов (Subresultant PRS). Наш калькулятор использует два таких алгоритма (Алгоритм 1 и Алгоритм 3), описанные В.С. Брауном в статье The Subresultant PRS Algorithm¹.
Для оценки работы алгоритма калькулятор выводит таблицу псевдоостатков и вычисляет НОД их коэффициентов. Чем меньше НОД в этой таблице, тем эффективнее работает алгоритм.

Источник

Алгоритм Евклида — нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Решение задачи на языке программирования Python

Алгоритм нахождения НОД делением

Большее число делим на меньшее.
Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
Если есть остаток, то большее число заменяем на остаток от деления.
Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print(a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для определения НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Если условием завершения цикла является равенство хотя бы одной из переменных нулю (a == 0 or b == 0), то условием продолжения его работы является обратное этому условие — обе переменные должны иметь отличные от нуля значения (a != 0 and b != 0).

Блок-схема алгоритма Евклида

Для того, чтобы вышеприведенная программа могла обрабатывать отрицательные числа, в логическом выражении при if должны сравниваться модули значений переменных: if abs(a) > abs(b):. Иначе большим числом может оказаться меньшее по модулю. В этом случае интерпретатор Питона в качестве остатка от деления выдает вещественное число. В результате это приводит к зацикливанию, так как низвести переменные до нуля становится как минимум маловероятным.

Алгоритм нахождения НОД вычитанием

Из большего числа вычитаем меньшее.
Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла).
Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 — 18 = 12
18 — 12 = 6
12 — 6 = 6
6 — 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = int(input())
b = int(input())
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print(a)

Функция, вычисляющая НОД

def gcd(m, n):
    while m != n:
        if m > n:
            m = m - n
        else:
            n = n - m
    return n
 
 
a = int(input())
b = int(input())
 
print(gcd(a, b))

Функция `gcd` модуля `math`

В модуле math языка программирования Python есть функция gcd, вычисляющая наибольший общий делитель двух чисел.

>>> import math
>>> math.gcd(30, 18)
6

Больше задач в PDF

Источник

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII^[1] и X^[2] книгах «Начал». В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.

Первое описание алгоритма находится в «Началах» Евклида (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время^[3]. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако в XIX веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида также был обобщён на другие математические структуры, такие как узлы и многомерные полиномы.

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA^[4], широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений^[5], при построении непрерывных дробей^[6], в методе Штурма^[7]. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратов^[8] и основная теорема арифметики^[9].

Содержание

1 История
2 Описание
- 2.1 Алгоритм Евклида для целых чисел
- 2.2 Геометрический алгоритм Евклида
- 2.3 Пример
3 Применения
- 3.1 Расширенный алгоритм Евклида и соотношение Безу
- 3.2 Цепные дроби
- 3.3 Линейные диофантовы уравнения
4 Вариации и обобщения
- 4.1 Евклидово кольцо
- 4.2 Обобщённый алгоритм Евклида для многочленов
- 4.3 Ускоренные версии алгоритма
5 Примечания
6 Литература
7 Ссылки

История[править | править вики-текст]

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля^[3]. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел^[1] и в X книге для нахождения наибольшей общей меры двух однородных величин^[2]. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника)^[10]. Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Описание[править | править вики-текст]

Алгоритм Евклида для целых чисел[править | править вики-текст]

Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел

$a>b>r_{1}>r_{2}>r_{3}>r_{4}>cdots >r_{n}$

определена тем, что каждое $r_{k}$ — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

$a=bq_{0}+r_{1},$

$b=r_{1}q_{1}+r_{2},$

$r_{1}=r_{2}q_{2}+r_{3},$

$r_{k-2}=r_{k-1}q_{k-1}+r_{k},$

$r_{n-2}=r_{n-1}q_{n-1}+r_{n},$

$r_{n-1}=r_{n}q_{n}.$

Тогда НОД(a, b), наибольший общий делитель a и b, равен r_n, последнему ненулевому члену этой последовательности^[11].

Существование таких r₁, r₂, …, r_n, то есть возможность деления с остатком m на n для любого целого m и целого n ≠ 0, доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений^[12]:

Пусть a = b⋅q + r, тогда НОД (a, b) = НОД (b, r).

Доказательство

Пусть k — любой общий делитель чисел a и b, не обязательно наибольший, тогда a = t₁⋅k и b = t₂⋅k, где t₁ и t₂ — целые числа из определения.
Тогда k является также общим делителем чисел b и r, так как b делится на k по определению, а r = a — b⋅q = (t₁ — t₂⋅q)⋅k (выражение в скобках есть целое число, следовательно, k делит r без остатка).
Обратное также верно и доказывается аналогично пункту 2: любой делитель b и r так же является делителем a и b.
Следовательно, все общие делители пар чисел (a, b) и (b, r) совпадают. Другими словами, нет общего делителя у чисел (a, b), который не был бы также делителем (b, r), и наоборот.
В частности, наибольший общий делитель остается тем же самым. Что и требовалось доказать.

НОД(r, 0) = r для любого ненулевого r (так как 0 делится на любое целое число, кроме нуля).

Геометрический алгоритм Евклида[править | править вики-текст]

Пусть даны два отрезка длины a и b. Вычтем из большего отрезка меньший и заменим больший отрезок полученной разностью. Повторяем эту операцию, пока отрезки не станут равны. Если это произойдёт, то исходные отрезки соизмеримы, и последний полученный отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В таком виде алгоритм описан Евклидом^[2] и реализуется с помощью циркуля и линейки.

Пример[править | править вики-текст]

Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (q₀ = 2), оставаясь с остатком 147:

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (q₁ = 3), оставаясь с остатком 21:

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (q₂ = 7), оставаясь без остатка:

147 = 7 × 21 + 0.

Таким образом последовательность a > b > r₁ > r₂ > r₃ > … > r_n в данном конкретном случае будет выглядеть так:

1071 > 462 > 147 > 21.

Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462) = 21.

В табличной форме шаги были следующие:

Шаг k	Равенство	Частное и остаток
0	1071 = q₀ 462 + r₀	q₀ = 2 и r₀ = 147
1	462 = q₁ 147 + r₁	q₁ = 3 и r₁ = 21
2	147 = q₂ 21 + r₂	q₂ = 7 и r₂ = 0; алгоритм заканчивается

Применения[править | править вики-текст]

Расширенный алгоритм Евклида и соотношение Безу[править | править вики-текст]

Формулы для $r_{i}$ могут быть переписаны следующим образом:

$r_{1}=a+b(-q_{0})$

$r_{2}=b-r_{1}q_{1}=a(-q_{1})+b(1+q_{1}q_{0})$

НОД $(a,b)=r_{n}=as+bt$

Здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу^[13]. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Цепные дроби[править | править вики-текст]

Алгоритм Евклида достаточно тесно связан с цепными дробями^[6]. Отношение a/b допускает представление в виде цепной дроби:

${frac {a}{b}}=[q_{0};q_{1},q_{2},cdots ,q_{n}]$

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t/s, взятому со знаком минус:

$[q_{0};q_{1},q_{2},cdots ,q_{n-1}]=-{frac {t}{s}}$

Последовательность равенств, задающая алгоритм Евклида, может быть переписана в форме:

${begin{aligned}{frac {a}{b}}&=q_{0}+{frac {r_{0}}{b}}\{frac {b}{r_{0}}}&=q_{1}+{frac {r_{1}}{r_{0}}}\{frac {r_{0}}{r_{1}}}&=q_{2}+{frac {r_{2}}{r_{1}}}\&{} vdots \{frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{frac {r_{k}}{r_{k-1}}}\&{} vdots \{frac {r_{N-2}}{r_{N-1}}}&=q_{N}end{aligned}}$

Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объединены в форме:

${frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {r_{1}}{r_{0}}}}}$

Третье равенство может быть использовано, чтобы заменить знаменатель выражения r₁/r₀, получим:

${frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {r_{2}}{r_{1}}}}}}}$

Последнее отношение остатков r_k/r_k−1 всегда может быть заменено с использованием следующего равенства в последовательности, и так до последнего уравнения. Результатом является цепная дробь:

${frac {a}{b}}=q_{0}+{cfrac {1}{q_{1}+{cfrac {1}{q_{2}+{cfrac {1}{ddots +{cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},ldots ,q_{N}]$

В приведённом выше примере НОД(1071, 462) был посчитан и были найдены частные q_k, равные 2, 3 и 7 соответственно. Поэтому 1071/462 может быть записана как:

${frac {1071}{462}}=2+{cfrac {1}{3+{cfrac {1}{7}}}}=[2;3,7]$

Линейные диофантовы уравнения[править | править вики-текст]

Диофантово уравнение — это уравнение с целочисленными коэффициентами и с одним или несколькими переменными, причем ставится задача поиска лишь его целых корней. Такое уравнение может иметь бесконечно много решений, конечное число решений или не иметь их вовсе. Простейшее диофантово уравнение — линейное с двумя неизвестными:

где a, b, c — целые числа. С помощью алгоритма Евклида может быть найдено полное решение уравнения такого типа^[5]. Сначала с помощью этого алгоритма можно определить d = НОД(a, b). Затем, используя расширенный алгоритм Евклида, определяются такие k и l, что:

То есть x = k и y = l — это частное решение уравнения при c = d. Получается, что если c = q⋅d, то x = q⋅k, y = q⋅l — частное решение исходного уравнения, так как:

Обратно, если существует хотя бы одно решение уравнения, то c кратно d. Это следует из того, что d делит и a, и b (а значит, и всю левую часть), поэтому должно делить и c (правую часть). Таким образом, линейное диофантово уравнение имеет хотя бы одно решение тогда и только тогда, когда c кратно НОД(a, b).

Вариации и обобщения[править | править вики-текст]

Евклидово кольцо[править | править вики-текст]

Кольца, в которых применим алгоритм Евклида, называются евклидовыми кольцами^[14]. К ним относятся, в частности, кольца целых чисел и кольца многочленов.

Обобщённый алгоритм Евклида для многочленов[править | править вики-текст]

Алгоритм Евклида и расширенный алгоритм Евклида естественным образом обобщается на кольцо многочленов k[x] от одной переменной над произвольным полем k, поскольку для таких многочленов определена операция деления с остатком. При выполнении алгоритма Евклида для многочленов аналогично алгоритму Евклида для целых чисел получается последовательность полиномиальных остатков (PRS)^[15].

Пример для кольца Z[x]

Пусть cont(f) по определению — НОД коэффициентов многочлена f(x) из Z[x] — содержание многочлена. Частное от деления f(x) на cont(f) называется примитивной частью многочлена f(x) и обозначается primpart(f(x)). Эти определения понадобятся для нахождения НОД двух многочленов p₁(x) и p₂(x) в кольце Z[x]. Для многочленов над целыми числами верно следующее:

cont( НОД ${p_{1}(x),p_{2}(x)})=$ НОД ${cont(p_{1}(x)),cont(p_{2}(x))},$

НОД ${p_{1}(x),p_{2}(x)})=$ НОД ${primpart(p_{1}(x)),primpart(p_{2}(x))}.$

Таким образом, задача поиска НОД двух произвольных многочленов сводится к задаче поиска НОД примитивных полиномов.

Пусть есть два примитивных многочлена p₁(x) и p₂(x) из Z[x], для которых выполняется соотношение между их степенями: deg(p₁(x)) = m и deg(p₂(x)) = n, m > n. Деление многочленов с остатком предполагает точную делимость старшего коэффициента делимого на старший коэффициент делителя, в общем случае деление с остатком выполнить невозможно. Поэтому вводят алгоритм псевдоделения, который всё же позволяет получить псевдочастное и псевдоостаток (prem), которые будут сами по себе принадлежать множеству многочленов над целыми числами.

Под псевдоделением будем понимать, что самому делению предшествует умножение полинома $p_{1}(x)$ на $(lc(p_{2}(x)))^{m-n+1}$ , то есть

$lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),deg(r(x))<deg(p_{2}(x)),$

где q(x) и r(x) — соответственно псевдочастное и псевдоостаток.

Итак, $p_{1}(x),p_{2}(x)in Z[x]$ , причём $deg(p_{1})=n_{1}geq deg(p_{2})=n_{2}$ . Тогда алгоритм Евклида состоит из следующих шагов:

1. Вычисление НОД содержаний:

c:= НОД ${cont(p_{1}),cont(p_{2})}$ .

2. Вычисление примитивных частей:

$p_{1}'(x):=primpart(p_{1}(x));$

$p_{2}'(x):=primpart(p_{2}(x)).$

3. Построение последовательности полиномиальных остатков:

$p_{1}'(x),$

$p_{2}'(x),$

$p_{3}(x):=prem(p_{1}'(x),p_{2}'(x)),$

$p_{4}(x):=prem(p_{2}'(x),p_{3}(x)),$

$p_{5}(x):=prem(p_{3}(x),p_{4}(x)),$

$p_{h}(x):=prem(p_{h-2}(x),p_{h-1}(x)).$

4. Возврат результата:

Если $deg(p_{h}(x))=0$ , то вернуть , иначе вернуть $ccdot primpart(p_{h}(x))$ .

Ускоренные версии алгоритма[править | править вики-текст]

Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка^[16]:

$r_{i}equiv r_{i-2}{pmod {r_{i-1}}},$

где

$-{frac {r_{i-1}}{2}}leq r_{i}leq {frac {r_{i-1}}{2}}.$

Одна из версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии «разделяй и властвуй» позволяет уменьшить асимптотическую сложность алгоритма^[16].

Примечания[править | править вики-текст]

↑ ¹ ² Мордухай-Болтовской, 1949, с. 11—13
↑ ¹ ² ³ Мордухай-Болтовской, 1949, с. 103—105
↑ ¹ ² Кнут, 2001, с. 378
↑ Menezes, 1996, с. 286
↑ ¹ ² Курант, 2001, с. 74—76
↑ ¹ ² Виноградов, 1952, с. 14—18
↑ Энгелер, 1987, с. 24—31
↑ Тихомиров, 2003, с. 11—14
↑ Калужин, 1969, с. 6—14
↑ Цейтен, 1932, с. 112-114
↑ Виноградов, 1952, с. 9-10
↑ Курант, 2001, с. 67-70
↑ Хассе, 1953, с. 29-30
↑ Курош, 1973, с. 91-92
↑ Панкратьев, 2007, с. 54-58
↑ ¹ ² Gathen, 2013, с. 313-326

Литература[править | править вики-текст]

Начала Евклида / пер.с греч. и комм. Д. Д. Мордухая-Болтовского под ред. Выгодского М. Я. и Веселовского И. Н.. — ГИТТЛ, 1949. — Т. 2. — 511 с.
Виноградов И. М. Основы теории чисел. — М.-Л.: ГИТТЛ, 1952. — 180 с. — ISBN 978-5-811-40535-0.
Курант Р., Роббинс Г. Дополнение к главе I, § 4. // Что такое математика? — 3-e изд., испр. и доп. — М., 2001. — 568 с. — ISBN 5-900916-45-6.
Абрамов С. Самый знаменитый алгоритм // Квант. — 1985. — № 11. — С. 44—46.
Кнут Д. Э. Искусство программирования. — Вильямс, 2001. — Т. 2. — 829 с. — ISBN 5-8459-0081-6.
Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 с. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7.
von zur Gathen J., Gerhard J. Modern Computer Algebra. — Cambridge University Press, 2013. — 808 с. — ISBN 978-1-107-03903-2.
Панкратьев Е. В. Элементы компьютерной алгебры. — ИНТУИТ, 2007. — 217 с. — ISBN 978-5-955-60099-4.
Тихомиров В. М. Великие математики прошлого и их великие теоремы. — 2-е изд., испр. — МЦНМО, 2003. — 16 с. — ISBN 5-94057-110-7.
Калужин Л. А. Основная теорема арифметики. — Популярные лекции по математике. — М.: Наука, 1969. — 33 с.
Хассе Г. Лекции по теории чисел. — Изд. иностранной литературы, 1953. — 527 с.
Энгелер Э. Метаматематика элементарной математики. — М.: Мир, 1987. — 128 с.
Цейтен Г. Г. История математики в Древности и в Средние века. — ГТТИ, 1932. — 232 с.
Курош А. Г. Лекции по общей алгебре. — М.: Наука, 1973. — 400 с.

Ссылки[править | править вики-текст]

Описание метода и коды программ алгоритма Евклида.
Обоснование алгоритма Евклида
Алгоритм Евклида на e-maxx.ru
C# реализация расширенного алгоритма Эвклида

Источник

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

Дробно-рациональные функции

Наибольший общий делитель (НОД) двух многочленов

Проблема взрывного роста коэффициентов остатков

Алгоритм Евклида — нахождение наибольшего общего делителя

Алгоритм нахождения НОД делением

Алгоритм нахождения НОД вычитанием

Функция, вычисляющая НОД

Функция gcd модуля math

Содержание

История[править | править вики-текст]

Описание[править | править вики-текст]

Алгоритм Евклида для целых чисел[править | править вики-текст]

Геометрический алгоритм Евклида[править | править вики-текст]

Пример[править | править вики-текст]

Применения[править | править вики-текст]

Расширенный алгоритм Евклида и соотношение Безу[править | править вики-текст]

Цепные дроби[править | править вики-текст]

Линейные диофантовы уравнения[править | править вики-текст]

Вариации и обобщения[править | править вики-текст]

Евклидово кольцо[править | править вики-текст]

Обобщённый алгоритм Евклида для многочленов[править | править вики-текст]

Ускоренные версии алгоритма[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]

Функция `gcd` модуля `math`