#+TITLE: Алгоритмы алгебры и теории чисел
#+AUTHOR: Андрей Гущин
#+LATEX_CLASS: Lecture
#+LATEX_HEADER: \usepackage{../preamble}

# Лекция 1 (08.09.22)
* Делимость в кольце целых чисел

Множество натуральных чисел можно определить с помощью аксиомы Пеано
1. $1 \in N$
2. $\forall a \in N \; \existsonly a^+$
3. $\forall a \in N \; a^+ \ne 1$
4. $a^+ = b^+ \implies a = b$
5. Если нек подмножество n входящее в мнво нат чисел и оно содержит единицу
   и для нек нат $a$ существует последующее число содержащееся в $n$,
   то эти множества совпадают

На этих аксиомах строятся вся арифметика натуральных чисел,
то есть любой паре натуральных чисел можно однозначно сопоставить число,
которое будет являться натуральным. При этом будут вып 4 условия
1. a + 1  = a^+
2. сумма будет ассоц
3. сумма будет коммут
4. сумма будет дистрибутивна

Каждой паре нат чисел можно однозн сопост произведение, которое также
будет являться натуральным числом. При этом также будут выполняться 6
условий
1. a \cdot 1  = a^+
2. a \cdot b^+ = ab + a
3. сумма будет ассоц
4. сумма будет коммут
5. сумма будет дистрибутивна
6. ...

Из аксиом 2 и 4 следует что множ нат чисел линейно и упорядочено.

Из множества нат чисел построим множество целых чисел

Опр. Множество целых чисел будем определять как объединение множества натуральных чисел
     множ отриц нат чисел и нуля. Обозначается буквой Z. На множестве целых чисел определяются
     операции сложения и умножения и задаются теми же правилами, что и для натуральных чисел.

Опр. Пусть над нек множеством \Omega некоторой произвольной природы определены операции сложения
     и умножения. Тогда это множество называется кольцом, если выполняются следующие условия:
     1. Сложение коммутативно
     2. Сложение ассоциативно
     3. Существует нулевой элемент, принадлежащий этому множеству такой, что a + 0 = a
     4. \forall a \in \Omega существует противоположный ему элемент, такой, что a + -a = 0
     5. Умножение должно быть дистрибутивно относительно сложения: a * (b + c) = (a * b) + (a * c)

- Если в кольце умножение коммутативно, то кольцо называется коммутативным.
- Если в кольце умножение ассоциативно, то кольцо называется ассоциативным.
- Если в кольце существует единичный элемент e, такой что a * e = e * a = a, то кольцо
  называется кольцом с единицей
- Если в ассоциативном коммутативном кольце с единицей для любого элемента a \ne 0, такой,
  что a * a^-1 = a^-1 * a = e, то такое кольцо будет называться полем
- Следует ответить, что множество натуральных чисел является ассоциативным коммутативным кольцом с единицей

** Делимость целых чисел

Пусть a и b произвольные целые числа и пусть существует нек целое число q, что a = b * q. Тогда можно сказать,
что число a делится на число b. (Записывается как три точки)

Свойства делимости
1. Каждое число a делится на единицу и делится на само себя
2. Отношение делимости транзитивно
3. Если a и b делится на c, то их сумма, разность и произведение на любое
   произвольное целое число также будет делиться на c.
4. Пусть дано равенство a_1 + a_2 + \dots + a_m = b_1 + b_2 + \dots + b_n в
   котором все члены кроме одного делятся на c. Тогда этот оставшийся член также будет делиться на c.
5. Пусть a и b целые числа. Если 

Опр. Пусть a и b целые числа и b \ne 0 и a = bq + r, где r = 0->b, то число q называется неполным частным
     или просто частным, а число r является остатком от деления числа a на b.

Теорема. Пусть a и b произвольные числа и b > 0. Частное и остаток от деления a
         на b существуют и определены однозначно.