- •Вопрос 1. Методы математических доказательств (метод непосредственной проверки, метод доказательства от противного, метод математической индукции).
- •2 Метод.
- •3 Метод.
- •Вопрос 2. Формула Бинома Ньютона.
- •Вопрос 3. Сочетания, размещения, перестановки. Теоремы о числе сочетаний, размещений и перестановок, их следствия.
- •Вопрос 4. Инверсии в перестановках. Чётные и нечётные перестановки при транспозиции.
- •Вопрос 5. Понятие множества. Основные операции на множествах. Свойства операций на множестве (ассоциативность, коммутативность, дистрибутивность). Декартово произведение множеств.
- •Вопрос 6. Отображения множеств. Свойства отображений.
- •Вопрос 7. Отношения на множестве, бинарные отношения. Отношения эквивалентности, отношения порядка.
- •Вопрос 8. Понятия группоида, полугруппы, группы и подгруппы. Совпадение нейтрального (единичного) и симметричного (обратного) элементов группы и подгруппы.
- •Вопрос 9. Подгруппа, порожденная подмножеством элементов группы.
- •Вопрос 10. Понятие наибольшего общего делителя (нод) и наименьшего общего кратного (нок) целых чисел. Условия существования и единственности нод. Взаимно простые числа и их свойства.
- •Вопрос 11. Алгоритм Евклида для целых чисел.
- •Вопрос 12. Представление нод двух чисел в виде их линейной комбинации:
- •Вопрос 13. Простые числа, их свойства. Основная теорема арифметики. Каноническое разложение целого числа.
- •Вопрос 14. Бесконечность множества простых чисел.
- •Вопрос 15. Понятие изоморфизма групп. Теорема о изоморфизме цикличных групп одного и того же порядка.
- •Вопрос 16. Критерий «быть подгруппой», следствия. Пересечение подгрупп.
- •Вопрос 17. Смежные классы. Теорема Лагранжа.
- •Вопрос18: Разложение подстановки в произведение независимых циклов. Цикловая структура подстановки.
- •Вопрос 19: Теоремы о гомоморфизме групп.
- •Вопрос 20. Обращение теоремы Лагранжа для циклических групп.
- •Вопрос 21. Классы сопряженных элементов, их свойства. Нормализатор элемента группы.
- •Вопрос 22. Группа биективных отображений множества (симметрическая группа). Определение группы подстановок. Сопряжённые элементы в симметрической группе.
- •Вопрос 23. Знакопеременная группа.
- •Вопрос 24. Циклические группы, их описание. Цикличность подгруппы циклической группы. Пример группы корней n-ой степени из единицы.
- •Вопрос 25. Порядок элемента конечной группы. Соотношения между порядком элемента и порядком группы.
Вопрос 9. Подгруппа, порожденная подмножеством элементов группы.
Пусть M - подмножество группы G, тогда символом (М) будем обозначать пересечение всех подгрупп, содержащих множество M. Это множество - подгруппа, порожденная множеством М: (М)= . Множество (М) состоит в точности из тех элементов, которые можно записать через элементы из М, используя операции умножения и взятия обратного элемента . Говорят, что М порождает подгруппу Н, если (М)=Н.
Вопрос 10. Понятие наибольшего общего делителя (нод) и наименьшего общего кратного (нок) целых чисел. Условия существования и единственности нод. Взаимно простые числа и их свойства.
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. (НОД(m, n))
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n. (НОК(m, n))
Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
Свойства:
-Числа a и b взаимно просты тогда и только тогда, когда выполняется одно из эквивалентных условий.
-Наибольший общий делитель a, b равен единице.
-Существуют целые x и y такие, что ax+by=1 (соотношение Безу).
-Любые два (различных) простых числа взаимно просты.
-Если a — делитель произведения bc, и a взаимно просто с b, то a — делитель c.
-Если числа a1,…, an — попарно взаимно простые числа, то НОК(a1,…, an) = |a1·…·an|. Например, НОК(9,11)=9*11=99
Вопрос 11. Алгоритм Евклида для целых чисел.
Вариант 1:
Пусть a и b — целые числа, не равные одновременно нулю, и последовательность чисел определена тем, что каждое rk — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
a = bq0 + r1
b = r1q1 + r2
r1 = r2q2 + r3
rk − 2 = rk − 1qk − 1 + rk
rn − 1 = rnqn
Тогда НОД(a,b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.
Существование таких r1,r2,..., то есть возможность деления с остатком m на n для любого целого m и целого , доказывается индукцией по m.
Корректность этого алгоритма вытекает из следующих двух утверждений:
1) Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).
Доказательство :
-
Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда a = t1 * k ; b = t2 * k; где t1 и t2 — целые числа из определения.
-
Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а r = a − bq = (t1 − t2 * q) * k (выражение в скобках есть целое число, следовательно, k делит r без остатка)
-
Обратное также верно и доказывается аналогично пункту 2 - любой делитель b и r так же является делителем a и b.
-
Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
-
В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
2) НОД(0,r) = r для любого ненулевого r (т.к. 0 делится на любое целое число, кроме нуля).
Проще сформулировать алгоритм Евклида так: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
Вариант 2:
Содержание алгоритма Евклида сводится к последовательному вычислению следующих равенств:
Действие алгоритма прекращается тогда, когда полученный остаток равен нулю; последний ненулевой остаток (rn) равен наибольшему общему делителю.