- •Введение
- •Библиография
- •Теория множеств
- •Множества и подмножества
- •Мощность множества
- •Операции над множествами
- •Декартово произведение
- •Круги Эйлера
- •Мультимножества
- •Бинарные отношения
- •Упорядоченные множества
- •Множества в информатике и программировании
- •Библиография
- •Комбинаторная теория
- •Правило сложения
- •Правило умножения
- •Метод включения и исключения
- •Перестановки
- •Размещения
- •Сочетания
- •Перестановки с повторениями
- •Размещения с повторениями
- •Сочетания с повторениями
- •Бином Ньютона и полиномиальная формула
- •Разбиения
- •Генерация всех перестановок
- •Генерация всех подмножеств
- •Генерация размещений без повторений
- •Генерация размещений с повторениями
- •Генерация сочетаний с повторениями
- •Генерация всех разбиений
- •Библиография
- •Теория графов
- •Основные понятия
- •Представление графов в компьютере
- •Матрица смежности
- •Матрица инцидентности
- •Список связности
- •Список рёбер
- •Обход графа в глубину
- •Обход графа в ширину
- •Маршруты, цепи и циклы
- •Связность
- •Сочленения
- •Мосты
- •Деревья
- •Эйлеровы графы
- •Гамильтоновы графы
- •Планарные графы
- •Покрытие и независимость
- •Библиография
- •Приложение А. Исчисление конечных сумм
- •Библиография
- •Приложение Б. Рекуррентные соотношения
- •Задача о ханойских башнях
- •Задача о разрезании пиццы
- •Задача Иосифа Флавия
- •Библиография
- •Приложение В. Элементы теории чисел
- •Делимость и кратность
- •Алгоритм Евклида
- •Простые числа
- •Сравнения
- •Библиография
- •Библиография
Приложение В. Элементы теории чисел |
41 |
Приложение В. Элементы теории чисел
Теория чисел – древнейший раздел математики. Ещё не так давно теория чисел носила название арифметика. Предметом изучения этой теории являются множества чисел: натуральные, целые, рациональные и вещественные числа. Теория чисел имеет много связей с другими разделами математики, такими как теория множеств, математический анализ, геометрия. Более того, теория чисел фактически явилась фундаментом для общей алгебры, предметом изучения которой являются так называемые алгебраические структуры. Для нас же важно то, что теория чисел имеет многочисленные приложения к различным разделам информатики и программирования, прежде всего таким как теория информации, кодирование и шифрование. Традиционно множество вещественных чисел рассматривается в математическом анализе и теории множеств, а вот множества натуральных, целых и рациональных чисел в силу их дискретности рассматриваются в дискретной математике.
Делимость и кратность
Пусть n и m , тогда говорят, что n делится на m, или m делит n, или m – делитель n,
если существует |
k такое, что n=m k , и обозначают это так: |
m n . Говорят также, что n |
кратно m , |
если существует k такое, что n=m k . |
Как видно, разница в |
определениях в том, что в случае кратности m может быть отрицательным числом и даже нулём. Например, справедливо, что 0 кратен 0, так как 0=0 k при любом k.
Наибольшим общим делителем (НОД) чисел n и m называется наибольшее целое число делящее как n так и m:
НОД (n, m)=max {k : k n иk m} .
Нетрудно доказать следующие свойства НОД (n, m) :
НОД (n, m)=НОД(m ,n)
НОД (k n ,k m)=k НОД (n ,m)
Можно также доказать, что НОД(n, m) делится на любой общий делитель чисел n и m.
Два натуральных числа n и m называются взаимно простыми, если НОД (n, m)=1 . Другими словами, n и m не имеют общих делителей кроме единицы.
Алгоритм Евклида
Для нахождения НОД(n, m) ещё Евклидом был придуман алгоритм, основанный на следующей рекуррентной зависимости:
НОД (n,0)=n
НОД (n ,m)=НОД (m ,n mod m),n≥m .
Для получения НОД(n, m) нужно последовательно применять рекуррентное соотношение НОД (n, m)=НОД(m ,nmod m) до тех пор, пока не сработает терминальное условие
НОД (n,0)=n .
Простые числа
Натуральное число, большее единицы, называется простым, если оно имеет ровно два делителя: единицу и самое себя. Числа, большие единицы и не являющиеся простыми, называют составными. Число 1 не является ни простым, ни составным.
Число является простым тогда и только тогда, когда оно взаимно просто со всеми меньшими натуральными числами.
42 |
Симоненко Е.А. Дискретная математика. Лекции |
Ещё Евклид доказал, что множество простых чисел бесконечно.
Любое натуральное число, большее единицы, представимо в виде произведения простых чисел. Такое представление единственно с точностью до порядка сомножителей.
Для доказательства, что какое-то натуральное число является простым, необходимо доказать, что оно не делится ни на одно меньшее его число, кроме 1.
Например, докажем, что 31 – простое число. Будем перебирать последовательно все потенциальные делители от 2 до 30 и проверять на делимость (здесь mod означает операцию взятия остатка от деления):
31mod 2=1 |
31 mod 6=1 |
31mod 3=1 |
… |
31mod 4=3 |
31 mod 29=2 |
31mod 5=1 |
31 mod 30=1 |
Из примера хорошо видно, что проверив делимость на 2, не нужно проверять делимость на 4, на 6 и так далее, проверив делимость на 3, не нужно проверять делимость на 6 и так далее. Более того, если хорошо подумать, то нет надобности проверять на делимость все числа, а только те, что меньше определённого значения, зависящего от проверяемого числа. Подумайте, что это за значение. Не следует также продолжать проверять делимость, если нам уже встретился делитель.
Для вычисления ряда простых чисел от 1 до некоторого n нужно последовательно перебирать все числа промежутка [1,n] и доказывать, что они являются простыми или составными. Если n невелико, то можно воспользоваться методом решета. Идея метода заключается в том, что мы заводим массив длины n, и при обнаружении очередного простого числа, оставляем в этом массиве по индексу, соответствующему найденному числу, отметку, что это простое число, а для всех кратных ему – пометку, что число составное. Это даёт нам две вещи: вопервых, при проверке очередного числа на простоту мы можем проверять его делимость только на раннее найденные простые числа; во-вторых, мы можем пропускать числа уже имеющие отметку, что они составные.
Найдём все простые числа от 2 до 20:
2 – простое; далее пропускаем числа 4, 6, 8, 10, 12, 14, 16, 18, 20; 3 – простое; далее пропускаем числа 6, 9, 12, 15, 18; 5 – простое; далее пропускаем числа 10, 15, 20; 7 – простое; далее пропускаем число 14; 11 – простое; 13 – простое; 17 – простое; 19 – простое.
Благодаря решету, мы избавили себя от проверки одиннадцати чисел из девятнадцати!
Сравнения
Говорят, что a сравнимо с b по модулю m ( a ,b ,m ), если их разность делится на m: a−b m . В этом случае пишут a≡b(mod m) .
Приложение В. Элементы теории чисел |
43 |
Можно доказать, что два числа сравнимы по модулю m тогда и только тогда, когда они имеют одинаковые остатки от деления на m.
Справедливы следующие свойства:
a≡a (mod m)
a≡b(mod m) b≡a(mod m)
a≡b(mod m),b≡c(mod m) a≡c(mod m)
a1≡b1(mod m),a2≡b2(mod m) a1+a2≡b1+b2 (mod m) a1≡b1(mod m),a2≡b2(mod m) a1 a2≡b1 b2(mod m)
Библиография
Об элементах теории чисел можно прочитать в [Грэхем, Кнут, Паташник], [Краснов, Киселёв]. Развёрнутое изложение теории чисел в [Виноградов].