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

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

[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).$

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

• Template:ContribRaji