Алгоритм Евклида и линейное представление НОД – CODE BLOG

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

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

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

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

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

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

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

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

img-i0GHA9.pngimg-kVNELA.pngimg-z3UxJD.pngimg-3FvB6O.pngimg-hc4Zr9.png

img-lTbDUn.pngimg-F3wJlh.pngimg-I2mbGN.png

img-XP08zK.pngimg-Sqy3Ao.png

img-jn8Hvf.pngimg-fbeJtM.png

img-g8X9Eu.pngimg-uvRzGQ.png

img-wd1okr.png

img-uCvJpH.pngimg-TrxG_J.png

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

img-R80wsx.png=img-VziWYV.png. Получившаяся в результате дробьimg-vsEpDj.pngявляется правильной.

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

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

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

  1. img-FKORHU.png.

  2. img-UZJW2W.png.

  3. img-ESq6s4.png.

  4. img-DXGHkc.png.

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

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

  1. Если дробь – неправильная, то выделяем целую часть, а на простейшие раскладываем получившуюся правильную дробь.

  2. Раскладываем знаменатель правильной дроби на множители.

  3. Записываем правильную дробь в виде суммы простейших дробей с неопределенными коэффициентами.

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

  5. Находим неопределенные коэффициенты:

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

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

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

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

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

img-k4rmcj.pngimg-nlcXdE.pngimg-809mAG.pngimg-Djwa1I.pngimg-IPiPLz.png

img-treEDI.png1

img-cNGmO3.pngimg-KQa1pC.png

img-6GPJSK.png= 1 +img-CE3nW9.png.

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

img-kB0S_E.png.

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

img-sZzrSI.png.

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

img-bg0nGr.png.

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

img-d65d7Z.png

Ответ: img-LFyKbS.png.

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

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

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

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

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

При х = 1:

img-vIR1z5.png,

img-KKgrcG.pngПрих= ‑1:

img-uMqEH8.png

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

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

img-wB4MvI.pngОтвет:img-XOCBmT.png.

Общие сведения

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

Основные соотношения алгоритма Евклида

Суть алгоритма заключается в формировании новой пары чисел из меньшего и разницы между большим и меньшим элементом. Процесс, состоящий из арифметических операций, повторяется до тех пор, пока числа не будут равны друг другу. Первоначально инструкция создавалась для натуральных чисел и геометрических величин. Однако в XIX веке ее расширили и стали применять для других объектов: целых чисел Гаусса и многочленов с одной переменной (полиномов). Направление, получившееся в математике, специалисты стали называть евклидовым кольцом. Позднее его доработали и стали применять для узлов и многомерных полиномов.

Алгоритм является основой для криптографического шифрования с открытым ключом, который распространен в электронной коммерции для защиты программных продуктов от злоумышленников. Его применяют для решения уравнений Диофанта, построения дробей непрерывного типа, доказательств утверждений (основная теорема арифметики и теорема Лагранжа о сумме 4 квадратов).

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

Алгоритм Евклида позволяет с легкостью вычислить наибольший общий делитель для двух положительных чисел. Формулировки и доказательство алгоритма Евклида мы привели в разделе «Наибольший общий делитель: определитель, примеры».

Суть алгоритма заключается в том, чтобы последовательно проводить деление с остатком, в ходе которого получается ряд равенств вида:

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Мы можем закончить деление тогда, когда rk+1=0, при этом rk=НОД(a, b).

Пример 1

Найдите наибольший общий делитель чисел 64 и 48.

Решение

Введем обозначения: a=64, b=48.

На основе алгоритма Евклида проведем деление 64 на 48.

Получим 1 и остаток 16. Получается, что q1=1, r1=16.

Вторым шагом разделим 48 на 16, получим 3. То есть q2=3, а r2=0. Таким образом число 16 – это наибольший общий делитель для чисел из условия.

Ответ: НОД(64, 48)=16.

Пример 2

Чему равен НОД чисел 111 и 432?

Решение

Делим 432 на 111. Согласно алгоритму Евклида получаем цепочку равенств 432=111·3+99, 111=99·1+12, 99=12·8+3, 12=3·4.

Таким образом, наибольший общий делитель чисел 111 и 432 – это 3.

Ответ: НОД(111, 432)=3.

Пример 3

Найдите наибольший общий делитель чисел 661 и 113.

Решение

Проведем последовательно деление чисел и получим НОД(661, 113)=1. Это значит, что 661 и 113 – это взаимно простые числа. Мы могли выяснить это до начала вычислений, если бы обратились к таблице простых чисел.

Ответ: НОД(661, 113)=1.

Понятие наибольшего общего делителя

Начнем с самого начала и вспомним, что такое общий делитель. У целого числа может быть несколько делителей. А сейчас нам особенно интересно, как обращаться с делителями сразу нескольких целых чисел.

Делитель натурального числа — это такое натуральное число, которое делит данное число без остатка. Если у натурального числа больше двух делителей, его называют составным.

Общий делитель нескольких целых чисел — это такое число, которое может быть делителем каждого числа из указанного множества. Например, у чисел 12 и 8 общим делителем будет четверка. Чтобы это проверить, напишем верные равенства: 8 = 4 * 2 и 12 = 3 * 4. Но у этой пары чисел есть и другие общие делители: 1, -1 и -4.

Любое число можно разделить на 1, -1 и на само себя. Значит у любого набора целых чисел будет как минимум три общих делителя. Если общий делитель больше 0 — противоположное ему значение со знаком минус также является общим делителем.

Если b — делитель целого числа a, которое не равно нулю, то модуль числа b не может быть больше модуля числа a. Значит любое число, не равное 0, имеет конечное число делителей.

Разобраться во всех правилах и быстро щелкать задачки помогут внимательные учителя детской школы Skysmart. Вместо скучных параграфов ребенка ждут интерактивные упражнения с мгновенной автоматической проверкой, увлекательные математические комиксы и даже онлайн-доска, на которой можно чертить вместе с учителем.

Запишите вашего ребенка на бесплатный вводный урок математики: покажем, как все устроено и вдохновим на учебу.

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

Например, для 4 и -16 НОД будет 4. Как мы к этому пришли:

  1. Зафиксируем все делители четырех: ±4, ±2, ±1.
  2. А теперь все делители шестнадцати: ±16, ±8, ±4, ±3 и ±1.
  3. Выбираем общие: это -4, -2, -1, 1, 2 и 4. Самое большое общее число: 4. Вот и ответ.

Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.

Найдем наибольший общий делитель нескольких целых чисел: 10, 6, 44, -18. Он будет равен трем. Ответ можно записать так: НОД (12, 6, 42, -18) = 3. А чтобы проверить правильность ответа, нужно записать все делители и выбрать из них самые большие.

Взаимно простые числа — это натуральные числа, у которых только один общий делитель — единица. Их НОД равен 1.

Помимо НОД есть еще и НОК, что расшифровывается, как наименьшее общее кратное и означает наименьшее число, которое делится на каждое из исходных чисел без остатка.

Еще один пример. Рассчитаем НОД для 28 и 64.

Как находим:

  1. Распишем простые множители для каждого числа и подчеркнем одинаковые

    Д (28) = 2 * 2 * 7

    Д (64) = 2 * 2 * 2 * 2 * 2 * 2

  2. Найдем произведение одинаковых простых множителей и запишем ответ

    НОД (28; 64) = 2 * 2 = 4

Ответ: НОД (28; 64) = 4

Оформить поиск НОД можно в строчку, как мы сделали выше или в столбик, как на картинке.

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

Наибольший общий делитель многочленов. Дайте многочлен P (x). Всех многочленов, кратных полинома P (х)) Где r (x) также является многочленом, называемым делителем многочлена P(x). Мы обнаружили, что многочлен P (x) можно описать как: Где а…, a, является действительным числом многочленов, и коэффициенты вида x2 + p, x + 7 /соответствуют по своей сути комплексным корням этого многочлена. Коэффициенты A, p, -, и 7. (/ = 1, 2,…, Д) является valid. It следует Действительно, нет никаких других факторов в виде Где A, p и 7 действительны и-4-7.Так как о в факторизации многочлена H (x) является многочленом H (x), то можно факторизовать как (23.15), так и в других многочленах, если факторизация выражения h (x) содержит фактор x-a вида x2 + px + y соответственно, то корень члена x = i также является многочленом p (x) 3-го члена X2 + таким образом, указанные факторы входят в разложение(23.12).

Общие делители 2 полиномов, которые делятся на общие делители этих полиномов, называются наибольшими делителями. Людмила Фирмаль

  • Неравенство (23.14)также очевидно. Из той же формулы (23.11) следует, что кратность корней многочлена H (x) не может превышать кратности тех же корней многочлена P (x). Затем укажите 2 полинома P (x) и SCx).Все полиномы, которые являются делителями обоих полиномов P (x) и 多項式 (x), называются общими делителями. Многочлен P(.если (x) и 0(x) записываются в виде (23.12). Тогда все эти общие делители H (x) можно записать в виде (23.13). Для расширений (23.16) и расширений(23.17). Если индексы коэффициентов разложения (23.16) и (23.17) коэффициентов (23.18) равны соответственно/ / и th,//, то неравенство (23.14).

Для того чтобы полином (23.13) стал наибольшим общим коэффициентом полиномов P (x) и C (x), показатели K = 1, 2,…, r и p;, / = 1, 2 является необходимым и достаточным. и…, 5 является максимально возможным, то есть Фактически, при этих условиях полиномы P (x) являются полиномами P (x) и C?(X) будет общим делителем, и далее условие (23.19) будет разделено на любой многочлен вида (23.13), который будет удовлетворен. P (x) делится на общий делитель многочлена P (x). Из формы общих найденных делителей, особенно самых больших делителей, мы сначала видим, что самые большие делители 2 полиномов не уникальны. Однако 2 из 2 наибольших общих делителей данного многочлена могут отличаться только постоянным коэффициентом (константой B в Формуле (23.13) можно считать любое значение, отличное от нуля).

  • Во-вторых, наибольший общий делитель 2 полиномов имеет степень, большую, чем любой из этих общих делителей, который не является наибольшим общим делителем. В качестве примера, который поможет вам ниже, найдите наибольший общий делитель многочлена P (x) и его производную P ’(x). Во-первых, если число a является действительным корнем кратности a многочлена P (x), то есть, a-корень кратности a-1 многочлена P ’(x). фактически дифференцирование (23.21)、 Точно так же Где r4—7 0, отсюда три члена x2 + px + 7 r4 и r2 (22 = 2!) Корни по своей сути сложны、 Действительно, дифференцировать(23.22). Из вышеизложенного следует, что если многочлен P (x) описывается в виде (23.12), то его производная P ’(x) может быть представлена в следующем виде: Где многочлен P5 (x) равен x-a、-、1 = 1、2、… даже в r, x2 + p / X-1-7 /но она не делима. / = 1, 2,…5, то есть, нет общего корня многочлена P (х).

Из формул(23.13)и(23.20) полином P (x) и его производная P ’(x) имеют наибольший общий делитель P (x) Приведенный выше метод получения наибольших общих делителей 2 полиномов P (x) и^(x) радикально и полностью решает проблему существования и формы наибольших общих делителей. difficulties. To используйте этот метод, вам нужно использовать данные многочлены P (x) и C? вам нужно знать факторизацию (x) формы (23.16) и (23.17). Однако 2 многочлена P (x) и? Существует еще один способ получить наибольший общий делитель (X), обычно называемый евклидовым алгоритмом. *Описать его. Чтобы быть ясным, степень многочлена P (x) больше или равна степени многочлена φ (x). Разделить P(x) на 2 (x).

Однако его практическое применение может вызвать серьезные проблемы. Людмила Фирмаль

  • Получим некоторые многочлены 3 (x) и остаток Px (x) в виде частных. Его степень явно меньше степени многочлена 2 (x) (в противном случае можно продолжить процесс деления на ($(x))). Из этого выражения следует следующее: 1) Если многочлены P (x) и 2 (x) делятся на некоторые многочлены r (x), то многочлены Px (x) также делятся на этот многочлен. 2) Если многочлены 2 (x) и RL (x) делятся на один многочлен r (x), то многочлены P (x) также делятся на этот многочлен r (x).Это означает, что общие делители полиномов P (x) и 2 (x), в частности, их наибольшие общие делители, будут совпадать.

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

Предмет математический анализ

Описание и доказательство алгоритма

Для целых чисел алгоритм состоит из соотношений, количество которых равно числу элементов. Если предположить, что а и b являются целыми и неравными нулю значениями, то для них выполняется соотношение a > b > R1 > … > Rn. Величинами R с определенными индексами являются остатки от деления а на некоторое значение Q1 и b на Q2. Описывается процесс такими формулами:

  1. а = b * q0 + R1.
  2. b = R1 * q1 + R2.
  3. R1 = R2 * Q2 + R3.
  4. Rn-1 = Rn * Qn.

На последнем этапе не должно быть остатка. Для отрезков применяется геометрический алгоритм. Чтобы найти наибольший общий отрезок, нужно из большего вычесть меньший, а затем заменить первый их разностью. Операцию следует завершить при равенстве двух отрезков. Реализуется данный алгоритм при помощи циркуля и линейки. Для доказательства алгоритма Евклида следует взять пару чисел f и g, для которых можно привести такие утверждения:

Применение в дисциплинах с математическим уклоном
  1. Делители f и g — общие делители (f — g) и g.
  2. Делители (f — g) и g — общие делители f и g.
  3. Когда f > g, тогда НОД (f, g) = НОД (f — g, g).
  4. НОД (f, 0) = f.

Для доказательства следует ввести новую переменную z. Она является общим делителем для f и g. Кроме того, разность f — g также делится на z. Из предположения f = z * k и g = z * s следует, что f — g = z * k — z * s = z * (k — s). Иными словами, z — общий множитель для f — g. Из соотношения можно доказать, что z делит не только разность, но и сумму: f — g + g = f. Следовательно, z — общий делитель для f и g.

На основании полученных вычислений можно сделать вывод, что z для f и g совпадает с (f — g) и g. Если одно из чисел имеет нулевое значение, то НОД равен другому числу, поскольку 0 делится на любое число.

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

Свойства наибольшего общего делителя

У наибольшего общего делителя есть ряд определенных свойств. Опишем их в виде теорем и сразу приведем доказательства.

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

Свойство 1. Наибольший общий делитель чисел а и b равен наибольшему общему делителю чисел b и а, то есть НОД (a, b) = НОД (b, a). Перемена мест чисел не влияет на конечный результат.

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

Свойство 2. Если а делится на b, то множество общих делителей чисел а и b совпадает со множеством делителей числа b, поэтому НОД (a, b) = b.

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

 

Любой общий делитель чисел а и b является делителем каждого из этих чисел, в том числе и числа b. Так как а кратно b, то любой делитель числа b является делителем и числа а, благодаря свойствам делимости. Из этого следует, что любой делитель числа b является общим делителем чисел а и b.

 

Значит, если а делится на b, то совокупность делителей чисел а и b совпадает с совокупностью делителей одного числа b. А так как наибольшим делителем числа b является само число b, то наибольший общий делитель чисела и b также равен b, то есть НОД (а, b) = b.

 

В частности, если a = b, то НОД (a, b) = НОД (a, a) = НОД (b, b) = a = b.

  • Например, НОД (25, 25) = 25.

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

  • Например, НОД (4, 40) = 4, так как 40 кратно 4.

Свойство 3. Если a = bq + c, где а, b, с и q — целые числа, то множество общих делителей чисел а и b совпадает со множеством общих делителей чисел b и с. Равенство НОД (a, b) = НОД (b, c) справедливо.

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

 

Существует равенство a = bq + c, значит всякий общий делитель чисел а и b делит также и с, исходя из свойств делимости. По этой же причине, всякий общий делитель чисел b и с делит а. Поэтому совокупность общих делителей чисел а и b совпадает с совокупностью общих делителей чисел b и c.

 

Поэтому должны совпадать и наибольшие из этих общих делителей, и равенство НОД (a, b) = НОД (b, c) можно считать справедливым.

Свойство 4. Если m — любое натуральное число, то НОД (mа, mb) = m * НОД(а, b).

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

Если умножить на m обе стороны каждого из равенств алгоритма Евклида, то получим, что НОД (mа, mb)= mr, где r — это НОД (а, b). На этом свойстве наибольшего общего делителя основан поиск НОД с помощью разложения на простые множители.

Свойство 5. Пусть р — любой общий делитель чисел а и b, тогда НОД (а : p, b : p) = НОД (а, b) : p. А именно, если p = НОД (a, b) имеем НОД (a : НОД (a, b), b: НОД (a, b)) = 1, то есть, числа a : НОД (a, b) и b : НОД (a, b) — взаимно простые.

Так как a = p(a : p) и b = p(b : p), и в силу предыдущего свойства, мы можем записать цепочку равенств вида НОД (a, b) = НОД (p(a : p), p(b : p)) = p * НОД (a : p, b : p), откуда и следует доказываемое равенство.

Пример решения

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

Пример решения задачи
  • Выполнить операцию разности до получения остатка: 1071 — 462 — 462 + 147 = 1071 — 2 * 462 + 147 (Q0 = 2, R0 = 147).
  • От 462 отнять 147 до получения результата, который меньше 147: 462 — 147 — 147 — 147 + 21 = 462 — 3 * 147 + 21 (Q1 = 3, R1 = 21).
  • Анализ пары чисел 147 и 21: 147 — 21 — 21 — 21 — 21 — 21 — 21 — 21 + 0 (Q2 = 7, R2 = 0).
  • Определение результата: НОД (1071,462) = 21.

На третьем шаге алгоритм заканчивается, поскольку остаток отсутствует, т. е. R2 = 0. В написании программ применяется такой же принцип. Если даны три числа, то методика решения усложняется. Для этой цели применяется специальный онлайн-калькулятор.

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

Рейтинг
( 1 оценка, среднее 5 из 5 )
Загрузка ...