5.5: Детальніше про НСД

Last updated
Save as PDF

Page ID: 64103

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

У цьому розділі ми обговоримо кілька технічних результатів про$\gcd(a,b)$.

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

Нехай$d=\gcd(a,b)$, де$a,b\in\mathbb{N}$. Тоді\[\{ as+bt \mid s,t\in\mathbb{Z} \} = \{ nd \mid n\in\mathbb{Z} \}. \nonumber\] Отже, кожна лінійна комбінація$a$ і$b$ є кратним$\gcd(a,b)$, і навпаки, кожне кратне$\gcd(a,b)$ виражається як лінійна комбінація$a$ і$b$.

Доказ

Для стислості, нехай\[S=\{as+bt\mid s,t\in\mathbb{Z}\}, \qquad\mbox{and}\qquad T=\{nd\mid n\in\mathbb{Z}\}. \nonumber\] Ми покажемо це,$S=T$ доводячи, що$S\subseteq T$ і$T\subseteq S$.

Нехай$x\in S$. Щоб довести це$S\subseteq T$, ми хочемо показати$x\in T$ і це. Перебуваючи в$S$ означає$x = as+bt$ для деяких цілих чисел$s$ і$t$. Так як$d=\gcd(a,b)$, ми знаємо, що$d\mid a$ і$d\mid b$. Значить,$a=da'$ і$b=db'$ для деяких цілих чисел$a'$ і$b'$. Тоді\[x = as+bt = da's+db't = d(a's+b't), \nonumber\] де$a's+b't$ - ціле число. Це показує, що$x$ є кратним$d$. Отже,$x\in T$.

Щоб це показати$T\subseteq S$, досить показати, що$d\in S$. Причина в тому, якщо$d=as+bt$ для деяких цілих чисел$s$ і$t$, то$nd = n(as+bt) = a(ns)+b(nt)$ має на увазі, що$nd\in S$.

Щоб це довести$d\in S$, врахуйте$S^+$. З тих пір$a=a\cdot1+b\cdot0$, у нас є$a\in S^+$. Отже,$S^+$ є непорожнім набором натуральних чисел. Принцип добре впорядкованості має на увазі, що$S^+$ має найменший елемент. Називайте це$e$. Потім\[e = as^*+bt^* \nonumber\] для деяких цілих чисел$s^*$ і$t^*$. Ми це вже знаємо$a\in S^+$. Будучи найменшим елементом в$S^+$, ми повинні мати$e\leq a$. Потім$a=eq+r$ для деяких цілих чисел$q$ і$r$, де$0\leq r<e$. Якщо$r>0$, то\[r = a-eq = a-(as^*+bt^*)q = a(1-s^*q)+b(-t^*q). \nonumber\] це робить$r$ лінійну комбінацію$a$ і$b$. Так як$r>0$, знаходимо$r\in S^+$. Оскільки$r<e$ б суперечити мінімалізмі$e$, ми повинні мати$r=0$. Отже$a=eq$, таким чином$e\mid a$. Аналогічно, оскільки$b = a\cdot0+b\cdot1\in S^+$, ми можемо застосувати той самий аргумент, щоб показати, що$e\mid b$. Зробимо висновок, що$e$ є загальним дільником$a$ і$b$.

$f$Дозволяти бути будь-який спільний дільник$a$ і$b$. Потім$f\mid a$ і$f\mid b$. Звідси випливає, що$f\mid (ax+by)$ для будь-яких цілих чисел$x$ і$y$. Зокрема,$f\mid(as^*+bt^*)=e$. Отже,$f\leq e$. $e$Оскільки сам по собі загальний дільник$a$ і$b$, і ми тільки що довели,$e$ що більше, ніж будь-який інший спільний дільник$a$ і$b$,$e$ саме ціле число повинно бути найбільшим спільним дільником. Звідси випливає, що$d=\gcd(a,b)=e\in S^+$. Зараз доказ завершено.

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

Найбільший спільний дільник двох ненульових цілих чисел$a$ і$b$ є найменшим натуральним числом серед усіх їх лінійних комбінацій. Іншими словами,$\gcd(a,b)$ це найменший позитивний елемент у множині$\{as+bt \mid s,t\in\mathbb{Z}\}$.

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

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

Доказ: Теорема 5.5.1 стверджує, що множина всіх лінійних комбінацій$a$ і$b$ дорівнює множині всіх кратних$\gcd(a,b)$. Оскільки$\gcd(a,b)$ це кратна сама по собі, вона повинна дорівнювати одній з цих лінійних комбінацій. Таким чином,$\gcd(a,b) = sa+tb$ для деяких цілих чисел$s$ і$t$.

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

Два ненульових цілих числа$a$ і$b$ є відносно простими, якщо і тільки якщо$as+bt=1$ для деяких цілих чисел$s$ і$t$.

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

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

Зрозуміло, що 5 і 7 є відносно простими, так і 14 і 27. Знайдіть лінійну комбінацію цих двох пар чисел, яка дорівнює 1.

Рішення: Шляхом огляду, або використовуючи розширений евклідовий алгоритм, знаходимо$3\cdot5-2\cdot7=1$, і$2\cdot14-1\cdot27=1$.

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

Покажіть це,$\gcd(133,143)=1$ знайшовши відповідну лінійну комбінацію.

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

Покажіть, що 757 і 1215 є відносно простими, знайшовши відповідну лінійну комбінацію.

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

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

Теорема$\PageIndex{5}$ (Euclid's Lemma)

Нехай$a,b,c\in\mathbb{Z}$. Якщо$\gcd(a,c)=1$ і$c\mid ab$, то$c\mid b$.

Обговорення

Давайте запишемо те, що ми знаємо і що ми хочемо показати (WTS):\[\begin{array}{ll} \mbox{Know}: & as+ct=1 \mbox{ for some integers $s$ and $t$}, \\ & ab = cx \mbox{ for some integer $x$}, \\ \mbox{WTS}: & b = cq \mbox{ for some integer $q$}. \end{array} \nonumber\] Щоб мати можливість показати, що$b=cq$ для деякого цілого числа$q$, ми повинні придумати деяку інформацію про$b$. Ця інформація повинна виходити з двох рівнянь$as+ct=1$ і$ab=cx$. Так як$b=b\cdot1$, ми можемо$b$ множити на обидві сторони$as+ct=1$. За умовністю ми не можемо писати

$(as+ct=1) \cdot b$.

Це позначення неприпустимо! Причина в тому, що ми не можемо помножити рівняння на число. Швидше, ми повинні помножити обидві сторони рівняння на число:\[b = 1\cdot b = (as+ct)\cdot b = asb + ctb. \nonumber\] Очевидно,$ctb$ кратна$c$; ми на крок ближче до нашої мети. Так як$asb = ab\cdot s$, і ми знаємо,$ab$ що дійсно кратна$c$, тому доказ може бути завершений. Тепер ми готові зв'язати вільні кінці, і полірувати доказ.

Доказ: Припустимо$\gcd(a,c)=1$, і$c\mid ab$. Існують цілі числа$s$ і$t$ такі, що\[as + ct = 1. \nonumber\] Це призводить до\[b = 1\cdot b = (as+ct)\cdot b = asb + ctb. \nonumber\] Since$c\mid ab$, існує ціле число$x$ таке, що$ab=cx$. Тоді\[b = ab\cdot s + ctb = cx\cdot s + ctb = c(xs+tb), \nonumber\] де$xc+tb\in\mathbb{Z}$. Тому,$c\mid b$.

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

Якщо$a,b\in\mathbb{Z}$ і$p$ є простим таким$p\mid ab$, що, то або$p\mid a$ або$p\mid b$.

Доказ: Якщо$p\mid a$, ми закінчили з доказом. Якщо$p\nmid a$$\gcd(p,a)=1$, то і лема Евкліда має на увазі це$p\mid b$.

Ми не можемо застосувати наслідок, якщо$p$ є складовим. Наприклад$6\mid 4\cdot15$, але$6\nmid 4$ і$6\nmid 15$. З іншого боку, коли$p\mid ab$, де$p$ просте, можна мати$p\mid a$ і те й інше$p\mid b$. Наприклад$5\mid 15\cdot 25$, все ж у нас є і те,$5\mid 15$ і інше$5\mid 25$.

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

Якщо$a_1,a_2,\ldots,a_n\in\mathbb{Z}$ і$p$ є простим таким$p\mid a_1 a_2 \cdots a_n$, що, то$p\mid a_i$ для деяких$i$, де$1\leq i\leq n$. Отже, якщо просте$p$ ділить добуток$n$ факторів, то$p$ необхідно розділити хоча б один з цих$n$ факторів.

Доказ: Ми залишаємо вам доказ як вправу.

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

Доведіть, що$\sqrt{2}$ це нераціонально.

Зауваження

Раніше ми довели, що$\sqrt{2}$ це нераціонально в практичних вправах. Представлене нами рішення має незначний недолік. Ключовий крок у цьому доказі стверджує, що\[\mbox{The integer 2 divides $m^2$, therefore 2 divides $m$}. \nonumber\] Це твердження є помилковим загалом. Наприклад, 4 ділить$6^2$, а 4 не ділить 6. Тому ми повинні обґрунтувати, чому ця претензія дійсна для 2.

Рішення: Припустимо,$\sqrt{2}$ є раціональним, то ми можемо записати\[\sqrt{2} = \frac{m}{n} \nonumber\] для деяких натуральних чисел$m$ і$n$ які не мають спільного дільника, крім 1. Квадратування обох сторін і перехресне множення дає\[2n^2 = m^2. \nonumber\] Таким чином 2 ділення$m^2$. Оскільки 2 є простим, лема Евкліда передбачає, що 2 також повинні розділити$m$. Тоді ми можемо написати$m=2s$ для деякого цілого числа$s$. Рівняння вище стає\[2n^2 = m^2 = (2s)^2 = 4s^2. \nonumber\] Отже,\[n^2 = 2s^2, \nonumber\] що означає, що 2 ділить$n^2$. Знову ж таки, оскільки 2 є простим, лема Евкліда передбачає, що 2 також ділить$n$. Ми довели, що обидва$m$ і$n$ діляться на 2. Це суперечить$m$ припущенню, що і$n$ не мають спільного дільника. Значить,$\sqrt{2}$ має бути нераціональним.

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

Доведіть, що$\sqrt{7}$ це нераціонально.

Закриваємо цей розділ воістину захоплюючим результатом.

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

Для будь-яких натуральних чисел$m$ and$n$,$\gcd(F_m,F_n)=F_{\gcd(m,n)}$.

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

Для будь-якого натурального цілого числа$n$,$3\mid F_n \Leftrightarrow 4\mid n$.

Доказ

($\Rightarrow$) Якщо$3\mid F_n$, то, тому що$F_3=4$, у нас\[3 = \gcd(3,F_n) = \gcd(F_4,F_n) = F_{\gcd(4,n)}. \nonumber\] випливає$\gcd(4,n)=4$, що, в свою чергу, означає, що$4\mid n$.

($\Leftarrow$) Якщо$4\mid n$, то$\gcd(4,n)=4$, і,\[\gcd(3,F_n) = \gcd(F_4,F_n) = F_{\gcd(4,n)} = F_4 = 3; \nonumber\] отже,$3\mid F_n$.

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

За будь-якими двома ненульовими цілими числами існує лише одна спеціальна лінійна комбінація, яка дорівнювала б їх найбільшому спільному дільнику.
Всі інші лінійні комбінації є лише кратними їх найбільшому спільному дільнику.
Якщо$a$ і відносно$c$ прості, то лема Евкліда стверджує, що якщо$c$ ділить$ab$, то$c$ треба ділити$b$.
Зокрема, якщо$p$ є простим, а якщо$p\mid ab$, то або$p\mid a$ або$p\mid b$.

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

Задано будь-яке довільне натуральне число$n$, довести, що$2n+1$ і$3n+2$ є відносно простими.

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

Використовуйте індукцію, щоб довести$n\geq2$, що для будь-якого цілого числа, якщо$a_1,a_2,\ldots,a_n\in\mathbb{Z}$ і$p$ є простим таким$p\mid a_1 a_2 \cdots a_n$, що, то$p\mid a_i$ для деяких$i$, де$1\leq i\leq n$.

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

Доведіть, що$\sqrt{p}$ є ірраціональним для будь-якого простого числа$p$.

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

Доведіть, що$\sqrt[3]{2}$ це нераціонально.

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

Дано будь-які довільні натуральні числа$a$$b$,$c$, і, показують$a\mid c$, що якщо$b\mid c$, і$\gcd(a,b)=1$, то$ab\mid c$.

Зауваження. Цей результат дуже важливий. Запам'ятайте це!

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

Дано будь-які довільні натуральні числа$a$$b$, і$c$, показують, що якщо$a\mid c$, і$b\mid c$, то$ab\mid cd$, де$d=\gcd(a,b)$.

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

Використовуйте індукцію, щоб довести, що$3\mid(2^{4n}-1)$ і$5\mid(2^{4n}-1)$ для будь-якого цілого числа$n\geq1$. Використовуйте ці результати, щоб довести, що$15\mid (2^{4n}-1)$ для будь-якого цілого числа$n\geq1$.

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

Доведіть, що$2\mid F_n \Leftrightarrow 3\mid n$ для будь-якого натурального цілого числа$n$.