Функция Эйлера
Версия от 16:42, 24 декабря 2020; MetaMockery (обсуждение | вклад) (Отмена правки 75527, сделанной MetaMockery (обсуждение))
Содержание
Функция Эйлера
Определение: |
Функция | называется мультипликативной, если для любых взаимно-простых .
Определение: |
Функция Эйлера | - определяется как количество натуральных чисел, не превосходящих и взаимно-простых с .
Теорема (Мультипликативность функции Эйлера): |
Для любых взаимно-простых чисел
|
Доказательство: |
Запишем натуральных чисел, не превосходящих , в виде прямоугольной таблицы с столбцами и строками, располагая первые чисел в первой строке, вторые чисел во второй и т.д.Поскольку и взаимно-просты, то целое взаимно-просто с если и только если оно взаимно-просто как с , так и с . Итак, нужно доказать, что количество чисел в таблице, взаимно-простых с и с равно . Мы знаем, что число взаимно-просто с натуральным если и только если его остаток при делении на взаимно-просто с . Поэтому, числа в таблице, взаимно-простые с , заполняют ровно столбцов таблицы.Давайте рассмотрим Подставив в данные рассуждения последовательных членов арифметической прогрессии . Тогда, если , то остатки всех этих чисел по модулю разные, а значит образуют все множество остатков , причем каждый остаток получается ровно из одного из членов прогрессии. , получим, что в каждом столбце таблицы имеется ровно чисел, взаимно-простых с . Следовательно всего чисел, взаимно-простых и с и с равно , что и требовалось доказать. |
Функции , и , их мультипликативность и значения
Функция
Каноническое разложение числа
Функция
определяется как сумма делителей натурального числа :Для простого числа
легко посчитатьФункция
мультипликативна. Значит
sigma и tau функции, их мультипликативность и значение
Примеры:
, ,
, .
Свойства функции Эйлера
- 1. Доказательство: простое, .
- Логически понятно, если строго, то выводится из 2 свойства.
, p — - 2. Пусть — каноническое разложение числа a, тогда
- Доказательство: Пусть НОД. Тогда есть число значений , равных единице. Возьмем функцию, которая равна единице, если , и равна нулю в остальных случаях. Вот такая функция : , где — функция Мебиуса. Отсюда . Поскольку справа сумма в скобках берется по всем делителям d числа , то d делит x и a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел ровно штук. Получается, что . пробегает числа , положим —
- 3. Функция Эйлера является мультипликативной .
- Вытекает из первого свойства.