1.4: Визначення елементарної теорії чисел
- Page ID
- 64920
1.4.1: Парне і непарне
Якщо розділити число на,\(2\) і воно виходить парним (тобто без залишку) число вважається парним. Так що слово навіть пов'язане з поділом. Виявляється, поняття навіть краще зрозуміти через роздуми про множення.
Ціле число\(n\) навіть точно, коли є ціле число\(m\) таке, що\(n = 2m\).
Слід зазначити, що для цього визначення є якість «вулиці з двостороннім рухом» - справді з більшістю, якщо не всіма, визначеннями. Якщо число парне, то нам гарантується існування ще одного цілого числа вдвічі меншого. З іншого боку, якщо ми можемо показати, що ще одне ціле число половина як великий існує, то ми знаємо, що вихідне число парне. Ця двостороння означає, що визначення - це те, що відоме як біумовне, поняття, яке ми переглянемо в розділі 2.2.
Багато людей не вірять, що\(0\) слід вважати парним числом. Тепер, коли ми озброєні точним визначенням, ми можемо легко відповісти на це питання. Чи є\(x\) таке ціле число\(0 = 2x\)? Безумовно! нехай\(x\) теж буде\(0\). (Зауважте, що у визначенні нічого не було\(n\) сказано\(m\) і відрізнятися один від одного.)
Ціле число непарне, якщо воно не парне. Тобто серед цілих чисел є тільки дві можливості: парна або непарна. Ми також можемо визначити непарність без прив'язки до «навіть».
Ціле число\(n\) непарне саме тоді, коли є ціле число\(m\) таке, що\(n = 2m + 1\).
1.4.2: Десяткова та базова\(n\) позначення
Ви також можете визначити парні числа, враховуючи їх десяткове подання. Нагадаємо, що кожна цифра в десятковому поданні числа має значення, яке залежить від її положення. Наприклад, число\(3482\) дійсно означає\(3 · 10^3 + 4 · 10^2 + 8 · 10^1 + 2 · 10^0\). Це також відоме як позначення місця. Той факт, що ми використовуємо повноваження\(10\) в нашому місці позначення, ймовірно, пов'язано з тим, що більшість людей мають\(10\) пальці. Є можливість використовувати будь-який номер замість\(10\). В інформатиці є й\(3\) інші основи загального користування:\(2\),\(8\) і\(16\) — вони відомі (відповідно) як двійкові, вісімкові та шістнадцяткові позначення. При позначенні числа з використанням якоїсь іншої бази\(10\), крім, прийнято додавати індекс, що позначає базу. Так, наприклад,\(1011_2\) це двійкові позначення\(1 · 2^3 + 0 · 2^2 + 1 · 2^1 + 1 · 2^0\) або\(8 + 2 + 1 = 11\). Незалежно від того, яку базу ми використовуємо, крайня права цифра числа множить підняту базу до\(0\) -ої степені. Будь-яке число, підняте до\(0\) -ої степені\(1\), є, а крайня права цифра, отже, відома як цифра одиниць. Зараз ми готові дати деякі твердження, які еквівалентні нашому визначенню парності. Ці твердження справді не заслуговують позначення «теорема», вони є безпосередніми наслідками визначення.
Ціле число є навіть, якщо цифра одиниць у десятковому поданні одна з\(0\)\(2\),\(4\),\(6\) або\(8\).
Ціле число, навіть якщо цифра одиниць у його двійковому поданні є\(0\).
Для певних проблем природним є використання якоїсь певної нотаційної системи. Наприклад, остання теорема, як правило, вказує на те, що двійкові числа корисні в задачах, що стосуються парних і непарних. З огляду на, що є багато різних позначень, які нам доступні, очевидно, бажано мати в нашому розпорядженні засоби для перетворення між ними. Можна розробити загальні правила перетворення базового\(a\) числа в\(b\) base-number (де a і b довільні), але насправді зручніше вибрати «стандартну» базу (а оскільки ми люди будемо використовувати base-\(10\)) і розробити методи перетворення між довільною базою і «стандартний». Уявіть собі, що в не надто віддаленому майбутньому нам потрібно перетворити деякі числа з базової\(7\) системи, використовуваної семилопатевими амебазоїдами від Епсилона Ерідані III в базову\(12\) схему, прихильну додекатонам Альфа-Центавра IV. Нам знадобиться процедура перетворення base-\(7\) в base-\(10\) та інша процедура перетворення з base-\(10\) в base-\(12\). В епізоді School House Rock «Маленькі дванадцять пальців» вони описують базову\(12\) нумерацію таким чином, який зрозумілий для дітей початкової школи - цифри\(\{1, 2, 3, 4, 5, 6, 7, 8, 9, δ, \epsilon \}\), які вони використовують, останні дві цифри (які вимовляються «дек» і «ель») необхідні, оскільки нам потрібні одиничні символи для речі, які ми зазвичай позначаємо за допомогою\(10\) і\(11\).
Перетворення з якоїсь іншої бази в десяткову легко. Ви просто використовуєте визначення позначення місця. Наприклад, щоб знайти те, що\(451663_7\) представляє в десятковій системі, просто напишіть
\(4·7^5+5·7^4+1·7^3+6·7^2+6·7+3 = 4·16807+5·2401+1·343+6·49+6·7+3 = 79915.\)
(Все в рядку вище можна інтерпретувати як базове\(10\) число, і для base- не потрібні індекси\(10\).)
Перетворення з десяткової в якусь іншу базу складніше. Існує алгоритм під назвою «повторне ділення», який ми трохи вивчимо у вправах для цього розділу. На даний момент просто переконайтеся, що\(3δ2 \epsilon 7_{12}\) це також подання числа, більш умовно написаного як\(79915\).
1.4.3: Подільність
Поняття буття навіть має очевидне узагальнення. Припустимо, ми запитали, чи\(3\) розділили рівномірно на задане число. Імовірно, ми могли б зробити визначення того, що це означало бути трирівним, але замість того, щоб робити це (або займатися будь-яким подальшим пуннерством), ми натомість перейдемо до загального визначення. Потрібні позначення для ситуації, коли одне число ділиться рівномірно на інше. Існує багато способів описати цю ситуацію англійською мовою, але, по суті, лише один у «математиці», ми використовуємо вертикальну смугу, а не дріб. Дійсно, різниця між цією вертикальною смугою та символом\(|\) дробу (проти\(/\)) повинна бути сильно підкреслена. Вертикальна смуга при розміщенні між двома числами є символом, який задає питання: «Чи ділиться перше число рівномірно (тобто без залишку) на друге?» З іншого боку брусок фракції просить вас фактично провести якийсь поділ. Значення\(2 | 5\) false, тоді як значення\(2/5\) is\(.4\).
Як і у випадку з визначенням парності, виявляється, що найкраще думати про множення, а не ділення, роблячи формальне визначення цього поняття. Задано два будь-яких цілих числа\(n\) і\(d\) ми визначаємо символ\(d|n\) по
\(d|n\)саме тоді, коли\(∃k ∈ Z\) таке\(n = kd\)
У розмовній мові символ\(d|n\) можна перекласти різними способами:
- \(d\)є дільником\(n\).
- \(d\)ділиться\(n\) рівномірно.
- \(d\)є фактором\(n\).
- \(n\)є цілим числом, кратним\(d\).
Хоча, на сьогоднішній день найпопулярнішим способом вираження цього поняття є просто сказати «\(d\)ділить»\(n\).
1.4.4: Підлога і стеля
Припустимо, є ліфт місткістю в\(1300\) кілограми. Велика група чоловіків, які всі важать близько\(200\) кілограмів, хочуть піднятися в ньому. Скільки потрібно їздити за один раз? Це всього лише проблема поділу,\(1300/200\) дає\(6.5\) чоловікам їздити разом. Ну, очевидно, покласти половину людини на ліфт - це погана ідея - ми повинні просто округлити і дозволити\(7\) їздити разом? Ні, якщо рейтинг потужності\(1300\) фунта не має запасу міцності! Це приклад того виду проблеми, в якій використовується функція підлоги. Функція floor приймає дійсне число як вхідні дані і повертає наступне нижнє ціле число.
Припустимо, після вечірки у нас є\(43\) нерозкриті пляшки пива. Ми хотіли б зберігати їх у контейнерах, які містять\(12\) пляшки кожен. Скільки контейнерів нам знадобиться? Знову ж таки, це просто проблема поділу\(– 43/12 = 3.58333\). Значить нам знадобляться\(3\) коробки і ще\(7\) дванадцяті частини коробки. Очевидно, що нам дійсно потрібні\(4\) коробки — принаймні в одному буде невикористаний простір. У такій ситуації ми маємо справу з функцією стелі. Задано дійсне число, стельова функція округляє його до наступного цілого числа.
Обидві ці функції позначаються за допомогою символів, які дуже схожі на бари абсолютних значень. Різниця полягає в деяких невеликих горизонтальних штрихах.
Якщо\(x\) є дійсним числом, позначається його підлога\(\lfloor x \rfloor\), а його стеля позначається\(\lceil x \rceil\). Ось формальні визначення:
\(y = \lfloor x \rfloor\)саме коли\(y ∈ Z\) і\(y ≤ x < y + 1\).
\(y = \lceil x \rceil\)саме коли\(y ∈ Z\) і\(y − 1 < x ≤ y\).
В основному, визначення статі говорить, що\(y\) це ціле число, яке менше або дорівнює\(x\), але\(y + 1\) безумовно перевищує\(x\). Визначення стелі можна перефразувати аналогічно.
1.4.5: Div і мод
У наступному розділі ми обговоримо так званий алгоритм поділу - це може бути надмірним вбивством, оскільки ви, звичайно, вже знаєте, як робити поділ! Дійсно, в США довгий поділ зазвичай вперше вивчається в другій половині початкової школи, і проблеми поділу, які не стосуються залишку, можуть бути знайдені вже в першому класі. Тим не менш, ми збираємося обговорити цей процес дуже докладно, оскільки він дає нам хорошу обстановку, в якій можна довести відносно легкі твердження. Припустимо, ви налаштовуєте задачу з довгим діленням, в якій ціле число\(n\) ділиться додатним дільником\(d\). (Якщо ви хочете розділити на від'ємне число, просто розділіть на відповідне додатне число, а потім киньте додатковий знак мінус на кінці.)
\( \;\;\;\underline{\;\;q\;\;\;} \\ d| \;\;n \\ \;\;\;\;... \\ \;\;\underline{\;\;\;\;\;\;\;\;} \\ \;\;\;\;\;r\)
Нагадаємо, що відповідь складається з двох частин, частки і залишку\(r\).\(q\) Звичайно,\(r\) може бути нульовим, але також, найбільшим\(r\) може бути є\(d − 1\). Твердження, що ця відповідь однозначно існує, відоме як теорема частка-залишок:
Задані цілі числа\(n\) і\(d > 0\), є унікальні цілі числа\(q\) і\(r\) такі, що\(n = qd + r\) і\(0 ≤ r < d\).
Слова «div» і «mod», які з'являються в назві цього підрозділу, надають математичне скорочення для\(q\) і\(r\). А саме «\(n \text{ mod } d\)» - це спосіб вираження залишку\(r\), а «\(n \text{ div } d\)» - це спосіб вираження частки\(q\).
Якщо два цілих числа,\(m\) і\(n\), залишити той же залишок, коли ви ділите їх на\(d\), ми говоримо, що вони конгруентні по модулю\(d\). Можна висловити це письмово\(n \text{ mod } d = m \text{ mod } d \), але зазвичай ми приймаємо стенографічне позначення.
\[n ≡ m (\text{mod } d).\]
Якщо хтось знаходиться в контексті, в якому абсолютно зрозуміло, що\(d\) таке, допустимо просто написати\(n ≡ m\).
Операція «\(\text{mod}\)» використовується досить багато в математиці. Коли ми робимо обчислення по модулю деяке число\(d\), (це відомо як «модульна арифметика» або, іноді, «арифметика годинника») деякі дуже приємні властивості «\(\text{mod}\)» стануть в нагоді
\[x + y \text{ mod } d = (x \text{ mod } d + y \text{ mod } d) \text{ mod } d\]
і
\[x · y \text{ mod } d = (x \text{ mod } d · y \text{ mod } d) \text{ mod } d.\]
Ці правила означають, що ми можемо або спочатку виконати операції, потім зменшити відповідь,\(\text{mod } d\) або ми можемо\(\text{mod } d\) спочатку зменшити, а потім зробити операції (хоча нам, можливо, доведеться зробити ще один раунд скорочення\(\text{mod } d\)).
Наприклад, якщо ми працюємо\(\text{mod } 10\), і хочемо обчислити\(87·96 \text{ mod } 10\), ми можемо замість цього просто обчислювати\(7 · 6 \text{ mod } 10\), який є\(2\).
1.4.6: Біноміальні коефіцієнти
«Біном» - це многочлен з\(2\) термінами, наприклад\(x + 1\) або\(a + b\). Числа, які з'являються як коефіцієнти, коли людина піднімає біноміал до певної потужності, є - досить дивно - відомі як біноміальні коефіцієнти.
Давайте подивимося на перші кілька повноважень\(a + b\).
\[\begin{array} (a + b)^0 &= 1 \\ (a + b)^1 &= a + b \\ (a + b)^2 &= a^2 + 2ab + b^2 \end{array}\]
Щоб пройти набагато далі другого харчування, потрібно трохи попрацювати, але спробуйте наступне
Помножити\((a+b)\) і для\((a^2 + 2ab+b^2)\) того, щоб визначити\((a+b)^3\). Якщо ви відчуваєте до цього, помножте на себе\((a^2+2ab+b^2)\) раз для того, щоб знайти\((a+b)^4\).
Оскільки нас цікавлять коефіцієнти цих поліномів, важливо зазначити, що якщо перед терміном не з'являється коефіцієнт, який означає, що коефіцієнт є\(1\).
Ці біноміальні коефіцієнти можуть бути розміщені в розташуванні, відомому як трикутник Паскаля 1, що забезпечує зручний спосіб обчислення малих біноміальних коефіцієнтів
Зверніть увагу, що в трикутнику є межа з обох сторін, що містять 1 і що числа на внутрішній стороні трикутника є сумою двох чисел над ними. Ви можете використовувати ці факти, щоб продовжити трикутник.
Додайте наступні два ряди до трикутника Паскаля на малюнку\(1.4.1\).
Біноміальні коефіцієнти позначаються за допомогою дещо дивного на вигляд символу. Позначається число в\(k\) -ій позиції в\(n\) рядку номер трикутника\(\binom{n}{k}\). Це виглядає трохи як дріб, але брусок фракції відсутній. Не кладіть його! Передбачається, що його не вистачає. У розмовній англійській мові ви говорите «\(n\)вибрати\(k\)», коли стикаєтеся з символом\(\binom{n}{k}\).
Існує формула для біноміальних коефіцієнтів — що приємно. В іншому випадку нам потрібно буде завершити досить величезний трикутник Паскаля, щоб обчислити щось на зразок\(\binom{52}{5}\). Формула передбачає факторіальні позначення. Просто щоб бути впевненим, що ми всі на одній сторінці, ми визначимо факторіали, перш ніж продовжити.
Символ для факторіалів є знак оклику після числа. Це лише коротка рука для вираження добутку всіх чисел аж до заданого. Наприклад,\(7!\) засіб\(1 · 2 · 3 · 4 · 5 · 6 · 7\). Звичайно, насправді немає необхідності писати початковий\(1\) - також, чомусь люди зазвичай пишуть товар у порядку зменшення\((7! = 7 · 6 · 5 · 4 · 3 · 2)\).
Формула для біноміального коефіцієнта дорівнює
\[\binom{n}{k} = \dfrac{n!}{k! · (n − k)!} \]
Наприклад
\[\binom{5}{3} = \dfrac{5!}{3! · (5 − 3)!} = \dfrac{1 · 2 · 3 · 4 · 5}{ (1 · 2 · 3) · (1 · 2)} = 10 \]
Трохи складніший приклад (і той, який люблять азартні гравці)
\[\begin{array} \binom{52}{5} &= \dfrac{52!}{5! · (52 − 5)!} \\ &= \dfrac{1 · 2 · 3 · · · · 52}{(1 · 2 · 3 · 4 · 5) · (1 · 2 · 3 · · · · 47)} \\ &= \dfrac{48 · 49 · 50 · 51 · 52}{1 · 2 · 3 · 4 · 5} \\ &= 2598960. \end{array}\]
Причина того, що азартний гравець може бути зацікавлений в кількості, яку ми щойно розрахували, полягає в тому, що біноміальні коефіцієнти роблять більше, ніж просто дають нам коефіцієнти в розширенні біноміального. Вони також можуть бути використані для обчислення того, скільки способів можна вибрати підмножину заданого розміру з набору. \(\binom{52}{5}\)Це кількість способів, за допомогою яких можна отримати\(5\) карткову руку з колоди\(52\) карт.
Є сім днів на тиждень. Скільки способів можна вибрати набір з трьох днів (на тиждень)
Вправи:
Ціле число\(n\\) є подвійно-парним, якщо воно парне, а ціле число\(m\) гарантовано існує, тому що\(n\) є парним. Це\(0\) подвійно-парний? Які перші\(3\) позитивні, подвійно-парні цілі числа?
Ділення цілого числа на два має цікаву інтерпретацію при використанні двійкових позначень: просто зрушити цифри вправо. Таким чином,\(22 = 10110_2\) при поділі на два дає\(1011_2\) який є\(8 + 2 + 1 = 11\). Як можна розпізнати подвійне парне ціле число з його двійкового подання?
Вісімкове подання цілого числа використовує степені\(8\) позначення на місці. Цифри вісімкового числа йдуть від\(0\) до\(7\), ніхто ніколи не бачить\(8\) 's або\(9\)' s. Як би ви представляли\(8\) і\(9\) як вісімкові числа? Яке вісімкове число приходить відразу після\(777_8\)? Що таке (десяткове) число\(777_8\)?
Один метод перетворення з десяткової в якусь іншу базу називається повторним діленням. Один ділить число на базу і записує залишок - один потім ділить частку, отриману на основу, і записує залишок. Продовжуйте ділити послідовні частки на основу, поки частка не буде меншою за основу. Перетворити\(3267\) на base-\(7\) за допомогою повторного ділення. Перевірте свою відповідь, використовуючи значення позначення base-\(7\) place. (Наприклад\(54321_7\) означає\(5 · 7^4 + 4 · 7^3 + 3 · 7^2 + 2 · 7^1 + 1 · 7^0\).)
Створіть теорему про вісімкове подання парних чисел.
У шістнадцятковому (базовому\(16\)) позначенні потрібні\(16\) «цифри», звичайні цифри використовуються для\(0\)\(9\) наскрізних, а літери\(\text{A}\) через\(\text{F}\) використовуються для отримання одиночних символів для\(10\) наскрізного\(15\). Першим\(32\) натуральним числом у шістнадцятковому вигляді є:
\(1,2,3,4,5,6,7,8,9,\text{A},\text{B},\text{C},\text{D},\text{E},\text{F},10,11,12,13,14,15,16,17,18,19,1\text{A},1\text{B},1\text{C},1\text{D},1\text{E},1\text{F},20\).
Запишіть наступні\(10\) шістнадцяткові числа після\(\text{AB}\).
Для перетворення між трьома основами, які найчастіше використовуються в інформатиці, ми можемо взяти двійковий як «стандартну» базу і конвертувати за допомогою таблиці пошуку. Кожна вісімкова цифра буде відповідати двійковій трійці, а кожна шістнадцяткова цифра буде відповідати\(4\) -кортежу двійкових чисел. Заповніть наступні таблиці. (Як перевірка,\(4\) -кортеж поруч\(A\) із таблицею для шістнадцяткової має бути\(1010\) - що приємно, оскільки\(A\) насправді\(10\) так, якщо ви читаєте, що як «десят-десять» це хороша допомога пам'яті.)
| вісімковий | двійковий |
|---|---|
| 0 | 000 |
| 1 | 001 |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 |
| шістнадцятковий | двійковий |
|---|---|
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| \(\text{A}\) | |
| \(\text{B}\) | |
| \(\text{C}\) | |
| \(\text{D}\) | |
| \(\text{E}\) | |
| \(\text{F}\) |
Скористайтеся таблицями з попередньої проблеми, щоб зробити наступні конверсії.
- Перетворити\(757_8\) на двійковий файл.
- Перетворити\(1007_8\) на шістнадцятковий.
- Перетворити\(100101010110_2\) на вісімкову.
- Перетворити\(1111101000110101_2\) на шістнадцятковий.
- Перетворити\(FEED_{16}\) на двійковий файл.
- Перетворити\(FFFFFF_{16}\) на вісімкову.
Спробуйте такі перетворення між різними системами числення:
- Перетворити\(30\) (base\(10\)) на двійковий.
- Перетворити\(69\) (base\(10\)) на базу\(5\).
- Перетворити\(12223\) на двійковий файл.
- \(12347\)Перетворити на базу\(10\).
- \(EEED_{15}\)Перетворити на базу\(12\). (Використовуйте\(\{1, 2, 3 . . . 9, d, e\}\) як цифри в базі\(12\).)
- Перетворити\(6789\) на шістнадцятковий.
Добре відомий факт, що якщо число ділиться на\(3\), то\(3\) ділить суму (десяткових) цифр цього числа. Чи вірний цей результат у базі\(7\)? Як ви вважаєте, цей результат вірний в будь-якій базі?
Припустимо, що\(340\) фунти піску необхідно помістити в мішки, що мають місткість\(50\) фунта. Напишіть вираз, використовуючи позначення підлоги або стелі для кількості необхідних мішків.
Правда чи брехня?
\(\lfloor \dfrac{n}{d} \rfloor < \lceil \dfrac{n}{d} \rceil \)
для всіх цілих чисел\(n\) і\(d > 0\). Підтримайте свою претензію.
Що таке цінність\(\lceil π \rceil^2 − \lceil π^2 \rceil\)?
Припускаючи символи\(n\)\(d\),\(q\) і\(r\) мають значення, як у теоремі частки-залишок (теорема\(1.4.3\)). Напишіть вирази для\(q\) і\(r\), з точки зору\(n\) та\(d\) використовуючи позначення підлоги та/або стелі.
Розрахуйте наступні величини:
- \(3 \text{ mod } 5\)
- \(37 \text{ mod } 7\)
- \(1000001 \text{ mod } 100000\)
- \(6 \text{ div } 6\)
- \(7 \text{ div } 6\)
- \(1000001 \text{ div } 2\)
Обчисліть наступні біноміальні коефіцієнти:
- \(\binom{3}{0}\)
- \(\binom{7}{7}\)
- \(\binom{13}{5}\)
- \(\binom{13}{8}\)
- \(\binom{52}{7}\)
У магазині морозива продаються такі смаки: шоколад, ваніль, полуниця, кава, масло пекан, м'ятна шоколадна крихта і малина. Скільки різних мисок морозива - з трьома ложками - вони можуть зробити?