2.1: Смак теорії чисел

Перш ніж приступити до роботи, переконайтеся, що ви прочитали главу 1, яка задає тон для роботи, яку ми почнемо робити тут. Крім того, вам може знадобитися прочитати Додаток А: Елементи стилю для доказів. Як зазначено в кінці розділу 1.5, вам рекомендується періодично переглядати цей додаток, коли ви просуваєтесь у книзі, оскільки деякі вказівки спочатку можуть не мати сенсу або здаватися релевантними.

Важливо зазначити, що ми пірнаємо в голові спочатку тут. Коли ми починаємо, ми будемо покладатися на вашу інтуїцію та попередній досвід роботи з доказами. Це навмисно. Те, що ви, ймовірно, зіткнетеся з загальним розумінням того, що тягне за собою доказ, але ви, можливо, не зможете сформулювати більш тонкі деталі, які ви робите і не розумієте. Там будуть деякі тонкі проблеми, з якими ви зіткнетеся, і однією з наших цілей буде з'ясувати якомога більше з них. Нам потрібно відкалібрувати і розвивати інтелектуальну потребу в структурі. Вам рекомендується просто спробувати свої сили в написанні доказів проблем у цьому розділі, не надто турбуючись про те, чи «робите ви це правильно». У розділі 2.2 ми почнемо спочатку і почнемо розробляти формальну основу для матеріалу, що залишилася в книзі. Після того, як ви придбаєте більше досвіду та краще розумієте, що тягне за собою доказ, вам слід розглянути можливість повернення до цього розділу та перегляду ваших перших спроб написання доказів. А поки подивіться, що ви вмієте!

У цьому розділі ми познайомимо з основами галузі математики під назвою теорія чисел, яка присвячена вивченню властивостей цілих чисел. Цілі числа - це набір чисел, заданих\[Z:={...,−3,−2,−1,0,1,2,3,...}.\]

Колекція натуральних чисел також має спеціальну назву. Безліч натуральних чисел задається\[N:={1,2,3,...}.\]

Деякі математики (зокрема, теоретики набору) включають 0 в N, але це не буде нашою умовністю. Якщо ви уважно подивитеся на два набори, які ми визначили вище, ви помітите, що ми писали\(:=\) замість =. Використовуємо: =, щоб означати, що символ або вираз зліва визначено рівним виразу праворуч. Символ R використовується для позначення безлічі всіх дійсних чисел. Ми не будемо формально визначати реальні числа, а натомість покладатися на вашу попередню інтуїцію і розуміння.

Тому що ви так знайомі з багатьма з властивостей цілих чисел і дійсних чисел, одне з питань, які ми будемо натикатися на це знаючи, які факти ми можемо сприймати як належне. Як загальне правило, ви повинні намагатися використовувати надані визначення, не надто покладаючись на ваші попередні знання. Важливий порядок, в якому ми розвиваємо речі.

У математиці поширена практика використання символу в\(∈\) якості абревіатури для фрази «є елементом» або іноді просто «в». Наприклад, математичний вираз «n Z» означає «n - елемент цілих чисел». Однак слід подбати про те, як використовується цей символ. Ми будемо використовувати лише символ «» у виразах форми\(a ∈ A\), де A - множина, а a - елемент A. Ми напишемо вирази на\(a,b ∈ A\) кшталт скорочень для «a A та b A». Слід уникати написання таких фраз, як «a - це число A» та «n цілих чисел».

Ми зараз зіткнемося з нашим найпершим визначенням. У математиці визначення - це точне і однозначне опис значення математичного терміна. Він характеризує значення того чи іншого слова, надаючи всі властивості і тільки ті властивості, які повинні бути істинними. Перегляньте Додаток B для списку інших математичних термінів, з якими ми повинні бути знайомі.

Визначення 2.1. Ціле число n парне, якщо n = 2k для деякого k Z. ціле число n непарне, якщо n = 2k+ 1 для деякого k Z.

Зверніть увагу, що ми обрамляли визначення «парного» в терміні множення на відміну від ділення. При вирішенні теорем і проблем, пов'язаних з парними або непарними, обов'язково використовуйте наші формальні визначення, а не деякі відомі властивості подільності. Наразі вам слід уникати аргументів, які включають такі твердження, як «парні числа не мають залишку при діленні на два» або «остання цифра парного числа 0, 2, 4, 6 або 8». Також зверніть увагу, що поняття парного і непарного відносяться до нульових і негативних чисел. Зокрема, нуль дорівнює навіть тому, що 0 = 2 · 0, де варто підкреслити, що виникнення 0 з правого боку рівняння є цілим числом. Як інший приклад, ми бачимо, що −1 є непарним, оскільки −1 = 2 (−1) + 1. Незважаючи на те, що −1 = 2 (−1/2), це не означає, що −1 також є навіть, оскільки −1/2 не є цілим числом. Для решти цього розділу ви можете припустити, що кожне ціле число є парним або непарним, але ніколи не обидва.

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

Теорема 2.2. Якщо n - парне число, то n ² - парне число.

Одна суть у доведенні наступної теореми включає з'ясування того, як описати довільну пару послідовних цілих чисел.

Теорема 2.3. Сума двох послідовних цілих чисел непарна.

Один навик, який ми хочемо розвинути, - це визначення того, чи є дане математичне твердження істинним чи хибним. Для того, щоб переконатися, що математичне твердження є помилковим, ми повинні надати конкретний приклад, коли оператор не вдається. Такий приклад називається зустрічнимприкладом. Зверніть увагу, що достатньо надати один приклад, щоб переконатися, що загальне твердження не відповідає дійсності. З іншого боку, якщо ми хочемо довести, що загальне математичне твердження вірно, зазвичай недостатньо надати лише один приклад, а то й сто прикладів. Такі приклади є лише свідченням того, що твердження вірно.

Проблема 2.4. Визначте, чи є кожне з наступних тверджень істинним чи хибним. Якщо твердження вірно, доведіть це. Якщо твердження неправдиве, наведіть контрприклад.

(а) Добуток непарного цілого і парного цілого числа непарне.

(b) Добуток непарного цілого і непарного числа непарне.

(c) Добуток парного цілого і парного цілого числа парне.

(d) Сума парного і непарного цілого числа непарна.

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

Визначення 2.5. Задано n, m Z, скажемо, що n ділить m, записано\(n|m\), якщо існує k Z такий, що m = nk. Якщо n|m, можна також сказати, що m ділиться на n або що n - множник m.

Проблема 2.6. Для n, m Z, як схожі наступні математичні вирази і чим вони відрізняються? Зокрема, кожне є реченням чи просто іменником?

(а) н|м

(б)\(\dfrac{m}{n}\)

(c) м/п

У цьому розділі, присвяченому теорії чисел, ми дозволяємо додавання, віднімання та множення цілих чисел. Загалом, ми уникаємо ділення, оскільки ціле число, розділене на ціле число може призвести до числа, яке не є цілим числом. Підсумок полягає в тому, що ми будемо уникати письма\(\dfrac{m}{n}\). Коли відчуєте бажання розділити, перейдіть на еквівалентну формулювання за допомогою множення. Це значно полегшить ваше життя при доведенні тверджень, пов'язаних з подільністю.

Теорема 2.7. Сума будь-яких трьох послідовних цілих чисел завжди ділиться на три.

Проблема 2.8. Нехай a, b, n, m Z. Визначте, чи є кожне з наступних тверджень істинним чи хибним. Якщо твердження вірно, доведіть це. Якщо твердження неправдиве, наведіть контрприклад.

(a) Якщо a|n, то a|mn.

(b) Якщо 6 ділить n, то 2 ділить n і 3 ділить n.

(c) Якщо ab ділить n, то a ділить n і b ділить n.

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

Наслідок 2.9. Якщо a, n Z такі, що a ділить n, то a ділить n ². Наступні дві теореми, швидше за все, вам знайомі.

Теорема 2.10. Якщо a, n Z такі, що a ділить n, то a ділить −n.

Теорема 2.11. Якщо a, n, m Z такі, що a ділить m і a ділить n, то a ділить m + n.

Зверніть увагу, що ми возитися з твердженнями виду «Якщо., то.». Твердження такої форми називаються умовними пропозиціями, які ми переглянемо в наступному розділі. Фраза, яка виникає після «Якщо», але перед «тоді» називається гіпотезою, тоді як фраза, яка виникає після «тоді», називається висновком. Наприклад, у задачі 2.8 (a) «a|n» є гіпотезою, тоді як «a|mn» - висновок. Зверніть увагу, що умовні пропозиції можуть бути написані і у вигляді «.. якщо.», де висновок пишеться перед «якщо», а гіпотеза після. Наприклад, ми можемо переписати проблему 2.8 (a) як «a|mn, якщо a|n». Хоча порядок гіпотези та висновку були скасовані у реченні, їх ролі не мали.

Всякий раз, коли ми стикаємося з умовним твердженням в математиці, ми хочемо отримати звичку запитувати себе, що відбувається, коли ми міняємо ролі гіпотези та висновку. Твердження, яке є результатом зміни ролей гіпотези та висновку в умовному твердженні, називається зворотним вихідним твердженням. Наприклад, зворотна задача 2.8 (a) - «Якщо a|mn, то a|n», що трапляється помилкою.Конверс теореми 2.2 дорівнює «Якщо n ² - парне число, то n - парне ціле число». Хоча це твердження вірно, воно не має такого ж значення, як Теорема 2.2.

Завдання 2.12. Визначте, чи вірно зворотне кожне з наслідків 2.9, теореми 2.10 та теореми 2.11. Тобто для a, n, m Z визначте, чи є кожне з наступних тверджень істинним чи хибним. Якщо твердження вірно, доведіть це. Якщо твердження неправдиве, наведіть контрприклад.

(a) Якщо a ділить n2, то a ділить n. (Конверс Слідство 2.9)

(b) Якщо a ділить −n, то a ділить n. (Конверс теореми 2.10)

(c) Якщо a ділить m + n, то a ділить m і a ділить n. (Конверс теореми 2.11)

Наступну теорему часто називають транзитивністю ділення цілих чисел.

Теорема 2.13. Якщо a, b, c Z такі, що a ділить b і b ділить c, то a ділить c.

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

Теорема 2.14. Якщо a, n, m Z такі, що a ділить m і a ділить n, то a ділить m − n.

Теорема 2.15. Якщо n Z таке, що n непарне, то 8 ділить n ² − 1.