Числовые функции. Функция Эйлера. Теоремы Эйлера и Ферма.

Функция Ѳ: NNназывается мультипликативной, если:

1. Ѳ(1)=1

2. для любых m,n: (m,n)=1

Ѳ(m,n)= Ѳ(m)* Ѳ(n)

Рассмотрим функцию NN:

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

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

3. число всех натуральных чисел, не превосходящих nи взаимно простых с ним (φ(n))

Функция Эйлера:

пусть n= каноническое разложение натурального числа n, тогда:

1. τ(n)=(α₁+1)*…*(α_m+1)

2. σ(n)= *…*

3. φ(n)=(

Теорема Эйлера и Ферма: пусть (a,m)=1, тогда a^φ(m) 1(modm)

Пример: 3¹²⁹ 35

(3,35)=1

35=5*7 φ(35)=35(1 - )(1 - )=24

3²⁴ 1 (mod 35)

3¹²⁹=3^24*5+9 (1)⁵*3⁹

3⁴ 81 11

3⁹ 11²*3=121*3 16*3=48 13

12. Содержание

    • Множества и операции над ними. Отношение эквивалентности. Фактор множества.
    • Изоморфизм алгебраических структур
    • Натуральные числа. Нод. Деление с остатком и алгоритм Евклида.
    • Нок. Решение уравнений в целых числах.
    • Простые числа. Основная теорема арифметики. Каноническое разложение. Сравнения.
    • Кольца вычетов. Решение сравнений.
    • Числовые функции. Функция Эйлера. Теоремы Эйлера и Ферма.
    • Матрицы. Элементарные преобразования строк матрицы. Приведение к ступенчатому виду.
    • Операции над матрицами, их свойства.
    • Определители. Основные свойства. Вычисление определителей элементарными преобразованиями.
    • Евклидовы и унитарные пространства, скалярное произведение. Неравенство Коши-Буняковского.
    • Ортогональные системы векторов. Ортогонализация.
    • Ортогональное дополнение подпространства.
    • Сопряженное пространство. Двойственных базис.
    • Основные примеры групп. Конечные группы. Теорема Кэли.
    • Циклические группы. Подгруппы циклической группы.
    • Смежные классы по подгруппе. Теорема Лагранжа.