1: Вступ
- Page ID
- 64686
Цілі числа - це будівельні блоки теорії чисел. Цей розділ містить кілька дуже простих і очевидних спостережень, починаючи з властивостей цілих чисел, і все ж докази, що стоять за цими спостереженнями, не такі прості. У цьому розділі ми введемо основні операції над цілими числами та деякі алгебраїчні визначення, які будуть необхідні для розуміння основних понять у цій книзі. Потім ми вводимо принцип упорядкування Ну, який стверджує в основному, що кожен набір натуральних чисел має найменший елемент. Доказ індукцією також представлений як ефективний метод доведення кількох теорем у всій книзі. Переходимо до визначення поняття подільності і алгоритму поділу. Потім введено елементарне, але фундаментальне поняття найбільшого спільного дільника (gcd) двох цілих чисел та евклідовий алгоритм знаходження НСД двох цілих чисел. Ми закінчуємо цю главу Лемою Ламе на оцінці кількості кроків в евклідовому алгоритмі, необхідному для пошуку НСД двох цілих чисел.
- 1.1: Алгебраїчні операції з цілими числами
- Тоді як множина всіх натуральних чисел, позначених N, визначається N= {1,2,3,4,...}. На Z існують дві основні двійкові операції, а саме додавання (позначається +) та множення (позначається на ⋅), які задовольняють деяким основним властивостям, з яких виникає будь-яка інша властивість для Z.
- 1.2: Принцип упорядкування свердловин та математична індукція
- У цьому розділі ми наведемо три основні інструменти, які часто використовуватимуться для доведення властивостей цілих чисел. Почнемо з дуже важливої властивості цілих чисел, що називається принцип упорядкування свердловин. Потім ми констатуємо те, що відоме як принцип голубної дірки, а потім ми переходимо до представлення важливого методу, який називається математичною індукцією.
- 1.3: Подільність та алгоритм поділу
- Ми зараз обговоримо поняття подільності і його властивості.
- 1.4: Представлення цілих чисел у різних базах
- У цьому розділі ми покажемо, як будь-яке натуральне число може бути записано в терміні будь-якого додатного базового цілого розширення унікальним способом. Зазвичай ми використовуємо десяткові позначення для представлення цілих чисел, ми покажемо, як перетворити ціле число з десяткового позначення в будь-яке інше додатне базове ціле число і навпаки. Використання десяткових позначень у повсякденному житті просто краще, оскільки у нас є десять пальців, що полегшує всі математичні операції.
- 1.5: Найбільший спільний дільник
- У цьому розділі ми визначимо найбільший спільний дільник (gcd) двох цілих чисел і обговоримо його властивості. Доведено, що найбільшим спільним дільником двох цілих чисел є лінійна комбінація цих цілих чисел.
- 1.6: Алгоритм Евкліда
- У цьому розділі ми опишемо систематичний метод, який визначає найбільший спільний дільник двох цілих чисел. Цей метод називається евклідовим алгоритмом.
- 1.7: Теорема кульгавого
- У цьому розділі наведено оцінку кількості кроків, необхідних для пошуку найбільшого спільного дільника двох цілих чисел за допомогою алгоритму Евкліда. Для цього нам доведеться ввести числа Фібоначчі заради доведення леми, яка дає оцінку зростання чисел Фібоначчі в послідовності Фібоначчі. Лема, яку ми доведемо, буде використана в доведенні теореми Ламе.