Теория остатков (стр. 8 из 10)
и
. Эти два числа были опубликованы, причем дополнительно сообщалось, что 
, где 
и 
- простые числа, записываемые соответственно 
и 
десятичными знаками. Первому, кто дешифрует соответствующее сообщение 
была обещана награда в 100$.
Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, A. K. Lenstra и P. C. Leyland сообщили о дешифровке фразы, предложенной в [1]. Она1) была вынесена в заголовок статьи, а соответствующие числа
и оказались равными 
Определение. Функция : R R (или, более общо, : C C ) называется мультипликативной если:
1). Функция определена всюду на N и существует а N такой, что ( а ) 0.
2). Для любых взаимно простых натуральных чисел а 1 и а 2 выполняется ( а 1 · а 2 ) = ( а 1 ) · ( а 2 ).
Пример 1. ( а ) = а s , где s - любое (хоть действительное, хоть комплексное) число. Проверка аксиом 1) и 2) из определения мультипликативной функции не составляет труда, а сам пример показывает, что мультипликативных функций по меньшей мере континуум, т.е. много.
Перечислим, кое-где доказывая, некоторые свойства мультипликативных функций. Пусть всюду ниже ( а ) - произвольная мультипликативная функция.
Свойство 1. (1) = 1.
Доказательство. Пусть а - то самое натуральное число, для которого
( а ) 0. Тогда ( а · 1) = ( а ) · (1) = ( а ).
Свойство 2.
,где р 1 , р 2 ,..., р n - различные простые числа.
Доказательство очевидно.
Свойство 3. Обратно, мы всегда построим некоторую мультипликативную функцию ( a ), если зададим (1) = 1 и произвольно определим ( р ) для всех простых р и всех натуральных , а для остальных натуральных чисел доопределим функцию ( a ) используя равенство
.Доказательство сразу следует из основной теоремы арифметики.
Пример 2. Пусть (1) = 1 и ( р ) = 2 для всех р и . Тогда, для произвольного числа,
.Свойство 4. Произведение нескольких мультипликативных функций является мультипликативной функцией.
Доказательство. Сначала докажем для двух сомножителей: Пусть 1 и 2 - мультипликативные функции = 1 · 2 , тогда (проверяем аксиомы определения)
1) (1) = 1 (1) · 2 (1) = 1 и, кроме того, существует такое a (это a = 1), что ( a ) 0.
2) Пусть ( a , b ) = 1 - взаимно просты. Тогда
( a · b ) = 1 ( a · b ) · 2 ( a · b ) =
= 1 ( a ) 1 ( b ) 2 ( a ) 2 ( b ) =
= 1 ( a ) 2 ( a ) · 1 ( b ) 2 ( b ) = ( a ) ( b ).
Доказательство для большего числа сомножителей проводится стандартным индуктивным рассуждением.
Введем удобное обозначение. Всюду далее, символом
будем обозначать сумму чего-либо, в которой суммирование проведено по всем делителям 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 принимает вид:
 |
| сумма первых ( + 1) членов геометрической прогрессии |
- сумма всех делителей числа 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 . Полезность и практическое применение этой функции я продемонстрирую в следующих пунктах, а сейчас давайте поймем, как ее вычислять.