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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Алгоритм ЕвклидаРассмотрим задачу поиска наибольшего общего делителя g для двух натуральных чисел a и b.Алгоритм Евклида для решения этой задачи основан на наблюдении, что d – общий делитель чисел(a, b) тогда и только тогда, когда d – общий делитель чисел (a − b, b). Действительно, пусть d –общий делитель (a, b). Следовательно, a = dn, b = dm для некоторых целых n, m и a − b = d(n − m).Значит, d – общий делитель для (a − b, b). В обратную сторону доказательство аналогично. Такимобразом, переход от пары чисел (a, b) к паре (a − b, b) сохраняет множество общих делителей, аследовательно, и наибольший общий делитель.

Применяя этот переход несколько раз, получаем,что пара (a − kb, b), где k – некоторое натуральное число, имеет те же общие делители, что и пара(a, b).Пусть, не ограничивая общности, a > b. Поделим a на b с остатком, т.е. найдем q, r : a =qb + r, 0 ≤ r < b. Теперь можно перейти от пары (a, b) к паре (b, a − qb) = (b, r) с сохранениеммножества общих делителей. Далее этот процесс можно повторить, переходя от пары (b, r) к паре (r, r2 ), где b = q2 r + r2 . При каждом таком переходе числа в паре уменьшаются, но остаютсянеотрицательными.

Следовательно, за конечное число шагов образуется пара вида (rn , 0), для которой наибольший общий делитель g = rn . В результате общая схема алгоритма Евклида выглядитследующим образом:r−2 = a,r−1 = b,r−2 = r−1 q0 + r0 , r0 < r−1 , // Делим r−2 на r−1 с остаткомr−1 = r0 q1 + r1 , r1 < r0 , // Делим r−1 на r0 с остатком(1)...rn−2 = rn−1 qn + rn , // Делим rn−2 на rn−1 с остаткомrn−1 = rn qn+1 .Наибольший общий делитель g = rn .Пример. Найдём g = НОД(252, 105). Применяя схему (1), получаем:252 = 105 · 2 + 42,105 = 42 · 2 + 21,42 = 21 · 2.Отсюда g = 21.Для поиска наибольшего общего делителя трех и более чисел можно воспользоваться свойствомНОД(a, b, c) = НОД(a, НОД(b, c))и запускать алгоритм Евклида несколько раз.

Для поиска наименьшего общего кратного двух чиселможно воспользоваться свойствомНОК(a, b)НОД(a, b) = ab.Для g = НОД(a, b) справедлива теорема Безу: найдутся x, y ∈ Z такие, что g = ax + by. Этоутверждение легко доказать, «раскручивая» схему (1) в обратную сторону. Действительно, g =rn = rn−2 − rn−1 qn . Подставляя в это равенство значение rn−1 = rn−3 − rn−2 qn−1 , получаем, что g =−qn rn−3 + (1 + qn qn−1 )rn−2 = αrn−3 + βrn−2 для некоторых α, β ∈ Z. Продолжая эти рассуждения,получим утверждение теоремы. Модификация схемы (1), позволяющая вместе с наибольшим общимделителем найти числа x, y из теоремы Безу, получила название расширенного алгоритма Евклида.1Будем искать xi , yi ∈ Z, для которых справедливо ri = axi + byi , где ri , i = −2, .

. . , n – остаткииз алгоритма Евклида (1). Для i = −2, −1 решение записывается какx−2 = 1, x−1 = 0,y−2 = 0, y−1 = 1.Пусть верно ri−2 = axi−2 + byi−2 , ri−1 = axi−1 + byi−1 . Тогда найдем xi , yi :ri = ri−2 − qi ri−1 = (axi−2 + byi−2 ) − qi (axi−1 + byi−1 ) = a(xi−2 − qi xi−1 ) + b(yi−2 − qi yi−1 ) = axi + byi .Следовательно, xi = xi−2 − qi xi−1 , yi = yi−2 − qi yi−1 . В итоге расширенный алгоритм Евклидаповторяет схему (1), в которой на каждом шаге дополнительно вычисляются xi , yi по приведённымформулам.Пример.

Расширим предыдущий пример и найдем g, x, y ∈ Z : g = 252x + 105y. Сведём всевычисления в таблицу:i-2-1012ri−2ri−1qi252105421054221222ri25210542210xi101-25yi01-25-12Таким образом, g = 21, x = −2, y = 5.Алгоритм Евклида (а также его расширенная версия) может быть применен не только дляслучая целых чисел. Он остаётся справедливым в любом евклидовом кольце R, т.е. таком целостномкольце, в котором для любых двух ненулевых элементов возможна процедура деления с остатком,причём норма остатка меньше нормы делителя:∀a, b ∈ R, b 6= 0 a = bq + r, 0 ≤ norm(r) < norm(b).Примером евклидова кольца является кольцо многочленов F [x] над произвольным полем F , где вкачестве нормы выступает степень многочлена.С помощью расширенного алгоритма Евклида легко находить обратные элементы в конечныхполях.

Пусть имеется поле Fnp = Fp [x]/(f (x)), где f (x) – неприводимый полином степени n над Fp .Тогда обратный элемент h для некоторого многочлена g из поля Fnp определяется условием:g(x)h(x) ≡ 1mod f (x).Данное уравнение эквивалентно следующемуf (x)a(x) + g(x)h(x) = 1.Оно может быть решено путем применения расширенного алгоритма Евклида для пары многочленов (f, g). Заметим, что решение данного уравнения всегда существует, т.к. f – неприводимыйполином, степень g всегда меньше, чем степень f , и поэтому НОД(f, g) = 1.Пример. Найдём обратный элемент для x2 + x + 3 в поле F7 [x]/(x4 + x3 + x2 + 3).

Для этогорешим уравнение(x4 + x3 + x2 + 3)a(x) + (x2 + x + 3)b(x) = 1(2)с помощью расширенного алгоритма Евклида:Шаг 0. r−2 (x) = x4 + x3 + x2 + 3,r−1 (x) = x2 + x + 3,y−2 (x) = 0,y−1 (x) = 1.Шаг 1. r−2 (x) = r−1 (x)q0 (x) + r0 (x),q0 (x) = x2 + 5,r0 (x) = 2x + 2,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = −x2 − 5.Шаг 2. r−1 (x) = r0 (x)q1 (x) + r1 (x),q1 (x) = 4x,r1 (x) = 3,y1 (x) = y−1 (x) − y0 (x)q1 (x) = 1 + 4x(x2 + 5) = 4x3 + 6x + 1.Заметим, что в итерациях алгоритма нет необходимости вычислять xi (x), т.е. коэффициент приx4 + x3 + x2 + 3, т.к. нас интересует только коэффициент при x2 + x + 3, т.е.

yi (x). Алгоритмзаканчивает свою работу на шаге 2, т.к. степень очередного остатка r1 равна степени многочленав правой части (2). Однако, сам остаток r1 отличается от требуемого на константный множитель.Действительно, после шага 2 мы имеем(x4 + x3 + x2 + 3)x1 (x) + (x2 + x + 3)y1 (x) = 3.Чтобы получить решение уравнения (2), достаточно домножить последний результат на 3−1 = 5:h(x) = 5y1 (x) = 5(4x3 + 6x + 1) = 6x3 + 2x + 5.Если на последнем шаге алгоритма Евклида текущий остаток не является требуемым с точностью до константного множителя, то соответствующее уравнение не имеет решения.Расширенный алгоритм Евклида также активно применяется для декодирования БЧХ кодов..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы