 |
 |
 |
 |
 |
 |
 |
| Кратко о теории чисел. |
|
| |
|
||||||||||
|
|
 |
§ 3. Важнейшие функции в теории чиселПункт 14. Примеры мультипликативных функций.Предыдущий пункт дал нам общие абстрактные знания о мультипликативных функциях вообще. Благодаря этому, в этом пункте мы сможем во всеоружии встретить целую серию примеров полезных мультипликативных функций. Большинство этих примеров строятся с использованием лемм предыдущего пункта, а в качестве исходного строительного материала берется какая-нибудь конкретная степенная функция q ( а ) = а s , которая, конечно, мультипликативна. Вы готовы? Начинаем. Пример 1. Число делителей данного числа. Пусть q ( а ) = а 0 є 1 - тождественная единица (заведомо мультипликативная функция). Тогда, если
то тождество леммы 1 пункта 13 принимает вид:
- это не что иное, как количество делителей числа a . По лемме 2 пункта 13, количество делителей t ( a ) числа a есть мультипликативная функция. Численный примерчик. t (720) = t (2 4 · 3 2 · 5) = (4 + 1)(2 + 1)(1 + 1) = 30. Пример 2. Сумма делителей данного числа. Пусть q ( a ) = a 1 є a - тождественная мультипликативная функция. Тогда, если
то тождество леммы 1 пункта 13 принимает вид:
- сумма всех делителей числа a . По лемме 2 пункта 13, сумма всех делителей есть мультипликативная функция. Численный примерчик.
Пример 3. Функция Мебиуса. Функция Мебиуса m ( a ) - это мультипликативная функция, определяемая следующим образом: если p - простое число, то m ( p ) = -1; m ( p a ) = 0, при a > 1; на остальных натуральных числах функция доопределяется по мультипликативности. 
Таким образом, если число a делится на квадрат натурального числа, отличный от единицы, то m ( a ) = 0; если же a = p 1 p 2· · · p n (теоретик-числовик сказал бы на своем жаргоне: "если a свободно от квадратов"), то m ( a ) = (-1) k , где k - число различных простых делителей a . Понятно, что m (1) = (-1) 0 = 1, как и должно быть. Лемма 1. Пусть q ( a ) - произвольная мультипликативная функция,
Тогда:
(при a = 1 считаем правую часть равной 1). Доказательство. Рассмотрим функцию q 1 ( x ) = m ( x ) · q ( x ). Эта функция мультипликативна, как произведение мультипликативных функций. Для q 1 ( x ) имеем ( p - простое): q 1 ( p ) = - q ( x ); q 1 ( p a ) = 0, при a > 1. Следовательно, для q 1 ( x ) тождество леммы 1 пункта 13 выглядит так:
Ё
Следствие 1. Пусть q ( d ) = d -1 = 1/ d (это, конечно, мультипликативная функция),
Тогда:
Воздержусь от доказательства этого следствия в силу банальности сего доказательства, но вот на правую часть этого тождества попрошу обратить внимание, так как она еще неоднократно у нас встретится. Физический смысл этой правой части раскрывает пример следующей функции. Пример 4. Функция Эйлера. Функция Эйлера, пожалуй, самая знаменитая и "дары приносящая" функция из всех функций, рассматриваемых в этом пункте. Функция Эйлера j ( a ) есть количество чисел из ряда 0, 1, 2,..., a - 1, взаимно простых с a . Полезность и практическое применение этой функции я продемонстрирую в следующих пунктах, а сейчас давайте поймем, как ее вычислять.
Лемма 2. Пусть
Тогда: 1) 2) в частности, j ( p a ) = p a - p a -1 , j ( p ) = p - 1. Доказательство. Пусть x пробегает числа 0, 1, 2,..., a - 1. Положим d x = ( x , a ) - наибольший общий делитель. Тогда j ( a ) есть число значений d x , равных 1. Придумаем такую функцию c ( d x ), чтобы она была единицей, когда d x единица, и была нулем в остальных случаях. Вот подходящая кандидатура:
Последнее легко понять, если вспомнить лемму 1 из этого пункта и в ее формулировке взять q ( d ) є 1. Далее, сделав над собой некоторое усилие, можно усмотреть, что:
Поскольку справа сумма в скобках берется по всем делителям d числа d x = ( x , a ), то d делит x и d делит a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел 0, 1, 2,..., a - 1 ровно a / d штук. Получается, что:
что и требовалось. Пояснение для читателей, у которых предыдущие соображения не захотели укладываться в голову, например, из-за плохих погодных условий. Имеем
Зафиксируем некоторое d 0 такое, что d 0 делит a , d 0 делит x , x < a . Значит в сумме справа в скобках слагаемых m ( d 0 ) ровно a / d 0 штук и j ( a ) есть просто сумма
После этого, равенство
получается применением следствия из леммы 1 этого пункта. Должен признать, что приведенное доказательство формулы Эйлера и, в особенности, его последний момент с изменением порядка суммирования, объективно тяжеловаты для понимания. Но мы не боимся трудностей! Второе утверждение леммы следует из первого внесением впереди стоящего множителя a внутрь скобок. Ё Оказывается, только что доказанная формула
для вычисления функции Эйлера имеет ясный "физический смысл". Дело в том, что в ней отражено так называемое правило включений и исключений: Правило включений и исключений. Пусть задано множество А и выделено k его подмножеств. Количество элементов множества А , которые не входят ни в одно из выделенный подмножеств, подсчитывается так: надо из общего числа элементов А вычесть количества элементов всех k подмножеств, прибавить количества элементов всех их попарных пересечений, вычесть количества элементов всех тройных пересечений, прибавить количества элементов всех пересечений по четыре и т.д. вплоть до пересечения всех k подмножеств. Проиллюстрирую это правило на примере подсчета функции Эйлера для чисел вида
Посмотрите на рисунок 4.
Рис. 4. Прямоугольник изображает множество всех целых чисел от 0 до a ; овал N 1 - множество чисел, кратных p 1 ; кружок N 2 - числа, кратные p 2 ; пересечение N 1,2 - множество чисел, делящихся одновременно на p 1 и p 2 , т.е. на p 1 p 2 ; числа вне овала и кружочка взаимно просты с a . Для подсчета числа чисел, взаимно простых с a , нужно из a вычесть количество чисел в N 1 и количество чисел в N 2 (их, соответственно, a / p 1 и a / p 2 штук), при этом общая часть N 1,2 (там a /( p 1 p 2 ) штук чисел) вычтется дважды, значит ее надо один раз прибавить (вот оно, "включение - исключение"!). В результате получим:
что я вам и утверждал. Мне кажется, что таким способом можно объяснить формулу Эйлера любому смышленому школьнику. Кстати, любому смышленому школьнику вполне возможно объяснить и то, что при a > 2, j ( a ) всегда число четное. Действительно, если k взаимно просто с a и k < a , то число a - k тоже меньше a , взаимно просто с a и не равно k . (Если бы a и a - k имели общий делитель, то их разность a - ( a - k ) = k тоже делилась бы на этот делитель, что противоречит взаимной простоте a и k .) Значит числа, взаимно простые с a разбиваются на пары k и a - k , следовательно, их четное число. Из леммы 2 вытекают приятные следствия. Следствие 2. Функция Эйлера мультипликативна. Доказательство. Имеем:
- произведение двух мультипликативных функций, первая из которых мультипликативна по лемме 2 пункта 13. Значит, j ( a ) - мультипликативна. Ё Следствие 3.
Доказательство. Пусть
Тогда, по лемме 1 пункта 13 имеем:
Ё Численные примерчики. j (5) = 5 - 1 = 4 j (30) = j (2 · 3 · 5) = (2 - 1)(3 - 1)(5 - 1) = 8
На этом, пожалуй, пункт 14 закончим. Кроме того, предложение, которое вы сейчас начали внимательно читать, тоже закончилось.
* Числа равные сумме собственных делителей древние греки назвали совершенными. В формулировке задачи указаны первые четыре (известных еще Пифагору) совершенных числа. Евклид обнаружил, что если число 2 k -1 - простое, то число (2 k -1) · 2 k -1 обязано быть совершенным. Эйлер доказал, что все четные совершенные числа имеют такой вид. Неизвестно, существуют ли вообще нечетные совершенные числа; во всяком случае, такие числа должны быть больше 10 100 - результат хорошо организованной машинной проверки. Имеется ровно 24 значения k < 20000 , для которых число 2 k -1 - простое ( в этом случае k само обязано быть простым ). Простые числа вида 2 k -1 называются числами Мерсенна, по имени французского математика, который в 1644 году указал в большей части верный список всех таких простых, меньших 10 79 . Изрядно потрудившись, читатель сам может выписать наибольшее известное на сегодняшний день совершенное число, отталкиваясь от наибольшего известного на сегодня простого числа Мерсенна, указанного в пункте 6 этой книжки. Предполагается, что совершенные числа были известны уже в древнем Вавилоне и Египте, где рука с загнутым безымянным пальцем обозначала число шесть - первое совершенное число. Тем самым этот палец сам стал причастен к совершенству и за ним закрепилась привилегия носить обручальное кольцо.
|
||||||||||||||||||||||
,
,
(формула Эйлера);
.
