Loading [MathJax]/jax/output/SVG/jax.js

Метка: НОД целых чисел

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

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

Определение. Даны числа A,B∈Z+, где A⩾B и rk,qk∈Z+, при k=1,2,3…n, где rk — остаток, а qk — частное. Находим ряд равенств: A=Bq1+r1 B=r1q2+r2 r1=r2q3+r3 …… rn−1=rnqn+1+0, где rn и будет НОД целых чисел A и B. Все ранее написанное и называется алгоритмом Евклида.

Другими словами, мы представляем деление A на B, как A=Bq+r и пока остаток r≠0 мы делим делитель на остаток от деления. А так как остаток всегда меньше делителя двух целых чисел (r1<B или rn<rn−1), то рано или поздно остаток будет равен нулю. А НОД двух чисел будет последний делитель.

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


Спойлер

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

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

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

Пусть даны два многочлена f(x),g(x)∈P[x], где deg(f(x))⩾deg(g(x)). Находим ряд равенств: f(x)=g(x)q1(x)+r1(x) g(x)=r1(x)q2(x)+r2(x) r1(x)=r2(x)q3(x)+r3(x) …… rn−1(x)=rn(x)qn+1(x)+0, где rk,qk∈P[x] при k=1,2,3,…,n, где rk — остаток, а qk — частное. В случае с целыми числами, остатки в алгоритме убывают, при многочленах же убывают степени остатка (deg(rn(x))<deg(rn−1(x))<deg(rn−2(x))<…), это означает, что наступит момент деления без остатка. Поэтому НОД двух многочленов, по алгоритму Евклида, будет последний отличный от нуля остаток(в нашем случае rn).

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

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

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

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

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

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

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

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

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

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

  4. Найти НОД x5−10x3−20x2−15x−4 и x4−6x2−8x−3 используя алгоритм Евклида.
    Решение

    Для лучшего понимания распишу два деления. Одно в столбик, другое — по определению. Деление в столбик: Деление по определению: x5−10x3−20x2−15x−4=x(x4−6x2−8x−3)—4x3−12x2−12x−4 x4−6x2−8x−3=(−4x3−12x2−12x−4)(−x4)—3x3−9x2x−9x−3 −4x3−12x2−12x−4=(−3x3−9x2x2−9x−3)(−43)+0, где 3x3−9x2−9x−3 — НОД многочленов x5−10x3−20x2−15x−4 и x4−6x2−8x−3, так как это последний делитель в алгоритме.

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

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

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