4.9 ФИ- И МЮ-ФУНКЦИИ

Сколько среди целых чисел взаимно простых с Эта важная величина называется - «тотиентой» числа (названной так Дж. Дж. Силвестером [274] — английским математиком, любившим придумывать новые термины). Имеем

для всех составных чисел .

Функция называется эйлеровой фи-функцией, ибо Эйлер был первым, кто изучал ее. Так, Эйлер обнаружил, что теорема Ферма (4.47) может быть обобщена на непростые модули следующим образом:

(Доказать теорему Эйлера предлагается в упр. 32).

Если является степенью простого числа, то легко вычисляется, ибо Кратными среди чисел являются числа следовательно, всего их подсчитывает то, что остается:

Обратите внимание, что при эта формула, как и положено, дает величину

Если не является степенью простого числа, то можно записать где Тогда числа могут быть представлены как в системе остатков. Согласно (4.30) и (4.4)

Следовательно, величина является тогда и только тогда, когда являются "хорошими" как так и если считать взаимную простоту хорошим качеством. А общее число „хороших" величин по модулю теперь может быть вычислено рекурсивно: оно равно поскольку имеется хороших способов выбора первой компоненты хороших способов выбора второй компоненты в модульном представлении.

Так, поскольку взаимно просто с 12 тогда и только тогда, когда или 3) и или 2). Вот четыре величины в системе остатков, взаимно простых с 12: (1,1), (1,2), (3,1), (3,2); в обычной десятичной записи это 1, 5, 7, 11. Теорема Эйлера утверждает, что всякий раз, когда

Функция целых положительных чисел называется мультипликативной, если и

Тем самым мы доказали, что -мультипликативная функция. Ранее в этой главе нам уже встречался другой пример мультипликативной функции: число несравнимых решений сравнения мультипликативно. А вот еще один пример: при любом показателе степени

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

целое положительное число может быть разложено на степени простых сомножителей, которые взаимно просты друг с другом. Общая формула

имеет место тогда и только тогда, когда — мультипликативная функция.

В частности, эта формула доставляет величину эйлеровой фи-функции для произвольного числа

К примеру, .

Обратимся теперь к использованию ф-функции для изучения рациональных чисел по Говорят, что дробь — правильная, если . Следовательно, — это число несократимых правильных дробей со знаменателем а все несократимые правильные дроби со знаменателем или меньшим и неправильная дробь входят в состав последовательности Фарея

Множество всех правильных дробей со знаменателем 12 до их приведения к несократимым имеет вид:

а после приведения —

и эти дроби можно сгруппировать по их знаменателям:

Но что из этого можно извлечь? Ну, например, то, что среди знаменателей встречается каждый делитель числа 12 вместе со всеми своими числителями. Все без исключения знаменатели являются делителями 12. Таким образом,

Если же начать с несокращенных дробей при любом то, очевидно, выйдет то же самое — следовательно,

Как-то в начале этой главы мы утверждали, что в теоретикочисловых задачах часто требуются суммы по делителям некоторого числа. Как видите, одна из таких сумм, так что наше утверждение подтвердилось. (Мы увидим и другие примеры.)

А теперь — курьезный факт: если некоторая функция, такая, что сумма

является мультипликативной функцией, то и сама — мультипликативная функция. (Это обстоятельство, наряду с (4.54) и тем фактом, что очевидно, мультипликативная функция, дает другое объяснение тому, почему является мультипликативной функцией.) Сей курьезный факт можно доказать индукцией по база индукции устанавливается просто, ибо Пусть и допустим, что для любых Если то

так как все делители взаимно просты со всеми делителями По индукционному предположению, за исключением, возможно, случая, когда следовательно,

Но это равно так что

Обратно, если является мультипликативной функцией, то соответствующая ей функция суммы по делителям — всегда мультипликативная функция. На самом деле, как показывает упр. 33, справедливо даже большее. Следовательно, наш курьезный факт и обратный к нему — это непреложные факты.

Функция Мёбиуса — названная так в честь математика девятнадцатого столетия Августа Мёбиуса, знаменитого также своей лентой, — определяется при всех уравнением

Вообще-то, это рекуррентное уравнение, поскольку его левая часть представляет собой сумму, состоящую из собственно и определенных значений при Например, если последовательно подставлять , то можно вычислить двенадцать первых значений данной функции:

Ричард Дедекинд [100] и Жозеф Лиувилль [199] в 1857г. заметили следующий важный „принцип обращения":

В соответствии с этим принципом, функция обеспечивает нас еще одним способом выяснения того, что собой представляет некоторая функция для которой известна сумма

Для доказательства соотношения (4.56) воспользуемся двумя приемами (4.7) и (4.9), которые были приведены где-то в начале этой главы. Если то

Другая половина соотношения (4.56) доказывается аналогично (см. упр. 12).

Соотношение (4.56) выявляет ценное качество функции Мёбиуса, и мы уже поместили в табличку первые двенадцать ее значений. Но какова величина при большом ? И как разрешить рекуррентность (4.55)? Ну, очевидно, что является мультипликативной функцией — при всех она попросту равна нулю, за исключением Так что функция Мёбиуса, определенная уравнением (4.55), должна быть мультипликативной функцией в силу того, что мы доказали минуту или две назад. Поэтому можно выяснить, что такое если вычислить Когда то (4.55) утверждает, что

при любом к 1, так как делителями является Отсюда следует, что

Поэтому в силу (4.52) получаем общую формулу:

Вот что такое

Если рассматривать (4.54) как рекуррентное соотношение для функции то эту рекуррентность можно разрешить, применив правило Дедекинда—Лиувилля (4.56). Искомое решение таково:

Например,

Если делится на различных простых чисел, скажем, на то сумма (4.58) имеет только ненулевых членов, ибо функция большей частью равна нулю. Так, можно убедиться, что (4.58) согласуется с формулой (4.53), записанной в виде

если перемножить все сомножителей то получим в точности ненулевых членов суммы (4.58). Достоинство функции Мёбиуса состоит в том, что помимо рассмотренной, она применима и во многих других ситуациях.

К примеру, попробуем выяснить, сколько дробей насчитывается в последовательности Фарея Их количество равно числу несократимых дробей из [0, 1], знаменатели которых не превосходят так что оно на 1 больше величины которая определяется как

(Из-за последней дроби у к нужно прибавить 1.) Непосредственное вычисление суммы (4.59) затруднительно, однако величину можно установить косвенно, заметив, что

при любом вещественном Но почему это тождество справедливо? Ну, несмотря на его несколько пугающий вид, на самом

деле доказательство его справедливости не выходит за рамки наших возможностей. Всего имеется правильных дробей считая как сокращенные, так и несокращенные дроби, — это дает правую часть. А число таких дробей с равно потому что такие дроби суть после замены на на Таким образом, левая часть подсчитывает число тех же самых дробей другим способом, и данное тождество должно быть признано справедливым.

Теперь более обстоятельно разберемся в сложившейся ситуации, с тем чтобы уравнения (4.59) и (4.60) стали более ясными. Из определения следует, что однако удобнее считать функцию определенной на произвольных вещественных числах, а не только на целых. В целых точках получаем следующую таблицу:

и можно проверить тождество (4.60) при

Поразительно.

Тождество (4.60) можно рассматривать как неявную рекуррентность относительно — как мы только что видели, этим можно было воспользоваться при вычислении величины Ф (12) по определенным величинам при . А разрешать такие рекуррентности можно с помощью другого прекрасного свойства функции Мёбиуса:

Данное правило обращения имеет место для всех функций таких, что . Это можно доказать следующим образом. Предположим, что Тогда

Доказательство в другую сторону по существу такое же.

Вот теперь мы в состоянии разрешить рекуррентность (4.60) относительно

Эта сумма всегда конечна. К примеру,

В гл. 9 мы покажем, как использовать (4.62) для получения хорошего приближения к в действительности мы докажем результат, установленный Мертенсом в 1874 г. [219],

Следовательно, функция возрастает «плавно» усредняя сумасбродное поведение функции

Придерживаясь заведенной в предыдущей главе традиции, завершим эту главу задачей, иллюстрирующей многое из того, с чем мы уже познакомились, и что, кроме того, имеет отношение к следующей главе. Представим себя обладателями бусинок различных цветов; наша цель — подсчитать, сколькими способами из них можно составить ожерелье длины . В данной задаче можно испытать принцип „обозначай и властвуй", обозначив число возможных ожерелий через .

К примеру, из бусинок двух цветов и В ожерелье длины 4 можно собрать различными способами:

Все другие способы эквивалентны одному из этих, потому что вращение ожерелья ничего не меняет. Однако их отражения считаются различными; так, в случае

Задача подсчета таких конфигураций впервые была решена майором П. А. Мак-Магоном в 1892 г. [212].

Явной рекуррентности для величины не существует, однако число ожерелий можно подсчитать, разрывая и вытягивая в нить способами каждое из них и рассматривая получающиеся

обрывки. Например, при получаем следующие наборы:

ВВВВ ВВВВ ВВВВ ВВВВ

Каждый из возможных наборов встречается по крайней мере один раз в этом наряде из ниток бус, а некоторые наборы — и более одного раза. А сколько раз на самом деле встречается набор ? В таком вопросе нет ничего сложного: это число циклических сдвигов набора , приводящих к тому же набору, что и первоначальный набор . К примеру, набор получается дважды, так как четыре способа разрыва ожерелья из бус соответствуют четырем циклическим сдвигам два из которых совпадают с самим Подобное рассуждение показывает, что

Здесь — множество различных цветов.

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

Это означает, что Таким образом, могут быть выбраны способами, а остальные а — в зависимости от них. Не напоминает ли это что-нибудь знакомое? В общем случае соотношение

заставляет нас уравнять при а нам известно, что кратными к по модулю являются числа где Поэтому общее решение состоит в независимом выборе и последующем присвоению при . А всего решений

Тем самым мы доказали, что

Эта сумма может быть упрощена, поскольку она включает только члены вида где Подстановка дает

(Мы имеем право заменить на , так как к должно быть кратно Наконец, по определению, и мы получаем формулу Мак-Магона:

К примеру, если то число ожерелий равно — как того и следовало ожидать.

Не тотчас очевидно, что величина определяемая суммой Мак-Магона, является целым числом! Давайте попробуем доказать непосредственно, что

не связывая наши рассуждения с ожерельями. В частном случае, когда — простое число, это сравнение сводится ), т. е. к сравнению Мы уже видели в (4.48), что это сравнение представляет собой другую формулировку теоремы Ферма. Поэтому сравнение (4.64) справедливо, если -его можно рассматривать как обобщение теоремы Ферма на случай, когда модуль не является простым. (Обобщение Эйлера (4.50) — это другое обобщение.)

Мы доказали (4.64) для всех простых модулей, так что обратимся к наименьшему из оставшихся непростых случаев — случаю Надо доказать, что

Доказательство упростится, если рассматривать отдельно четные и нечетные случаи. Если четно, то все три члена в левой части сравнимы с 0 по модулю 4 — так же, как и их сумма. Если же нечетно, то сравнимы с 1, а сравнимо с 2; следовательно, левая часть сравнима с а тем самым, сравнима с 0 по модулю 4, и мы получили требуемое.

А теперь немного осмелеем и замахнемся на случай Это должно нас заинтересовать потому, что оно имеет довольно много множителей, включая квадрат простого числа, несмотря на то, что само оно весьма мало. (К тому же нами движет надежда получить возможность обобщения доказательства для 12 на произвольное т.) Сравнение, которое надо доказать, это

Ну и что? Согласно (4.42) это сравнение выполняется тогда и только тогда, когда оно выполняется по модулю 3 и по модулю 4. Поэтому вначале докажем, что оно выполняется по модулю 3. Сравнение (4.64) выполняется для простых чисел, так что Под пытливым взором выясняется, что данный факт можно использовать для группировки членов большей суммы:

Итак, по модулю 3 это проходит.

Полдела сделано. Для доказательства сравнимости по модулю 4 воспользуемся тем же самым приемом. Уже доказано, что поэтому воспользуемся этим обстоятельством для группировки членов сравнения

для случая

Пока наше сравнение доказано для простого для для Теперь попробуем доказать его для степеней простого числа. Для конкретности можно предположить, что при некотором простом р. Тогда левая часть (4.64) есть

Можно показать, что это сравнимо с 0 по модулю если мы сумеем доказать, что делится на что делится на и что делится на , — ибо все это вместе будет тогда делиться на Согласно теореме Ферма в альтернативной формулировке имеем ), так что делит следовательно, существует целое такое, что

Теперь возводим обе части в степень, разлагаем правую часть в соответствии с биномиальной теоремой (с которой познакомимся в гл. 5) и после перегруппировки членов получаем

при некотором другом целом . Мы оказались в состоянии выделить множитель потому, что во втором слагаемом и потому, что множитель присутствует во всех последующих членах. Итак, выяснили, что делит .

Возведем еще раз обе части в степень, разложим в ряд и перегруппируем члены, получая

при еще одном целом Итак, делит Этим завершается доказательство для ибо показано, что делит левую часть (4.64).

Более того, можно доказать по индукции, что

при некотором последнем целом (последнем потому, что мы исчерпали все способы начертания данной буквы); следовательно,

Таким образом, левая часть (4.64), которая равна

делится на и тем самым сравнима с 0 по модулю

Уже почти все сделано. Теперь, когда сравнение (4.64) доказано для степеней простого числа, все, что осталось, - это доказать его для где считая, что данное сравнение справедливо при Рассмотрение случая который распадался на отдельные случаи дает основание надеяться, что такой подход будет оправдан.

Поскольку нам известно, что — мультипликативная функция, можно записать

Но внутренняя сумма сравнима с 0 по модулю так как мы предположили, что (4.64) выполняется при следовательно, и вся сумма сравнима с 0 по модулю Из симметричных соображений выясняется, что вся сумма сравнима с 0 по модулю

Таким образом, в силу (4.42) она сравнима с 0 по модулю