Skip to main content
LibreTexts - Ukrayinska

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

  1. Last updated
  2. Save as PDF
  • Page ID
    64710

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    У цьому розділі ми опишемо систематичний метод, який визначає найбільший спільний дільник двох цілих чисел. Цей метод називається евклідовим алгоритмом.

    [lem1] Якщо\(a\) і\(b\) є двома цілими числами, а\(a=bq+r\) де також\(q\) і\(r\) є цілими числами, то\((a,b)=(r,b)\).

    Зауважимо, що за теоремою 8 ми маємо\((bq+r,b)=(b,r)\).

    Вищеописана лема призведе до більш загальної її версії. Наведемо алгоритм Евкліда в загальному вигляді. Він стверджує, що найбільшим спільним дільником двох цілих чисел є останній ненульовий залишок послідовного ділення.

    \(a=r_0\)\(b=r_1\)Дозволяти і бути два натуральних числа де\(a\geq b\). Якщо ми застосуємо алгоритм поділу послідовно, щоб отримати, що\[r_j=r_{j+1}q_{j+1}+r_{j+2} \ \ \mbox{where} \ \ 0\leq r_{j+2}<r_{j+1}\] для всіх\(j=0,1,...,n-2\) і\[r_{n+1}=0.\] Потім\((a,b)=r_{n}\).

    Застосовуючи алгоритм ділення, ми бачимо, що\[\begin{aligned} r_0&=&r_1q_1+r_2 \ \ \ \ \ 0\leq r_2<r_1, \\ r_1&=&r_2q_2+r_3 \ \ \ \ \ 0\leq r_3<r_2, \\ &.& \\ &.& \\ &.& \\ r_{n-2}&=&r_{n-1}q_{n-1}+r_{n} \ \ \ \ \ 0\leq r_{n}<r_{n-1}, \\ r_{n-1}&=&r_{n}q_{n}.\end{aligned}\] Зверніть увагу, що, ми матимемо залишок від\(0\) врешті-решт, оскільки всі залишки цілих чисел і кожен залишок на наступному кроці менше, ніж залишок у попередньому. Лемма [lem1], ми бачимо, що\[(a,b)=(b,r_2)=(r_2,r_3)=...=(r_n,0)=r_n.\]

    Ми знайдемо найбільший спільний дільник\(4147\) і\(10672\):

    Зверніть увагу, що\[\begin{aligned} 10672&=&4147\cdot 2+2378,\\ 4147&=&2378\cdot 1+1769,\\ 2378&=&1769\cdot 1+609,\\ 1769&=&609\cdot 2 +551,\\ 609&=& 551\cdot 1+58, \\ 551&=&58\cdot 9+ 29,\\ 58&=&29\cdot 2,\\\end{aligned}\] Звідси\((4147,10672)=29.\)

    Тепер ми використовуємо кроки в евклідовому алгоритмі, щоб записати найбільший спільний дільник двох цілих чисел як лінійну комбінацію двох цілих чисел. Наступний приклад фактично визначить змінні\(m\) та\(n\) описані в теоремі [thm9]. Наступний алгоритм можна описати загальною формою, але для простоти виразів наведемо приклад, який показує кроки отримання найбільшого спільного дільника двох цілих чисел у вигляді лінійної комбінації двох цілих чисел.

    Експрес 29 як лінійна комбінація\(4147\) і\(10672\):

    \[\begin{aligned} 29&=&551-9\cdot 58,\\ &=& 551-9(609-551\cdot 1),\\ &=& 10.551-9.609,\\ &=& 10\cdot (1769-609\cdot 2)-9\cdot 609,\\ &=& 10\cdot 1769-29\cdot 609,\\ &=& 10\cdot 1769-29(2378-1769\cdot 1),\\ &=& 39\cdot 1769-29\cdot 2378,\\ &=& 39(4147-2378\cdot 1)-29\cdot 2378,\\ &=& 39\cdot 4147-68\cdot 2378,\\ &=& 39\cdot 4147-68(10672-4147\cdot 2),\\ &=& 175\cdot 4147-68\cdot 10672,\end{aligned}\]

    В результаті ми це бачимо\(29=175\cdot 4147-68\cdot 10672\).

    Вправи

    1. Використовуйте евклідовий алгоритм, щоб знайти найбільший спільний дільник 412 і 32 і висловити його через два цілих числа.
    2. Використовуйте евклідовий алгоритм, щоб знайти найбільший спільний дільник 780 і 150 і висловити його через два цілих числа.
    3. Знайти найбільший спільний дільник\(70,98, 108\).
    4. \(b\)Дозволяти\(a\) і бути двома позитивними парними цілими числами. Доведіть, що\((a,b)=2(a/2,b/2).\)
    5. Показати, що якщо\(a\) і\(b\) є додатними цілими числами,\(a\) де\(b\) парне і непарне, то\((a,b)=(a/2,b).\)

    Автори та атрибуція