Лекция 01. Теоремы делимости и алгоритм Евклида

• Теория чисел - важная наука, изучающая свойства целых чисел.  

• Начнем с простых вещей, таких как целая часть числа.  

• Целая часть числа - это максимальный элемент множества целых чисел, меньших или равных данному числу.  

• Дробная доля числа - это разность между числом и его целой частью.  

• График функции целой части числа - это лестница, где в точках 0, 1, 2 и т.д. значения функции равны нулю.  

• График дробной доли числа - это периодическая функция, всегда меньшая единицы.  

• Верхняя целая часть числа - это минимум всех целых чисел, больших или равных данному числу.  

• График верхней целой части числа - это функция, где в точках 0 и -1 значения равны нулю.  

• Верхняя целая часть числа от 0.5 равна 1.  

• Расстояние до ближайшего целого числа - это минимум разности между данным числом и всеми целыми числами.  

• График расстояния до ближайшего целого числа показывает, что это функция, где в точках 0 и 1 значения равны нулю.  

• Расстояние до ближайшего целого числа определено однозначно, кроме случаев, когда дробная часть числа равна 1/2.  

• Упражнение 1: Выразить ближайшее целое число через дробную долю.  

• Упражнение 2: Доказать неравенство треугольника для расстояния до ближайшего целого числа.  

• Рекомендованные книги: "Теория чисел" Нестеренко, "Теория чисел" Бухштаба, "Основы теории чисел" Виноградова.  

• Теория чисел изучает свойства целых чисел, включая деление и делимость.  

• Определение делимости: число a делит число b, если оно является делителем b.  

• Примеры делимости: 10 делится на 5, 12 делится на 6 и т.д.  

• Первокурсников нужно переучивать, так как в университете используются другие обозначения.  

• В школе делитель пишут слева от делимого, а в университете - наоборот.  

• Это связано с математической культурой и не требует объяснений.  

• Обсуждается теорема о делении с остатком.  

• Теорема утверждает, что для любого целого числа a и натурального числа b существует единственное целое число r, такое что a = b * k + r, где 0 ≤ r < b.  

• Доказательство теоремы будет строгим, чтобы показать степень строгости доказательств.  

• Доказательство существования начинается с проверки, что множество натуральных чисел не пусто.  

• Используется принцип Архимеда, чтобы доказать существование минимального элемента в множестве.  

• Доказывается, что существует элемент x, такой что a = b * k + x, где x < b.  

• Доказывается единственность, что если a = b * k + r и a = b * k' + r', то r = r'.  

• Разность r - r' делится на b, что доказывает, что r = r'.  

• Единственность доказана, что подтверждает правильность теоремы.  

• Рассматриваются два различных представления чисел.  

• Разность между числами должна делиться на b.  

• Если числа различны, их разность больше единицы, что противоречит условию.  

• Если p = p', то bk = bk', что доказывает единственность.  

• Доказательство теоремы отделения с остатком.  

• Введение понятия "теоремы" вместо "теоремы".  

• Объяснение необходимости строгости в доказательствах.  

• Введение теоремы с отрицательным остатком.  

• Определение a = bk + r, где r - остаток.  

• Объяснение дробной доли a/b и формулы для r.  

• Введение теоремы с ближайшим целым.  

• Определение a = bk2 + r2, где r2 принадлежит множеству.  

• Объяснение верхней и нижней целых частей.  

• Введение алгоритма Евклида для нахождения наибольшего общего делителя.  

• Определение множества общих делителей a и b.  

• Применение принципа Архимеда для нахождения максимального элемента.  

• Лемма о сохранении наибольшего общего делителя при делении с остатком.  

• Объяснение, почему НОД сохраняется при делении с остатком.  

• Применение леммы для всех видов деления с остатком.  

• Обсуждение теорем 1 и 2, их формулировок и доказательств.  

• Введение в алгоритмы Евклида и их применение.  

• Объяснение обычного алгоритма Евклида и его шагов.  

• Описание процесса деления с остатком.  

• Условие завершения алгоритма и нахождение наибольшего общего делителя НОД.  

• Обоснование, почему НОД равен последнему неравному нулю остатку.  

• Объяснение, что такое НОД и как он связан с остатками.  

• Представление чисел в виде многоэтажных дробей.  

• Введение понятия неполного частного и его значение.  

• Описание алгоритма Евклида с минусом.  

• Аналогия с цепной дробью и её особенности.  

• Введение нового следствия о представлении рациональных чисел в виде цепных дробей с минусами.  

• Обсуждение алгоритма Евклида с ближайшими целыми.  

• Применение третьего деления с остатком.  

• Преимущества третьего деления с остатком: промежутки для остатка и их значения.  

• Новое деление с остатком быстрее предыдущих.  

• Обсуждение скорости алгоритма Евклида.  

• Разложение числа в цепную дробь.  

• Введение в проблему Зарембы.  

• Задача: для любого натурального числа существует взаимно простое с ним число, такое, что все неполные частные не превосходят пяти.  

• Упражнение: решить проблему Зарембы для минусов.  

• Проблема Зарембы остается нерешенной задачей.  

• Упражнение можно решить за короткое время.  

• Обсуждение на семинарах и перерыв.