Алгебра
Это актуальные билеты по сессии в СУНЦ МГУ. Надеюсь, что они помогут вам сдать экзамен.
1. Делимость чисел
Для удобства мне же, я буду использовать странный символ для обозначения делимости.
1.1. Определение делимости
Если a делится на b, то мы всегда можем разложить a на множители b и q.
1.2. Теорема о делении с остатком
Для любых целых чисел a и b, где b не равно нулю, существуют единственные целые числа q и r, такие что a = bq + r, где 0 <= r < |b|.
Доказательство
1.3. Свойства делимости
1.3.1. Арифметические свойства
Доказательство
Этого не было на лекции, однако это обобщенное свойство.
Доказательство
Это свойство можно легко получить из Произведение-1.
Доказательство
Это свойство можно легко получить из Произведение-1.
Доказательство
1.3.2. Модуль делителя
Если a делится на m, но a не равен нулю, то |a| не меньше m.
Доказательство
1.3.3. Сравнимость по модулю
Сравнимость по модулю - это отношение, которое устанавливается между двумя целыми числами a и b, если их разность делится на m.
1.3.4. Классы вычетов
Класс вычетов - это множество целых чисел, которые дают одинаковые остатки при делении на m.
Множество вычетов - это множество всех классов вычетов.
1.4 Простые числа
1.4.1. Определение простого числа
Простое число - это натуральное число, которое делится только на 1 и на само себя.
Примеры
1.4.2. Определение взаимно простых чисел
Взаимно простые числа - это целые числа, которые не имеют общих делителей, кроме 1, -1.
1.4.3. Теорема о взаимно простых числах
Если a и b взаимно простые, то существуют такие целые числа x0 и y0, что ax0 + by0 = 1.
Доказательство
1.4.4. Простых чисел бесконечно много
Множество простых чисел бесконечно. Это можно доказать от противного.
Доказательство
1.4.5. Малая теорема Ферма
Если p - простое число, а a не делится на p, то a^(p-1) - 1 делится на p.
1.4.6. Теорема Вильсона
Число p - простое тогда и только тогда, когда (p-1)! + 1 делится на p.
1.4.7. Теорема Евклида
Наибольший общий делитель двух чисел равен наибольшему общему делителю остатка на деления большего делителя на меньший делитель и меньшего делителя.
Доказательство
1.5. Теорема о наибольшем общем делителе
Аналогично Теореме о взаимно простых числах, только теперь a и b заданы произвольно.
Доказательство
1.6. Разрешимость линейного диофантова уравнения
Линейное диофантово уравнение - это уравнение вида ax + by = c, где a, b, c - целые числа, x, y - неизвестные.
Такое уравнение имеет решение тогда и только тогда, когда c делится на d = gcd(a, b).
Доказательство
1.7. Признаки делимости
Число делится на 2 тогда и только тогда, когда последняя цифра числа делится на 2.
Доказательство
Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.
Доказательство
Число делится на 5 тогда и только тогда, когда последняя цифра числа делится на 5.
Доказательство
Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.
Доказательство
Число делится на 10 тогда и только тогда, когда последняя цифра числа равна 0.
Доказательство
Число делится на 11 тогда и только тогда, разность сумм цифр на четных и нечетных позициях делится на 11.
Доказательство
1.8. НОД и НОК
Наибольший общий делитель - это наибольшее число, на которое делятся оба числа.
Наименьшее общее кратное - это наименьшее число, которое делится на оба числа.