Теория остатков

Доказательство для большего числа сомножителей проводится стандартным индуктивным рассуждением.



Введем удобное обозначение. Всюду далее, символом

будем обозначать сумму чего-либо, в которой суммирование проведено по всем делителям d числа n . Следующие менее очевидные, чем предыдущие, свойства мул

ьтипликативных функций я сформулирую в виде лемм, ввиду их важности и удобства дальнейших ссылок.

Лемма 1. Пусть

- каноническое разложение числа a N , - любая мультипликативная функция. Тогда:

Если a = 1, то считаем правую часть равной 1.

Доказательство. Раскроем скобки в правой части. Получим сумму всех (без пропусков и повторений) слагаемых вида

,

где 0 k k , для всех k n . Так как различные простые числа заведомо взаимно просты, то

,

а это как раз то, что стоит в доказываемом равенстве слева.



Лемма 2. Пусть ( a ) - любая мультипликативная функция. Тогда

,

- также мультипликативная функция.

Доказательство. Проверим для ( a ) аксиомы определения мультипликативной функции.

1).

2). Пусть

и все р и q различны. Тогда, по предыдущей лемме, имеем: (благо, делители у чисел a и b различны)



Пример 1. Число делителей данного числа.

Пусть ( а ) = а 0 1 - тождественная единица (заведомо мультипликативная функция). Тогда, если

,

то тождество леммы 1 пункта 13 принимает вид:

,

- это не что иное, как количество делителей числа a . По лемме 2 пункта 13, количество делителей ( a ) числа a есть мультипликативная функция.

Пример 2. Сумма делителей данного числа.

Пусть ( a ) = a 1 a - тождественная мультипликативная функция. Тогда, если

,

то тождество леммы 1 пункта 13 принимает вид:

- сумма всех делителей числа a . По лемме 2 пункта 13, сумма всех делителей есть мультипликативная функция.

Пример 3. Функция Мебиуса.

Функция Мебиуса ( a ) - это мультипликативная функция, определяемая следующим образом: если p - простое число, то ( p ) = -1; ( p ) = 0, при > 1; на остальных натуральных числах функция доопределяется по мультипликативности.

Таким образом, если число a делится на квадрат натурального числа, отличный от единицы, то ( a ) = 0; если же a = p 1 p 2· · · p n (теоретик-числовик сказал бы на своем жаргоне: "если a свободно от квадратов"), то ( a ) = (-1) k , где k - число различных простых делителей a . Понятно, что (1) = (-1) 0 = 1, как и должно быть.

Лемма 1. Пусть ( a ) - произвольная мультипликативная функция,

.

Тогда:

(при a = 1 считаем правую часть равной 1).

Доказательство. Рассмотрим функцию 1 ( x ) = ( x ) · ( x ). Эта функция мультипликативна, как произведение мультипликативных функций. Для 1 ( x ) имеем ( p - простое): 1 ( p ) = - ( x ); 1 ( p ) = 0, при > 1. Следовательно, для 1 ( x ) тождество леммы 1 пункта 13 выглядит так:



Следствие 1. Пусть ( d ) = d -1 = 1/ d (это, конечно, мультипликативная функция),

Тогда:

Пример 4. Функция Эйлера.

Функция Эйлера, пожалуй, самая знаменитая и "дары приносящая" функция из всех функций, рассматриваемых в этом пункте. Функция Эйлера ( a ) есть количество чисел из ряда 0, 1, 2, ., a - 1, взаимно простых с a . Полезность и практическое применение этой функции я продемонстрирую в следующих пунктах, а сейчас давайте поймем, как ее вычислять.

Лемма 2. Пусть

.

Тогда:

1) (формула Эйлера);

2)

в частности, ( p ) = p - p -1 , ( p ) = p - 1.

Доказательство. Пусть x пробегает числа 0, 1, 2, ., a - 1. Положим x = ( x , a ) - наибольший общий делитель. Тогда ( a ) есть число значений x , равных 1. Придумаем такую функцию ( x ), чтобы она была единицей, когда x единица, и была нулем в остальных случаях. Вот подходящая кандидатура:

Последнее легко понять, если вспомнить лемму 1 из этого пункта и в ее формулировке взять ( d ) 1. Далее, сделав над собой некоторое усилие, можно усмотреть, что:

Поскольку справа сумма в скобках берется по всем делителям d числа x = ( x , a ), то d делит x и d делит a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел 0, 1, 2, ., a - 1 ровно a / d штук. Получается, что:

 Скачать реферат