Материал: Михайленко Е.В. Математика. Ч. 1. Элементы общей алгебры

Дробной частью числа x называется разность x − [x]. Дробная часть числа x обозначается через {x}. Пример. Найдем дробные части чисел.

{2, 4} = 0, 4; {5} = 0; {−3, 7} = 0, 3.

ТЕОРЕМА.

Пусть α – показатель, с которым простое число p входит в каноническое разложение числа n!. Тогда значение этого показателя можно рассчитать по формуле:

Пример. Найти α – показатель степени, с которым p = 11 входит в каноническое разложение числа a = 1000!.

1000 1000 90 8 98.

11 121

Пример. Найти каноническое разложение числа 16!.

Имеем 16! = 2α1 3α2 5α3 7α4 11α5 13α6 . При этом,

Тогда 16! = 215 36 53 72 11 13.

36

Число делителей и сумма делителей

Функцией τ(n) называется число делителей натурального числа n. Функцией σ(n) называется сумма делителей натурального числа n. Пример. Найдем число делителей и сумму делителей натуральных чисел

3, 4, 6, 12.

Теорема. Пусть дано каноническое разложение n = p1α1 p2α2 . . . pkαk.

Тогда число делителей τ(n) натурального числа n равно

τ(n) = (α1 + 1) (α2 + 1) . . . (αk + 1).

Пример. Рассчитать число делителей числа n = 1000. Найдем каноническое разложение числа n:

1000 = 23 53.

Тогда

τ (1000) = (3 + 1)(3 + 1) = 16.

Теорема. Пусть дано каноническое разложение n = p1α1 p2α2 . . . pkαk.

Тогда сумма делителей σ(n) натурального числа n равна

σ(n) = p1(α1 + 1)/(p1-1) ∙ p2(α2 + 1)/(p2-1) ∙ . . . pk (αk + 1)/(pk-1).

Пример. Рассчитать сумму делителей числа n = 24. Найдем каноническое разложение числа n: 24 = 23 31.

Тогда

σ (24) = 23 + 1 / (2 – 1) ∙ 31 + 1 / (3 – 1) = 16 ∙ 9/2 =72.

Пример. Рассчитать сумму делителей числа n = 1000. Найдем каноническое разложение числа n:

1000 = 23 53.

Тогда

σ (1000) = 23 + 1 / (2 – 1) ∙ 53 + 1 / (5 – 1) = 2500.

37

Количество простых чисел

Определение. Функцией π(x) называется количество простых чисел в промежутке от 1 до x.

В начале XIX века поставлена задача нахождения приближения для функции π(x). Важный шаг к доказательству закона распределения простых чисел удалось сделать П.Л. Чебышеву. Он показал, что для достаточно больших x выполняется неравенство:

0,9212 lnxx (x) 1,1055 lnxx.

Пример. Оценить количество простых чисел, не превышающих 1000000. Для решения воспользуемся неравенством Чебышева.

0,9212 ln10000001000000 (x) 1,1055 ln10000001000000.

66679 (x) 80018.

2.5. Сравнения Определение сравнений

Пусть m – натуральное число, которое будем называть модулем, a и b – произвольные целые числа.

Число a сравнимо с числом b по модулю m, если a и b имеют одинаковые остатки при делении на m. Выражение: a сравнимо с b по модулю m, записывают a ≡ b (mod m).

Пример. Справедливы следующие сравнения:

17 ≡ 5 (mod 4); 18 ≡ −6 (mod 4); 15 ≡ 0 (mod 5).

Теорема. Пусть a и b - произвольные целые числа. Тогда равносильны следующие три утверждения:

1)a ≡ b (mod m),

2)a − b кратно m,

3)существует число q є Z с условием a = b + mq.

38

Свойства сравнений

Свойство 1. Отношение сравнимости а) Рефлексивно:

a ≡ a (mod m),

б) Симметрично:

из a ≡ b (mod m) следует b ≡ a (mod m).

в) Транзитивно:

из a ≡ b (mod m) и b ≡ c (mod m) следует a ≡ c (mod m).

Свойство 2. Сравнения можно почленно складывать, вычитать и умножать. Если a ≡ b (mod m) и c ≡ d (mod m), то

а) a + c ≡ b + d (mod m) б) a − c ≡ b − d (mod m) в) ac ≡ bd (mod m)

Свойство 3. Обе части сравнения можно а) умножать на произвольное целое число:

если a ≡ b (mod m), то ak ≡ bk (mod m).

б) разделить на число, взаимно простое с модулем:

если (k, m) = 1, то a/k ≡ b/k (mod m).

Свойство 4. Обе части сравнения можно возводить в степень с показателем k:

если a ≡ b (mod m) то ak ≡ bk (mod m).

Свойство 5.

а) Обе части сравнения и модуль можно умножать на произвольное число

k > 0:

если a ≡ b (mod m), то ak ≡ bk (mod mk).

б) Обе части сравнения и модуль можно разделить на их общий делитель

k > 0:

если ak ≡ bk (mod mk), то a ≡ b (mod m).

Свойство 6. Если a ≡ b (mod m1) и a ≡ b (mod m2), то a ≡ b (mod m), где m = [m1, m2] – НОК модулей m1 и m2.

39

2.6. Классы вычетов Определение классов по модулю m

Классом вычетов a по модулю m называется множество всех чисел, сравнимых с числом a по модулю m.

Теорема. Два класса вычетов a и b равны тогда и только тогда, когда числа a и b сравнимы по модулю m:

a = b a ≡ b (mod m).

При делении целых чисел на m возможны остатки 0, 1, 2, ..., m−1. Рассмотрим классы 0, 1, 2, ..., m−1.

Теорема. 1) Если r – остаток от деления числа a на m, то класс a совпадает

склассом r.

2)Существует ровно m классов вычетов по модулю m. Классы 0, 1, 2, ..., m−1 попарно различны и исчерпывают все классы по модулю m.

Пример.

При делении целых чисел на 7 получим классы вычетов:

0, 1, 2, 3, 4, 5, 6.

Полная система вычетов

Полной системой вычетов по модулю m называется совокупность чисел, взятых по одному из каждого класса вычетов по модулю m.

Пример. Совокупность чисел 5, 11, 4, 6 является полной системой вычетов по модулю 4, так как при m = 4 имеется ровно четыре класса 0, 1, 2, 3, а числа 5, 11, 4, 6 взяты по одному из каждого класса:

4 0, 5 1, 6 2, 11 3.

Числа 5, 1, 4, 6 не образуют полную систему вычетов по модулю 4, так как числа 5 и 1 взяты из одного класса 1 и не представлены числа из класса 3.

Теорема. Совокупность чисел x1, x2, ..., xk образует полную систему вычетов по модулю m тогда и только тогда, когда выполнены следующие два условия:

1)k = m,

2)xi xj (mod m) при i ≠ j.

40