Алгоритм Евклида

Алгоритм Евклида — это эффективный алгоритм для нахождения НОД. Для натуральных чисел, таких как $9$ и $6,$ достаточно было просто перебирать числа для нахождения НОД. Если же перебирать числа для более сложных примеров, как, например, $52152$ и $9875,$ то процесс нахождение НОД будет слишком долгим. Поэтому, вместо того чтобы перебирать числа, можно просто выполнить ряд простых действий.

Определение. Даны числа $A, B \in \mathbb{Z}^{+},$ где $A \geqslant B$ и $r_{k}, q_{k} \in \mathbb{Z}^{+},$ при $k = 1,2,3…n,$ где $r_k$ — остаток, а $q_{k}$ — частное. Находим ряд равенств: $$A = Bq_{1} + r_{1}$$ $$B = r_{1}q_{2}+r_2$$ $$r_{1} = r_{2}q_{3}+r_{3}$$ $$……$$ $$r_{n-1} = r_{n}q_{n+1}+0,$$ где $r_{n}$ и будет НОД целых чисел $A$ и $B$. Все ранее написанное и называется алгоритмом Евклида.

Другими словами, мы представляем деление $A$ на $B,$ как $A = Bq + r$ и пока остаток $r \neq 0$ мы делим делитель на остаток от деления. А так как остаток всегда меньше делителя двух целых чисел ($r_{1} < B$ или $r_{n} < r_{n-1}$), то рано или поздно остаток будет равен нулю. А НОД двух чисел будет последний делитель.

Выполним те же действия, но на этот раз запишем деление в столбик.


Спойлер

Евклид не открывал этот алгоритм. Этот алгоритм был придуман Аристотелем. Евклид лишь описал этот алгоритм в двух книгах «Начал», а конкретно в VII и X книгах. В первой он описал алгоритм как нахождение НОД двух натуральных чисел, а во второй как нахождение общей меры.

[свернуть]

НОД двух многочленов

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

Теорема. Наибольший общий делитель двух многочленов существует.

Пусть даны два многочлена $f\left(x\right), g\left(x\right) \in P[x],$ где $\deg \left(f\left(x\right)\right) \geqslant \deg \left(g\left(x\right)\right)$. Находим ряд равенств: $$f\left(x\right) = g\left(x\right)q_1\left(x\right)+r_1\left(x\right)$$ $$g\left(x\right) = r_{1}\left(x\right)q_{2}\left(x\right)+r_{2}\left(x\right)$$ $$r_{1}\left(x\right) = r_{2}\left(x\right)q_{3}\left(x\right)+r_{3}\left(x\right)$$ $$……$$ $$r_{n-1}\left(x\right) = r_{n}\left(x\right)q_{n+1}\left(x\right)+0,$$ где $r_{k}, q_{k} \in P[x]$ при $k = 1,2,3,…,n,$ где $r_{k}$ — остаток, а $q_{k}$ — частное. В случае с целыми числами, остатки в алгоритме убывают, при многочленах же убывают степени остатка ($\deg \left(r_{n}\left(x\right)\right) < \deg \left(r_{n-1}\left(x\right)\right) < \deg \left(r_{n-2}\left(x\right)\right) < …$), это означает, что наступит момент деления без остатка. Поэтому НОД двух многочленов, по алгоритму Евклида, будет последний отличный от нуля остаток(в нашем случае $r_{n}$).

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

Запишем тот же алгоритм делением в столбик.

Примеры решения задач

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

  1. Найти НОД $784$ и $552$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$784 = 552 \times 1 + 232$$ $$552 = 232 \times 2 + 88$$ $$232 = 88 \times 2 + 56$$ $$88 = 56 \times 1 + 32$$ $$56 = 32 \times 1 + 24$$ $$32 = 24 \times 1 + 8$$ $$24 = 8 \times 3 + 0,$$ где число $8$ — НОД $784$ и $552,$ так как это последний делитель.

  2. Найти НОД $868$ и $923$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$923 = 868 \times 1 + 55$$ $$868 = 55 \times 15 + 43$$ $$55 = 43 \times 1 + 12$$ $$43 = 12 \times 3 + 7$$ $$12 = 7 \times 1 + 5$$ $$12 = 7 \times 1 + 5$$ $$7 = 5 \times 1 + 2$$ $$5 = 2 \times 2 + 1$$ $$2 = 1 \times 2 + 0,$$ где число $1$ — НОД $868$ и $923,$ так как это последний делитель.

  3. Найти НОД $52800$ и $54108$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$54108 = 52800 \times 1 + 1308$$ $$52800 = 1308 \times 480 + 480$$ $$1308 = 480 \times 2 + 348$$ $$480 = 348 \times 1 + 132$$ $$348 = 132 \times 2 + 84$$ $$132 = 84 \times 1 + 48$$ $$84 = 48 \times 1 + 36$$ $$48 = 36 \times 1 + 12$$ $$36 = 12 \times 3 + 0,$$ где $12$ — НОД $52800$ и $54108$.

  4. Найти НОД $x^5-10x^3-20x^2-15x-4$ и $x^4-6x^2-8x-3$ используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: $$x^5-10x^3-20x^2-15x-4 = x\left(x^4-6x^2-8x-3\right) — 4x^3-12x^2-12x-4$$ $$x^4-6x^2-8x-3 = \left(- 4x^3-12x^2-12x-4\right)\left(- \frac{x}{4}\right) — 3x^3-9x^2x-9x-3$$ $$- 4x^3-12x^2-12x-4 =\left(-3x^3-9x^2x^2-9x-3\right)\left(-\frac{4}{3}\right) + 0,$$ где $3x^3-9x^2-9x-3$ — НОД многочленов $x^5-10x^3-20x^2-15x-4$ и $x^4-6x^2-8x-3,$ так как это последний делитель в алгоритме.

Проверка на освоение материала «Алгоритм Евклида».

Смотрите также

  1. Конспект Г.С.Белозерова. Глава 3 — 15с. — С. 3-5.
  2. Д.К. Фаддеев. Лекции по алгебре: Учебное пособие для вузов. — М.: Наука, 1984. — 416 с. — С. 7-11.
  3. И.М. Виноградов. Основы теории чисел. — Москва, 1952. — 181 с. — С. 8-12.

Алгоритм Евклида: 2 комментария

  1. — «достаточно было просто подставить числа» куда подставить?
    — «полученный ответ может оказаться неправильным» как полученный? почему неправильным? Хоть намекните, о чем Вы пишите?
    — «можем расписать как ряд равенств» Что именно мы можем расписать как ряд?
    — «перечисленные действия» но там нет действий! Вообще нет глаголов кроме «распишем».
    — «буду записывать двумя способами» После этих слов у Вас одно деление столбиком. О чем Вы? Какие два способа и где?
    — «Набольший»
    — И опять непонятно что расписывается КАК ряд равенств. Языковая схема подразумевает наличие двух объектов: X как Y. У вас только Y.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *