5.4: Найбільші спільні дільники

Last updated
Save as PDF

Page ID: 64107

$ \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}}$

Задано будь-які два цілих числа$a$ і$b$, ціле число$c\neq0$ є спільним дільником або загальним коефіцієнтом$a$ і$b$ if$c$ ділить обидва$a$ і$b$. Якщо, крім того,$a$ і не$b$ обидва рівні нулю, то найбільший спільний дільник, що позначається$\gcd(a,b)$, визначається як найбільший спільний дільник$a$ і$b$. Найбільші спільні дільники також називають найвищими загальними факторами. Повинно бути зрозуміло, що$\gcd(a,b)$ має бути позитивним.

Приклад$\PageIndex{1}\label{eg:gcd-01}$

Спільними дільниками 24 і 42 є$\pm1$,$\pm2$,$\pm3$, і$\pm6$. Серед них 6 є найбільшими. Тому,$\gcd(24,42)=6$. Загальні дільники 12 і 32 є$\pm1$,$\pm2$ і$\pm4$, з цього випливає$\gcd(12,32)=4$.

практичні вправи$\PageIndex{1}\label{he:gcd-01}$

Переконайтеся, що\[\gcd(5,35)=5, \quad \gcd(-5,10)=5, \quad \gcd(20,-10)=10, \quad\mbox{and}\quad \gcd(20,70)=10. \nonumber\] Поясніть чому$\gcd(3,5)=1$

Приклад$\PageIndex{2}\label{eg:gcd-02}$

Чи можете ви пояснити чому$\gcd(0,3)=3$? Як щодо$\gcd(0,-3)=3$?

Рішення: Нагадаємо, що 0 ділиться на будь-яке ненульове ціле число. Отже, всі дільники 3 також є дільниками 0. Очевидно, що 3 сам по собі є найбільшим дільником 3. Тому,$\gcd(0,3)=3$.

практичні вправи$\PageIndex{2}\label{he:gcd-02}$

Поясніть чому$\gcd(0,-8)=8$.

Теорема$\PageIndex{1}\label{thm:gcd0b}$

Для будь-якого ненульового цілого числа$b$, ми маємо$\gcd(0,b)=|b|$.

Доказ

Найбільшим додатним дільником$b$ є$|b|$. Оскільки$|b|$ також ділить 0, робимо висновок, що$\gcd(0,b)=|b|$.

Теорема 5.4.1 говорить нам, що$\gcd(0,b)=|b|$ якщо$b$ є ненульовим. З визначення загального дільника і найбільшого спільного дільника зрозуміло, що$\gcd(a,b) = \gcd(b,a)$, і$\gcd(a,b) = \gcd(\pm a,\pm b)$. Таким чином, ми можемо припустити$1\leq a\leq b$.

Теорема$\PageIndex{2}$

$b$Дозволяти$a$ і бути цілими числами такі, що$1\leq a\leq b$. Якщо$b=aq+r$, де$0\leq r< a$, то$\gcd(b,a)=\gcd(a,r)$.

Доказ

Щоб полегшити наш аргумент, нехай$d=\gcd(b,a)$ і$e=\gcd(a,r)$. За визначенням,$d$ є дільником обох$b$ і$a$. Тому$b=dx$ і$a=dy$ для деяких цілих чисел$x$ і$y$. Тоді\[r = b-aq = dx-dy\cdot q = d(x-yq), \nonumber\] де$x-yq$ - ціле число. Отже,$d\mid r$. Це$d$ робить загальний дільник обох$r$ і$a$. Оскільки$e$ є найбільшим спільним дільником$a$ і$r$, ми визначаємо, що$d\leq e$.

Аналогічно,$e=\gcd(a,r)$ є дільником обох$a$ і$r$. Таким чином,$a=eu$ і$r=ev$ для деяких цілих чисел$u$ і$v$. Тоді\[b = aq+r = a\cdot eu+ev = e(au+v), \nonumber\] де$au+v$ - ціле число. Отже,$e\mid b$. Це$e$ робить загальний дільник обох$b$ і$a$. Оскільки$d$ є найбільшим спільним дільником$b$ і$a$, ми виводимо, що$e\leq d$. Разом з$d\leq e$, робимо висновок, що$d=e$.

Приклад$\PageIndex{3}\label{eg:gcd-03}$

Від$997=996\cdot1+1$, отримуємо$\gcd(997,996)=\gcd(996,1)=1$.

Теорема це запевняє$\gcd(b,a) = \gcd(a,r)$. Ми можемо застосувати теорему знову до$\gcd(a,r)$. Ділення$a$ на$r$ дає новий частку і новий залишок. При необхідності повторюйте процес до тих пір, поки залишок не стане нулем. Якщо позначимо$b=r_0$ і$a=r_1$, то\[\begin{array}{rcl@{\qquad\qquad}l} r_0 &=& r_1 q_1 + r_2, & 0\leq r_2 < r_1, \\ r_1 &=& r_2 q_2 + r_3, & 0\leq r_3 < r_2, \\ r_2 &=& r_3 q_3 + r_4, & 0\leq r_4 < r_3, \\ \vdots & & \vdots \\ r_{k-1} &=& r_k q_k + r_{k+1}, & 0\leq r_{k+1} < r_k, \\ \vdots & & \vdots \\ r_{n-3} &=& r_{n-2} q_{n-2} + r_{n-1}, & 0\leq r_{n-1} < r_{n-2}, \\ r_{n-2} &=& r_{n-1} q_{n-1} + r_n, & r_n=0. \end{array} \nonumber\] випливає, що\[\gcd(b,a) = \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_{n-1},0) = r_{n-1}. \nonumber\] останній ненульовий залишок є$\gcd(a,b)$. Цей метод знаходження найбільшого спільного дільника називається евклідовим алгоритмом.

Приклад$\PageIndex{4}\label{eg:gcd-04}$

Знайти$\gcd(426,246)$.

Рішення: Застосовуючи теорему неодноразово, ми знаходимо\[\begin{array}{rcl@{\qquad\qquad}lcl} 426 &=& 246\cdot1+180, & \gcd(426,246) &=& \gcd(246,180) \\ 246 &=& 180\cdot1+ 66, & \gcd(246,180) &=& \gcd(180, 66) \\ 180 &=& 66\cdot2+ 48, & \gcd(180, 66) &=& \gcd( 66, 48) \\ 66 &=& 48\cdot1+ 18, & \gcd( 66, 48) &=& \gcd( 48, 18) \\ 48 &=& 18\cdot2+ 12, & \gcd( 48, 18) &=& \gcd( 18, 12) \\ 18 &=& 12\cdot1+ 6, & \gcd( 18, 12) &=& \gcd( 12, 6) \\ 12 &=& 6\cdot2+ 0, & \gcd( 12, 6) &=& \gcd( 6, 0) = 6. \end{array} \nonumber\] Отже,$\gcd(426,246)=6$.

практичні вправи$\PageIndex{3}\label{he:gcd-03}$

Визначте$\gcd(732,153)$.

практичні вправи$\PageIndex{4}\label{he:gcd-04}$

Визначте$\gcd(6958,2478)$.

Вручну ефективніше використовувати двоколонковий формат. Спочатку поставте два числа 426 і 246 в дві окремі стовпці, з більшим числом зліва. Виконайте короткий поділ, а зліва напишіть частку:\[\begin{array}{r|r|r|r} 1 & 426 & 246 & \\ & 246 & & \\ \ \cline{2-2} & 180 & & \end{array} \nonumber\]

У наступному раунді виконайте ще один короткий поділ на два числа 246 і 180 внизу. Оскільки більше число тепер знаходиться в правій колонці, залиште частку праворуч:

\[\begin{array}[t]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \hline & 180 & 66 & \end{array} \nonumber\]

Продовжуйте таким чином, поки залишок не стане 0. Останній ненульовий запис внизу є найбільшим спільним дільником. Ми також можемо залишити всі частки ліворуч:

\[\begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \hline 2 & 180 & 66 & 1 \\ & 132 & 48 & \\ \hline 2 & 48 & 18 & 1 \\ & 36 & 12 & \\ \hline 2 & 12 & 6 & \\ & 12 & & \\ \hline & 0 & \end{array} \hskip0.5in\mbox{or}\hskip0.5in \begin{array}[c]{r|r|r|r} 1 & 426 & 246 & \\ 1 & 246 & 180 & \\ \hline 2 & 180 & 66 & \\ 1 & 132 & 48 & \\ \hline 2 & 48 & 18 & \\ 1 & 36 & 12 & \\ \hline 2 & 12 & 6 & \\ & 12 & & \\ \hline & 0 & \end{array} \nonumber\]

практичні вправи$\PageIndex{5}\label{he:gcd-05}$

Використовуйте формат з двома стовпцями для обчислення$\gcd(153,732)$.

практичні вправи$\PageIndex{6}\label{eg:gcd-06}$

Використовуйте формат з двома стовпцями для обчислення$\gcd(6958,2478)$.

Задані будь-які цілі числа$m$ і$n$, числа виду$ms+nt$, де$s,t$ цілі числа, називаються лінійними комбінаціями$m$ і$n$. Вони відіграють важливу роль при вивченні$\gcd(m,n)$, як зазначено в наступній теоремі.

Теорема$\PageIndex{3}$

Для будь-яких ненульових цілих чисел$a$ і$b$, існують цілі числа$s$ і$t$ такі, що$\gcd(a,b)=as+bt$.

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

Теорема$\PageIndex{4}$

Кожна лінійна комбінація$a$ і$b$ є кратною$\gcd(a,b)$.

Слідство$\PageIndex{5}$

Найбільший спільний дільник двох ненульових цілих чисел$a$ і$b$ є найменшим натуральним числом серед усіх їх лінійних комбінацій.

Важливо розуміти, про що говорять ці три результати. Знаходження лінійної комбінації$a$ і$b$ тільки дає нам кратну$\gcd(a,b)$. Тільки спеціальна лінійна комбінація дасть точне значення$\gcd(a,b)$.

Приклад$\PageIndex{5}\label{eg:gcd-05}$

$n+1$Дозволяти$n$ і бути два послідовних натуральних числа. Потім\[n\cdot(-1)+(n+1)\cdot1 = 1 \nonumber\] має на увазі, що 1 кратна найбільшому спільному дільнику$n$ і$n+1$. Це означає, що найбільший спільний дільник повинен бути 1. Тому$\gcd(n,n+1)=1$ для всіх цілих чисел$n$.

Визначення

Два цілих числа$a$ і$b$, як кажуть, є відносно простими, якщо$\gcd(a,b)=1$. Тому$a$ і$b$ є відносно простими, якщо вони не мають спільних дільників, крім$\pm 1$.

Приклад$\PageIndex{6}\label{eg:gcd-06}$

Доведіть$\gcd(a,b)=1$, що якщо, то$\gcd(a+b,a-b)$ дорівнює 1 або 2.

Рішення: З лінійних комбінацій\[\begin{aligned} (a+b)\cdot1+(a-b)\cdot1 &=& 2a, \\ (a+b)\cdot1+(a-b)\cdot(-1) &=& 2b, \end{aligned} \nonumber\] ми знаємо, що$\gcd(a+b,a-b)$ ділить обидва$2a$ і$2b$. Оскільки$\gcd(a,b)=1$, робимо висновок, що$\gcd(a+b,a-b)$ ділить 2. Отже,$\gcd(a+b,a-b)$ це або 1, або 2.

Приклад$\PageIndex{7}\label{eg:gcd-07}$

Показати, що якщо$\gcd(a,b)=1$, то$\gcd(2a+b,a+2b)$ дорівнює або 1 або 3.

Рішення: З лінійних комбінацій\[\begin{aligned} (2a+b)\cdot 2 +(a+2b)\cdot(-1) &=& 3a, \\ (2a+b)\cdot(-1)+(a+2b)\cdot 2 &=& 3b, \end{aligned} \nonumber\] ми знаємо, що$\gcd(2a+b,a+2b)$ ділить обидва$3a$ і$3b$. Оскільки$\gcd(a,b)=1$, робимо висновок, що$\gcd(2a+b,a+2b)$ ділить 3. Таким чином,$\gcd(a+b,a-b)$ це 1 або 3.

практичні вправи$\PageIndex{7}\label{he:gcd-07}$

Які можливі значення,$\gcd(5m+7n,7m+5n)$ якщо два натуральних числа$m$ і$n$ є відносно простими?

Приклад$\PageIndex{8}\label{eg:gcd-08}$

Знайти цілі числа$s$ і$t$ такі, що$6=\gcd(426,246)=246s+426t$.

Рішення

Раніше ми вивчали, як знайти$\gcd(426,246)=6$. У кожному діленні ми хочемо висловити залишок як лінійну комбінацію 246 і 426. Ось як відбувається обчислення:

\[\begin{array}{lrcl} 426 = 246\cdot1+180,& 180 &=& 246\cdot(-1)+426\cdot1 \\ [3pt] 246 = 180\cdot1+66, & 66 &=& 246\cdot1+180\cdot(-1) \\ & &=& 246\cdot1+[246\cdot(-1)+426\cdot1]\cdot(-1) \\ & &=& 246\cdot2+426\cdot(-1) \\ [3pt] 180 = 66\cdot2+48, & 48 &=& 180\cdot1+66\cdot(-2) \\ & &=& [246\cdot(-1)+426\cdot1]\cdot1 +[246\cdot2+426\cdot(-1)]\cdot(-2) \\ & &=& 246(-5)+426\cdot3 \\ 66 = 48\cdot1+18, & 18 &=& 66\cdot1+48\cdot(-1) \\ & &=& [246\cdot2+426\cdot(-1)]\cdot1 + [246(-5)+426\cdot3]\cdot(-1) \\ & &=& 246\cdot7+426\cdot(-4) \\ [3pt] 48 = 18\cdot2+12, & 12 &=& 48\cdot1+18\cdot(-2) \\ & &=& [246(-5)+426\cdot3]\cdot1 + [246\cdot7+426\cdot(-4)]\cdot(-2) \\ & &=& 246\cdot(-19)+426\cdot11 \\ [3pt] 18 = 12\cdot1+6, & 6 &=& 18\cdot1 + 12\cdot(-1) \\ & &=& [246\cdot7+426\cdot(-4)]\cdot1 + [246\cdot(-19)+426\cdot11]\cdot(-1) \\ & &=& 246\cdot26+426\cdot(-15) \end{array} \nonumber\]

Відповідь є$6=246\cdot26+426\cdot(-15)$.

Обчислення стомлює! Розширений евклідовий алгоритм забезпечує полегшення. Він відстежує дві послідовності цілих чисел$s_k$ і$t_k$ поряд з$r_k$, таким чином, що\[r_k = a s_k + b t_k. \nonumber\] Це виражає кожен залишок як лінійну комбінацію$a$ і$b$. Оскільки останній ненульовий залишок є$\gcd(a,b)$, відповідна лінійна комбінація буде відповідною відповіддю, яку ми шукаємо.

Значення$s_k$ і$t_k$ для останнього прикладу підсумовуються нижче:

\[\begin{array}{|c|r|r|r| } \hline k & r_k & s_k & t_k \\ \hline 2 & 180 & -1 & 1 \\ 3 & 60 & 2 & -1 \\ 4 & 48 & -5 & 3 \\ 5 & 18 & 7 & -4 \\ 6 & 12 & -19 & 11 \\ 7 & 6 & 26 & -15 \\ \hline \end{array} \nonumber\]

Головне питання: як ми можемо ефективно обчислити ці значення?

Наведена вище таблиця починається з$k=2$. Як щодо$k=0$ і$k=1$? Від\[b = r_0 = a s_0 + b t_0, \nonumber\] визначаємо, що$s_0=0$ і$t_0=1$. Аналогічно,

\[a = r_1 = a s_1 + b t_1 \nonumber\]

має на увазі, що$s_1=1$ і$t_1=0$. Отже, список значень$s_k$ і$t_k$ починаємо з наступного:

\[\begin{array}{ccc} k & s_k & t_k \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \nonumber\]

Загалом, перш ніж проводити поділ$r_{k-1}\div r_k$, ми повинні були вже генерувати$s_0$ наскрізний$s_k$, і$t_0$ наскрізний$t_k$. Після поділу отримуємо$q_k$ і$r_{k+1}$ як в

\[r_{k-1} = r_k q_k + r_{k+1}. \nonumber\]

Далі обчислюємо$s_{k+1}$ і$t_{k+1}$ перш ніж переходити до наступного поділу. знаходимо

\[\begin{array}{rcl} r_{k+1} &=& r_{k-1} - r_k q_k \\ &=& (a s_{k-1} + bt_{k-1}) - (a s_k + b t_k) q_k \\ &=& a (s_{k-1} - s_k q_k) + b (t_{k-1} - t_k q_k). \end{array} \nonumber\]

Тому нам потрібно

\[\begin{array}{r c l} s_{k+1} &=& s_{k-1} - s_k q_k, \\ t_{k+1} &=& t_{k-1} - t_k q_k. \end{array} \nonumber\]

Словами:

\[\displaylines{ \mbox{next $s$-value} = \mbox{previous-previous $s$-value} - \mbox{previous $s$-value}\times \mbox{corresponding $q$}, \cr \mbox{next $t$-value} = \mbox{previous-previous $t$-value} - \mbox{previous $t$-value}\times \mbox{corresponding $q$}. \cr} \nonumber\]

Наприклад, припустимо на певному етапі значення$s$$t$, і$q$ виглядають наступним чином:

\[\begin{array}{ccc} k & s_k & t_k & q_k \\ 0 & 0 & 1 & \\ 1 & 1 & 0 & 1 \\ 2 & -1 & 1 & 1 \\ 3 & 2 & -1 & 2 \\ & & & 1 \\ & & & 2 \\ & & & 1 \\ & & & 2 \end{array} \nonumber\]Тоді\[\displaylines{ \mbox{next $s$-value} = -1-2\cdot2 = -5, \cr \mbox{next $t$-value} = 1-(-1)\cdot2 = 3. \cr} \nonumber\] Тепер список стає\[\begin{array}{ccc} k & s_k & t_k & q_k \\ 0 & 0 & 1 & \\ 1 & 1 & 0 & 1 \\ 2 & -1 & 1 & 1 \\ 3 & 2 & -1 & 2 \\ 4 & -5 & 3 & 1 \\ & & & 2 \\ & & & 1 \\ & & & 2 \end{array} \nonumber\]

Весь розрахунок може проводитися в модифікованому двоколонковому форматі.

Приклад$\PageIndex{9}\label{eg:gcd-09}$

Знайти цілі числа$s$ і$t$ такі, що$\gcd(246,426)=246s+426t$.

Рішення

Спочатку скопіюйте частки з крайнього правого стовпчика та вставте їх між цими частками у крайньому лівому стовпці:

\[\begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \cline{2-3} 2 & 180 & 66 & 1 \\ & 132 & 48 & \\ \cline{2-3} 2 & 48 & 18 & 1 \\ & 36 & 12 & \\ \cline{2-3} 2 & 12 & 6 & \\ & 12 & & \\ \cline{2-2} & 0 & \end{array} \qquad\mbox{becomes}\qquad \begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ 1 & 246 & 180 & \\ \cline{2-3} 2 & 180 & 66 & 1 \\ 1 & 132 & 48 & \\ \cline{2-3} 2 & 48 & 18 & 1 \\ 1 & 36 & 12 & \\ \cline{2-3} 2 & 12 & 6 & \\ & 12 & & \\ \cline{2-2} & 0 & \end{array} \nonumber\]

Далі обчислюємо$s_k$ і$t_k$ поряд з цими частками (нам не потрібно записувати значення$k$):

\[\begin{array}[t]{rr@{\qquad}r|r|r|r} s_k & t_k & \multicolumn{1}{r}{q_k} \\ 0 & 1 \\ 1 & 0 & 1 & 426 & 246 & 1 \\ -1 & 1 & 1 & 246 & 180 & \\ \cline{4-5} 2 & -1 & 2 & 180 & 66 & 1 \\ -5 & 3 & 1 & 132 & 48 & \\ \cline{4-5} 7 & -4 & 2 & 48 & 18 & 1 \\ -19 & 11 & 1 & 36 & 12 & \\ \cline{4-5} 26 & -15 & 2 & 12 & 6 & \\ & & & 12 & & \\ \cline{4-4} & & & 0 & \end{array} \nonumber\]Останній ненульовий залишок є найбільшим спільним дільником, а остання лінійна комбінація дає бажану відповідь. Знаходимо$\gcd(246,426) = 6 = 26\cdot246-15\cdot426$.

Зверніть увагу, що, починаючи з$k=2$, ознаки$s_k$ і$t_k$ чергуються. Це забезпечує швидку перевірку їх ознак. Крім того, ознаки$s_k$ і$t_k$ є протилежними для кожного$k\geq2$.

практичні вправи$\PageIndex{8}\label{he:gcd-08}$

Використовуйте формат з двома стовпцями, щоб знайти лінійну комбінацію, яка виробляє$\gcd(153,732)$.

практичні вправи$\PageIndex{9}\label{he:gcd-09}$

Використовуйте формат з двома стовпцями, щоб знайти лінійну комбінацію, яка виробляє$\gcd(2478,6958)$.

Резюме та огляд

Найбільший спільний дільник двох цілих чисел, а не обох нулів, є найбільшим (отже, він повинен бути додатним) цілим числом, яке ділить обидва.
Використовуйте евклідовий алгоритм, щоб знайти найбільший спільний дільник. Вона може бути реалізована в двоколонковому форматі.
Використовуючи розширену версію з двома додатковими стовпцями для обчислень$s_k$ і$t_k$, ми можемо знайти спеціальну лінійну комбінацію двох цілих чисел, яка виробляє їх найбільший спільний дільник.
Загалом, лінійна комбінація двох цілих чисел дає лише кратне їх найбільшому спільному дільнику.

Вправа$\PageIndex{1}\label{ex:gcd-01}$

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

27, 81
24, 84
1380, 3020

Вправа$\PageIndex{2}\label{ex:gcd-02}$

120, 615
412, 936
1122, 3672

Вправа$\PageIndex{3}\label{ex:gcd-03}$

Які можливі значення,$\gcd(2a+5b,5a-2b)$ якщо два натуральних числа aa та bb є відносно простими?

Вправа$\PageIndex{4}\label{ex:gcd-04}$

Доведіть, що будь-які послідовні непарні натуральні числа є відносно простими.

Вправа$\PageIndex{5}\label{ex:gcd-05}$

$n$Дозволяти$m$ і бути натуральними числами. Доведіть, що$\gcd(m,m+n)\mid n$.

Вправа$\PageIndex{6}\label{ex:gcd-06}$

$b$Дозволяти$a$ і бути цілими числами такі, що$1<a<b$ і$\gcd(a,b)=1$. Доведіть, що$\gcd(a+b,ab)=1$.

Вправа$\PageIndex{7}\label{ex:gcd-07}$

Які можливі значення,$\gcd(3m-5n,5m+3n)$ якщо два натуральних числа$m$ і$n$ є відносно простими?

Вправа$\PageIndex{8}\label{ex:gcd-08}$

Які можливі значення,$\gcd(4p+7q,7p-4q)$ якщо два натуральних числа$p$ і$q$ є відносно простими?