0. Основные определения
Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
(http://ru.wikipedia.org/wiki/Взаимно_простые_числа)
1. НОК и НОД
Даны два любых натуральных числа.
По основной теореме арифметики их можно разложить единственным способом в произведение простых чисел:
Наименьшее Общее Кратное есть
Наибольший Общий Делитель есть
Как нетрудно видеть коммутативность, ассоциативность, идемпотентность операций вычисления НОК и НОД
сводится в выполнения этих свойств для операции min и max.
2. Основные свойства бинарных отношений
Определения отношений:
Рефлексивные - диагональ декартова квадрата множества содержится в отношении.
Иррефлексивные - диагональ декартова квадрата множества не содержится в отношении.
Симметричность отношения - R(x,y) => R(y,x)
Антисимметричность отношения - R(x,y) AND R(y,x) => x=y
Тразитивность отношения - R(x,y) AND R(y,z) => R(x,z)
Класс эквивалентности по отношению R для x - множество элементов эквивалентных x, т.е. [x] = {y:R(y,x)}
Т Множество классов эквивалентности образуют разбиение множества, любое разбиение множества представляет на нём
отношение эквивалентности. Классы эквивалентности совпадают с элементами разбиения.
Множества, все элементы которого попарно сравнимы - линейно упорядоченное множество.
Индутивно упорядоченное множество - множество которое содержит наименьший элемент. Всякая неубывающая последовательность имеет точную верхнюю грань.
Отображение F называют непрерывным если F(sup{ai})=sup{F(ai)}
Т Всякое непрерывное отображение индуктивно упорядоченного множества в себя имеет наименьшую неподвижную точку F(x)=x, и строится по алгоритму x(0) = 0; x(i+1) = F(x(i))
Т Множество {0,1}^w не есть счётное множество.
3. Основные алгебраические структуры
Группоид - любая алгебра с бинарной операцией.
Полугруппа - группоид с ассоциативной операцией (пример не ассоциативной операции векторное умножение векторов R^3)
Моноид - полугруппа с нейтральным элементом
Полурешётка - Полугруппа с коммутативной и идемпотентной операцией
Группа - моноид, в котором каждый элемент для бинарной операции имеет обратный.
Пример группы:
Мультипликативная группа Zp = {1,2,...,p-1} состаяющая из p-1 элементов и имеющая операцию умножение как умножение чисел по модулю p
Абелева Группа - коммутативная группа
Циклическая группа - группа каждый элемент которой есть некоторая целая степень образующего элемента в этой группе.
Циклическая группа в Zp, вместе с проблемой дискретного логарифмирования (суть проблемы в том, что непонятно как решать эту задачу с логарифмированием в поле Zp без перебора) используется как основа алгоритма Диффи-Хелмана.
Кольцо - алгебра в которой
-- По сложению элементы образуют коммутативную группу
-- По умножению образуют моноид
-- Умножение дистрибутивно относительно операции сложения.
Примеры:
> множество целых чисел с обычным сложением и умножением
> Zk {0,1,...,k-1} чисел с операциями сложенеием и умножением по модулю k, где k не обязательно простое число.
Кольцо без делителей нуля - область целостности.
Кольцо в которой по умножению элементы образуют группу - тело.
Коммутативное по умножению тело - поле.
Т Конечная область целостности является полем.
Пример использования теоремы:
В кольце Zp если p простое число то там нет делителей нуля, и значит Zp как конечная область целостности является полем.
Пример тела, не являющаяся полем - алгебра кватернионов.
Суть - упорядоченные пары комплексных чисел. С покомпонентным сложением, а умножением введенным как (a,b)*(c,d)=(ac - bd', ad+bc'). Штрих означает комплексное дополнение. Умножение ассоциативно, но не коммутативно.
Над кватернионами можно также строить упорядоченные пары, описанным способом. Введя то, что дополнение ((a,b))'=(a,-b'). Полученная алгебра называется алгеброй Кэли. Алгебра Кэли уже не является даже ассоциативной.
Т Можно доказать, что кроме
алгебры Комплексных чисел, алгебры Кватернионов, алгебры Кэли в некотором смысле не существует числовых бесконечных алгебр без делителей нуля.
Т Кольцо вычетов по модулю p, является полем тогда и только тогда когда p - простое число.
Теорема Лагранжа: Группа G содержит подгруппу H.
Все левые классы группы H по элементу a из G (множество {y:y=a*h, h из H}) образуют разбиение множества G. Причём все они равномощны самому H. В случае конечной группы из этого вытекает важное следствие - порядок группы делится нацело на порядок любой её подгруппы. Которую и называют Теоремой Лагранжа.
Доп. следствие: Любой элемент конечной группы в степени равной порядку группы, равен 1.
Малая Теорема Ферма:
Если целое N не делится на простое число P => то
Короткое док-во:
С помощью формулы бинома Ньютона, просто расписав полином, можно увидеть, что если "N не делится на P" то:
Порядок мультипликативной группы вычетов по модулю P (где P - простое число) равен P-1
=> Из Следствия из Теоремы Лагражна мы получим
Алгебра (+, *, 0, 1) называется полукольцом если имеет для алгебры следующее:
-- По сложению -- коммутативный моноид (а не группу как в кольце)
-- По умножению -- моноид (как и в кольце)
-- Имеет место дистрибутивность сложения относительно операции сложения
-- Выполняются аннулирующие свойство нуля.
Идемпотентное полукольцо - полукольцо в котором сложение идемпотентно (X+X=X)
Идемпотентное полукольцо, в которой любая последовательность элементов имеет точную верхнюю грань, и операция умножения сохраняет точные верхние грани -- замкнутое полукольцо.
Естественный числовой порядок для Идемпотентного полукольца -- x <= y <=> x+y=y
Решение уравнения x=ax+b и x=xa+b основываются на применении Теоремы о неподвижной точки.
Решением являются соответственно величины x=(a*)b и x=b(a*)
В полукольцу R+(min, summ) итерацию любого элемента равна единице полукольца, оно же значение ноль в смысле поля действительных числе.
Интересные моменты
Теорема Клини об эквивалентности регулярных языков и детерминированного конечного автомата была доказано Stephen Klini, Ph.D. аспирантом в Принстоне в 1934 году. (Р. Седжвик)
Ссылки
[1] МГТУ, XIX Белоусов А.И., Ткачев СБ. Дискретная математика.