5.1: Теорія чисел - подільність та конгруентність

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

5.1A. Подільність.

Кожен студент математики знає, що деякі числа парні, а деякі - непарні; деякі числа діляться на 3, а деякі ні; тощо Давайте введемо позначення, яке дозволяє легко говорити про те, чи ділиться\(b\) одне число на якесь інше число\(a\):

Визначення\(5.1.1\).

Припустимо\(a, b \in \mathbb{Z}\). Ми говоримо\(a\) є дільником\(b\) (і писати «\(a \mid b\)»), якщо існує\(k \in \mathbb{Z}\), такий, що\(ak = b\). (Оскільки множення є комутативним, а рівність симетрична, це рівняння також можна записати як\(b = ka\).)

Позначення\(5.1.2\).

\(a \nmid b\)це абревіатура від «\(a\)не ділить»\(b\).

Зауваження\(5.1.3\).

Коли\(a\) є дільником\(b\), ми можемо також сказати:

1. \(a\)ділить\(b\), або
2. \(a\)є фактором\(b\), або
3. \(b\)є кратним\(a\), або
4. \(b\)ділиться на\(a\).

Приклад\(5.1.4\).

1. У нас є\(5 \mid 30\), тому що\(5 \cdot 6=30\), і\(6 \in \mathbb{Z}\).
2. У нас є\(5 \nmid 27\), тому що немає цілого числа\(k\), такі, що\(5k = 27\).

Вправа\(5.1.5\).

Заповніть кожну заготовку\(\mid\) або\(\nmid\), якщо це доречно.

1. 3________18
2. 4________18
3. 5________18
4. 6________18
5. 18________6
6. −6________6

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

Визначення\(5.1.6\).

Нехай\(n \in \mathbb{Z}\). Ми говоримо\(n\), що це навіть якщо\(2 \mid n\). Ми говоримо, що\(n\) це непарно iff\(2 \nmid n\).

Ось кілька прикладів доказів, пов'язаних з подільністю. Будемо вважати відомий факт, що сума, різниця і добуток цілих чисел є цілими числами: для всіх\(k_{1}, k_{2} \in \mathbb{Z}\), ми знаємо, що\(k_{1}+k_{2} \in \mathbb{Z}, k_{1}-k_{2} \in \mathbb{Z}\), а\(k_{1} k_{2} \in \mathbb{Z} .\) також, негатив будь-якого цілого числа - це ціле число: для всіх\(k \in \mathbb{Z}\), у нас є\(−k \in \mathbb{Z}\).

Наш перший результат - узагальнення відомого факту, що сума двох парних чисел парна.

Пропозиція\(5.1.7\).

Припустимо\(a, b_{1}, b_{2} \in \mathbb{Z}\). Якщо\(a \mid b_{1}\) і\(a \mid b_{2}\), то\(a \mid\left(b_{1}+b_{2}\right)\).

Подряпини. Оскільки\(a \mid b_{1}\) і\(a \mid b_{2}\), ми знаємо, що є деякі\(k \in \mathbb{Z}\), такі, що\(ak = b_{1}\), і ми знаємо, що є деякі\(k \in \mathbb{Z}\), такі, що\(ak = b_{2}\). Однак, це, ймовірно, два різних значення\(k\), тому ми повинні дати їм різні імена, якщо ми хочемо говорити про обидва з них одночасно. Отже, назвемо перший\(k_{1}\) і другий\(k_{2}\):

• існує\(k_{1} \in \mathbb{Z}\), такий, що\(a k_{1}=b_{1}\), і
• існує\(k_{2} \in \mathbb{Z}\), таке, що\(a k_{2}=b_{2}\).

Щоб показати\(a \mid\left(b_{1}+b_{2}\right)\), ми хочемо знайти деякі\(k \in \mathbb{Z}\), такі, що\[a k \stackrel{?}{=} b_{1}+b_{2} .\]
Оскільки\(b_{1}+b_{2}=a k_{1}+a k_{2}=a\left(k_{1}+k_{2}\right)\), це означає, що ми хочемо\[a k \stackrel{?}{=} a\left(k_{1}+k_{2}\right) .\]
Так що зрозуміло, що ми повинні дозволити\(k = k_{1} + k_{2}\).

Доказ

Оскільки, за припущенням, а є дільником обох\(b_{1}\) і\(b_{2}\), існують\(k_{1}, k_{2} \in \mathbb{Z}\), такі, що\(a k_{1}=b_{1}\) і\(a k_{2}=b_{2}\). Нехай\(k = k_{1} + k_{2}\). Потім\(k \in \mathbb{Z}\) і\[a k=a\left(k_{1}+k_{2}\right)=a k_{1}+a k_{2}=b_{1}+b_{2} ,\]

так\(a\) є дільником\(b_{1} + b_{2}\), за бажанням.

Пропозиція\(5.1.8\).

Припустимо\(a, b \in \mathbb{Z}\). У нас є\(a \mid b\) iff\(a \mid −b\).

Подряпини.

(\(\Rightarrow\)) Оскільки\(a \mid b\), ми знаємо, що є деякі\(k\), такі, що\(ak = b\). Щоб показати\(a \mid −b\), ми хочемо знайти якийсь інший\(k\) - назвемо це\(k^{\prime}\) - таке\(a k^{\prime} \stackrel{?}{=}-b\). Так як\(-b=-(a k)=a(-k)\), це означає, що ми хочемо\(a k^{\prime} \stackrel{?}{=} a(-k)\). Так що ми повинні дозволити\(k^{\prime} = −k\).

(\(\Leftarrow\)) Оскільки\(a \mid −b\), ми знаємо, що є деякі\(k\), такі, що\(ak = −b\). Щоб показати\(a \mid b\), ми хочемо знайти деякі\(k^{\prime}\), такі, що\(a k^{\prime} \stackrel{?}{=} b .\) з тих пір\(−b = ak\), у нас є\(b = −(ak) = a(−k)\), так що ми можемо дозволити\(k^{\prime} = −k\). Це та ж робота, що і в proof of (\(\Rightarrow\)), і офіційне доказ, наведене нижче, дозволяє уникнути необхідності повторення цієї алгебри, звертаючись до результату, який ми вже довели.

Доказ

(\(\Rightarrow\)) За припущенням, є деякі\(k \in \mathbb{Z}\), такі що\(ak = b\). Потім\(−k \in \mathbb{Z}\), і у нас є\(a(−k) = −ak = −b\), Отже,\(a\) ділить\(−b\).

(\(\Leftarrow\)) Припустимо\(a \mid −b\). З попереднього пункту робимо висновок\(a \mid −(−b) = b\), що за бажанням.

Вправа\(5.1.9\).

Припустимо\(a, a^{\prime} , b, b^{\prime} \in \mathbb{Z}\).

1. Покажіть, що якщо\(a \mid b\) і\(a \mid b^{\prime}\), то\(a \mid b - b^{\prime}\).
2. Покажіть, що\(a \mid b\) якщо\(−a \mid b\).
3. Показати\(1 \mid b\).
4. Показати\(a \mid 0\).
5. Покажіть, що якщо\(0 \mid b\), то\(b = 0\).
6. Покажіть, що якщо\(a \mid b\), то\(a | bb^{\prime}\).
7. Покажіть, що якщо\(a \mid b\) і\(a^{\prime} \mid b^{\prime}\), то\(a a^{\prime} \mid b b^{\prime}\).

Пропозиція\(5.1.10\).

Припустимо\(a, b_{1}, b_{2} \in \mathbb{Z}\). Якщо\(a \mid b_{1}\) і\(a \nmid b_{2}\), то\(a \nmid\left(b_{1}+b_{2}\right)\).

Доказ

Припустимо\(a \mid b_{1}\) і\(a \nmid b_{2}\).

Припустимо\(a \mid\left(b_{1}+b_{2}\right)\). (Це призведе до протиріччя.) Тоді\(a\) є дільником обох\(b_{1} +b_{2}\) і (за припущенням)\(b_{1}\). Так Вправа\(5.1.9(1)\) говорить нам\[a \mid\left(\left(b_{1}+b_{2}\right)-b_{1}\right)=b_{2}\]
Це суперечить припущенню, що\(a \nmid b_{2}\).

Тому що це призводить до протиріччя, наша гіпотеза, яка\(a \mid\left(b_{1}+b_{2}\right)\) повинна бути помилковою. Це означає\(a \nmid\left(b_{1}+b_{2}\right) .\)

Загальновідомо, що 1 і −1 є єдиними цілими числами, зворотне число яких також є цілим числом. Мовою подільності це можна повторити як наступний корисний факт:\[\text { For any integer } n \text {, we have } n \mid 1 \text { iff } n=\pm 1 \text {. }\]

Вправа\(5.1.11\).

Доведіть:

1. Для всіх\(a \in \mathbb{Z}\), у нас є\(a \mid a\).
2. Для всіх\(a, b, c \in \mathbb{Z}\), якщо\(a \mid b\) і\(b \mid c\), то\(a \mid c\).
3. Неправда, що для всіх\(a, b \in \mathbb{Z}\) у нас є\(a \mid b\) iff\(b \mid a\).

Зауваження\(5.1.12\).

Три частини попередньої вправи показують, що подільність є «рефлексивною» та «перехідною», але не «симетричною». Ці терміни будуть визначені у Визначенні\(7.1.9\).

Вправа\(5.1.13\).

Припустимо\(a, b, x, y \in \mathbb{Z}\). Доведіть:

1. Якщо\(a \mid x\) і\(b \mid y\), то\(ab \mid 2xy\).
2. Якщо\(a, b \in \mathbb{N}^{+}\), і\(a \mid b\), то\(a \leq b\).

Вправа\(5.1.14\).

Довести або спростувати кожне твердження.

1. Для всіх\(a, b_{1}, b_{2} \in \mathbb{Z}\), якщо\(a \nmid b_{1}\) і\(a \nmid b_{2}\), то\(a \nmid\left(b_{1}+b_{2}\right)\).
2. Для всіх\(a, b_{1}, b_{2} \in \mathbb{Z}\), якщо\(a \nmid b_{1}\) і\(a \nmid b_{2},\), то\(a \nmid b_{1} b_{2}\).
3. Для всіх\(a, b, c \in \mathbb{Z} \text {, }\) якщо\(a \nmid b\) і\(b \nmid c\), то\(a \nmid c\).
4. Для всіх\(a, b \in \mathbb{Z}\), якщо\(a \nmid b\), то\(a \nmid −b\).

5.1Б. Конгруентність по модулю\(n\).

Визначення\(5.1.15\).

Припустимо\(a, b, n \in \mathbb{Z}\). Ми говоримо\(a\), що конгруентний по\(b\) модулю\(n\) iff\(a − b\) ділиться на\(n\). Позначення для цього є:\(a \equiv b(\bmod n)\).

Приклад\(5.1.16\).

1. У нас є\(22 \equiv 0(\bmod 2)\),\(22 − 0 = 22 = 11 \times 2\) тому що кратна 2. (Більш загально, для\(a \in \mathbb{Z}\), можна показати, що\(a \equiv 0 (\bmod 2)\) iff\(a\) є парним.)
2. У нас є\(15 \equiv 1 (\bmod 2)\),\(15 − 1 = 14 = 7 \times 2\) тому що кратна 2. (Більш загально, для\(a \in \mathbb{Z}\), можна показати, що\(a \equiv 1 (\bmod 2)\) iff\(a\) є непарним.)
3. У нас є\(28 \equiv 13 (\bmod 5)\),\(28 − 13 = 15 = 3 \times 5\) тому що кратна 5.
4. Для будь-якого\(a, n \in \mathbb{Z}\), не важко помітити, що\(a \equiv 0 (\bmod n)\) iff\(a\) є кратним\(n\).

Вправа\(5.1.17\).

Заповніть кожну заготовку\(\equiv\) або\(\not \equiv\), якщо це доречно.

1. 14______5\((\bmod 2)\)
2. 14______5\((\bmod 3)\)
3. 14______5\((\bmod 4)\)
4. 14______32\((\bmod 2)\)
5. 14______32\((\bmod 3)\)
6. 14______32\((\bmod 4)\)

Вправа\(5.1.18\).

(«Конгруентність по модулю\(n\) є рефлексивним, симетричним і перехідним».) Нехай\(n \in \mathbb{Z}\). Доведіть:

1. Для всіх\(a \in \mathbb{Z}\), у нас є\(a \equiv a (\bmod n)\).
2. Для всіх\(a, b \in \mathbb{Z}\) у нас є\(a \equiv b (\bmod n)\) iff\(b \equiv a (\bmod n)\).
3. Для всіх\(a, b, c \in \mathbb{Z}\), якщо\(a \equiv b (\bmod n)\) і\(b \equiv c (\bmod n)\), то\(a \equiv c (\bmod n)\).

Вправа\(5.1.19\).

Припустимо\(a_{1} \equiv a_{2} (\bmod n)\) і\(b_{1} \equiv b_{2} (\bmod n)\). Показати:

1. \(a_{1}+b_{1} \equiv a_{2}+b_{2}(\bmod n)\).
2. \(a_{1}-b_{1} \equiv a_{2}-b_{2}(\bmod n)\).
3. \(a_{1} b_{1} \equiv a_{2} b_{2}(\bmod n)\). [Підказка:\(a_{1} b_{1}-a_{2} b_{2}=a_{1}\left(b_{1}-b_{2}\right)+\left(a_{1}-a_{2}\right) b_{2}\).]

Дітей вчать, що якщо число\(a\) розділити на число\(n\), то може бути залишок, але залишок завжди менше\(n\). Ця ідея говориться точніше в наступній теоремі:

Теорема\(5.1.20\) (Division Algorithm).

Припустимо\(a, n \in \mathbb{Z}\), і\(n \neq 0\). Тоді існують унікальні цілі числа\(q\) і\(r\) в\(\mathbb{Z}\), такі, що:

1. \(a = qn + r\), і
2. \(0 \leq r < |n|\).

Визначення\(5.1.21\).

У ситуації\(5.1.20\) Теореми число\(r\) називається залишком при\(a\) діленні на\(n\).

Наступна вправа розкриває тісний зв'язок між конгруентністю та залишком.

Вправа\(5.1.22\).

Припустимо\(a, b, n \in \mathbb{Z}\) (і\(n \neq 0\)).

1. \(r\)Дозволяти бути залишок\(a\), коли ділиться на\(n\). Показати\(a \equiv r (\bmod n)\).
2. Покажіть, що\(a \equiv b (\bmod n)\) iff\(a\) і\(b\) мають однаковий залишок при діленні на\(n\).

Зауваження\(5.1.23\).

З другої половини частин (1) і (2) Прикладу ми бачимо\(5.1.16\), що кожне ціле число конгруентне або 0 або 1 по модулю 2 (а не обидва).

\(n\)є рівним вимкненням\(n \equiv 0 (\bmod 2)\).
\(n\)є непарним вимкненням\(n \equiv 0 (\bmod 2)\).

Вправа\(5.1.22(1)\) узагальнює це до конгруентності чисел по модулю, відмінних від 2: якщо\(n \equiv \mathbb{N}^{+}\), то кожне ціле число конгруентне (по модулю\(n\)) до деякого числа в\(\{0,1,2, \ldots, n-1\}\).

Приклад\(5.1.24\).

Давайте покажемо, що якщо\(n\) непарний, то\(9n+ 6\) теж непарний. Щоб переконатися в цьому, зверніть увагу, що:

• \(9 \equiv 1 (\bmod 2)\), тому що\(9 = 4(2) + 1\),
• \(n \equiv 1 (\bmod 2)\), тому що\(n\) це непарно, і
• \(6 \equiv 0 (\bmod 2)\), тому що\(6 = 3(2) + 0\).

Тому, використовуючи Вправа\(5.1.19\), ми маємо\(9n + 6 \equiv (1)(1) + 0 \equiv 1 (\bmod 2)\).

Цей же метод можна застосувати в наступних вправах:

Вправа\(5.1.25\).

Нехай\(n \in \mathbb{Z}\).

1. Показ\(6n + 3\) непарний.
2. Покажіть,\(n\) що якщо парне, то\(5n + 3\) непарне.
3. Покажіть, що якщо\(n\) непарний,\(5n + 3\) то парний.

Пропозиція\(5.1.26\).

Нехай\(n \in \mathbb{Z}\). Тоді\(n^{2} + n\) навіть.

Доказ

З зауваження\(5.1.23\), ми знаємо, що\(n\) є конгруентним або 0 або 1 по модулю 2. Ці дві можливості ми розглядаємо як окремі випадки.

Випадок 1. Припустимо\(n \equiv 0 (\bmod 2)\). За припущенням цього випадку ми маємо\(n = 2q\), для деяких\(q \in \mathbb{Z}\). Тому\[n^{2}+n=(2 q)^{2}+2 q=4 q^{2}+2 q=2\left(2 q^{2}+q\right)\]
ділиться на 2.

Випадок 2. Припустимо\(n \equiv 1 (\bmod 2)\). За припущенням цього випадку ми маємо\(n = 2q + 1\), для деяких\(q \in \mathbb{Z}\). Тому\[n^{2}+n=(2 q+1)^{2}+(2 q+1)=\left(4 q^{2}+4 q+1\right)+(2 q+1)=4 q^{2}+6 q+2=2\left(2 q^{2}+3 q+1\right)\]
ділиться на 2.

Вправа\(5.1.27\).

Нехай\(n \in \mathbb{Z}\).

1. Покажіть,\(n\) що якщо рівний, то\(n^{2} \equiv 0 (\bmod 4)\). [Підказка: У нас є\(n = 2q\), для деяких\(q \in \mathbb{Z}\).]
2. Покажіть,\(n\) що якщо непарно, то n 2 ≡ 1 (мод 8). [Підказка: У нас є n = 2q + 1, для деяких q Z.]
3. Покажіть,\(n^{2}\) що якщо рівний,\(n\) то рівний.

5.1C. Приклади ірраціональних чисел.

Кожне раціональне число є дійсним числом (іншими словами\(\mathbb{Q} \subset \mathbb{R}\)), але, можливо, не настільки очевидно, що деякі дійсні числа не є раціональними (іншими словами\(\mathbb{R} \not \subset \mathbb{Q}\)). Такі цифри, як кажуть, нераціональні. Ми зараз наведемо один з найпростіших прикладів ірраціонального числа.

Пропозиція\(5.1.28\).

\(\sqrt{2}\)є нераціональним.

Доказ

ЗА ПРОТИРІЧЧЯМ.

Припустимо\(\sqrt{2}\), це раціонально. (Це призведе до протиріччя.) За визначенням це означає\(\sqrt{2}=a / b\) для деяких\(a, b \in \mathbb{Z}\), с\(b \neq 0\). Зводячи до найнижчих термінів, ми можемо припустити, що\(a\) і не\(b\) мають загальних факторів. Зокрема, У\[\text { it is not the case that both } a \text { and } b \text { are even. }\]
нас\[\frac{a^{2}}{b^{2}}=\left(\frac{a}{b}\right)^{2}=\sqrt{2}^{2}=2 ,\]
\(a^{2}=2 b^{2}\) так навіть. Тоді Вправа\(5.1.27(3)\) говорить нам, що\[a \text { is even, }\]
так ми маємо\(a = 2k\), для деяких\(k \in \mathbb{Z}\). Тоді\[2 b^{2}=a^{2}=(2 k)^{2}=4 k^{2} ,\]
\(b^{2} = 2k^{2}\) так навіть. Тоді Вправа\(5.1.27(3)\) говорить нам, що\[b \text { is even. }\]
Ми зараз показали, що\(a\) і\(b\) є рівними, але це суперечить факту, згаданому вище, що це не так, що\(b\) обидва\(a\) і рівні.

Вправа\(5.1.29\).

1. Для\(n \in \mathbb{Z}\), показати, що якщо\(3 \nmid n\), то\(n^{2} \equiv 1(\bmod 3)\).
2. Покажіть,\(\sqrt{3}\) що нераціонально.
3. Чи\(\sqrt{4}\) нераціонально?

Зауваження\(5.1.30\).

\(\pi=3.14159 \ldots\)Знамениті\(e=2.71828 \ldots\) цифри також нераціональні, але ці приклади набагато складніше довести, ніж Пропозиція\(5.1.28\).