П.4 Функция Мёбиуса

Определение. Целая часть Х — наибольшее целое число, не превосходящее х.

Обозначение. [ x ]—целая часть х.

Примеры. .

Геометрический смысл: — ближайшее целое число, слева от х.

Замечание. Из определение целой часть следует, что .

Определение. Дробная часть х —разность между числом и его целой частью.

Обозначение. —дробная часть х.

Примеры.

Геометрический смысл: { x }—расстояние от [ x ] до x.

 

Замечание. Из определения дробных частей следует, что любое число х можно представить в виде суммы его целой и дробной частей: , где

Наглядное представление о функциях и дают их графики:

Заметим, что , , где

Свойства целой части.

1. Пусть тогда — количество натуральных чисел, которые не превосходят х и делится на n.

Доказательство. Выпишем натуральные числа, которые делятся на n:

Для любого положительного х верно неравенство при некотором .

Тогда

■

2. Пусть Тогда

Доказательство. Левая часть—количество натуральных чисел и делящихся на n. Правая часть—количество натуральных чисел и делящихся на n. Но между [ x ] и х нет других целых чисел, следовательно, указанные два числа равны.

■

3. Для любых или 1.

Доказательство. Складывая двойные неравенства , получим , это означает, что или .

■

Пример. . Но,

Следствие. Пусть . Чтобы найти неполное частное от деления n на ab можно взять неполное частное от деления n на a и разделить его на b. Неполное частное от этого деления будет искомым:

Доказательство. Пусть , где остаток

Тогда , где . Отсюда следует, что — неполное частное от деления n на а.

Итак, указанное свойство действительно выражается записанной формулой. Но по свойству 2, .

■

Примеры того как в теории чисел используется функция [ x ] будут приведены в п2. сейчас познакомимся с работой функции { x } на примере теоремы Дирихле. При доказательстве этой теоремы Дирихле впервые сформулировал принцип, который сейчас носит его имя. (“Если разместить предмет в N ящиках, то хотя бы в одном ящике будет 2 перемета”).

Теорема (Дирихле).

Пусть Тогда существует рациональное число такое, что , где

Иначе говоря: любое действительное число α; можно приблизить рационально с помощью дроби с точностью до , .

Доказательство. Рассмотрим t +1 число из промежутка [0;1):

Разобьем [0;1) на t равных частей: .

По принципу Дирихле в одном из интервалов лежат 2 числа: и , можно считать, что

Расстояние между ними меньше длины интервала:

Далее, заменяя { x } на x­ –[ x ] получим

Обозначим Число n и m — целые.

Значит, найдена рациональная дробь такая, что

■

Следствие. Для любого иррационального числа α множество чисел n α­– m, где n и m — целые, всюду плотно на R, т.е. между любыми действительными х и у есть число вида n α ­– m.

Иначе говоря: для любых двойное неравенство

имеет целые решения n и m.

Доказательство. Для любого, сколь угодно малого интервала (х; у) можно выбрать такое, что станет меньше, чем длинна интервала .

Для выбранного t, согласно теореме Дирихле, найдется рациональное число такое, что . Число располагается близко к нулю. Откладывая k раз отрезок длины получим точку , т.е. .

■

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

Решение. Утверждение означает, что найдутся целые k и m такие, что

После логарифмирования получим .

Пологая , получим

Существование целых n и m следует из следствий к теореме Дирихле.

п.2 Каноническое разложение n!. Функции Чебышева.

Согласно основной теореме арифметики .

Обозначение:

Здесь — кратность, с которой простое число р входит в каноническое разложение n, т.е. — наибольший показатель, при котором n делится на (а на число n уже не делится).

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

Теорема 1. Показатель, с которым простое число р входит в произведение n! равен

Замечание. Число слагаемых в формуле (которая представлена выше) конечно. Действительно, как только станет больше, чем n, все целые части станут равны нулю.

Доказательство. запишем произведение n! выделяя те сомножители, которые делятся на р:

Здесь kp — последнее число кратное р. По свойству 1 целой части .

Будем считать, что каждое из k выделенных чисел вносит по единице в итоговый показатель . Но некоторые из выделенных чисел делятся на и, значит, их вклад в показатель составит уже по 2 единицы. Количество таких чисел, по тому же свойству 1, равно . Затем, чисел делятся на , их вклад в общую сумму составит по 3 единицы и так далее.

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

■

Пример 1. найти наивысшую степень числа 7, на которую делится 900!

Решение. Имеем n =900, p =7, поэтому Все слагаемые, начиная с четвертого равны нулю, так как .

Учитывая, что , , вычисления удобно проводить по следующей схеме:

Ответ: .

 

Следствие.

Пример 2. Найти каноническое разложение 16!

Решение. Имеем . При этом

, , , , .

Ответ:

Замечание. Пусть , — наибольшая степень р, не превосходящая n.

Тогда

Формула (1) используется в различных теоретико­-числовых соотношениях х.

Пусть х —действительное число, .

Обозначение:

Теорема 2. Показатель с которым простое число р входит в каноническое разложение К (х), равен .

Доказательство. пусть искомый показатель . Тогда К (х) делится на , но не делится на . Это означает, что среди чисел 1, 2, 3, … [ x ] есть хотя бы одно число u, которое делится на , но нет чисел, делящихся на . Следовательно, . Логарифмируя неравенство, получим

■

Следствие.

(При p > x все целые части равны нулю).

Кратность , с которыми простое р входит в разложение факториала и функции К (х), связаны одним важным соотношением, известным как тождество Чебышева: !

Пример. Пусть х =10. проверим, что

Произведение наименьших общих кратных в левой части равняется:

С другой стороны

■

Тождество (3) было доказано Чебышевым в работах, посвященных исследованию распределения простых чисел (подробнее см. §4).

Определение. Функциями Чебышева называют функции:

Где суммы берутся по всем простым числам для и по всем степеням простых чисел для .

Замечание. При вычислении каждый логарифм считается К раз, что соответствует К степеням — , не превосходящим х.

Пример.

Непосредственно из определения следует, что

Пример. .

Итак, , значит, логарифмируя тождество (3) получим следующее утверждение:

Теорема 3. (Тождество Чебышева)

(Сумма в левой части конечна, т.к. при х <2)

Доказательство. Пусть . По теореме 1 и свойству 2 целой части

С другой стороны, функция можно записать в виде

Тогда, суммируя эти функции по m, получим

Так как условие для пар натуральных чисел (m, K) равносильно условию

для всех пар (K, m).

Замечание. Между функциями и имеется очевидная связь: , что следует из того, что .

Сумма в правой части конечна: при х <2.

п.3 Мультипликативные функции.

Определение. Функция f(x) определенная на множестве натуральных чисел, называется мультипликативной, если:

1)f(n) не равняется тождественно нулю;

2)для любых взаимно простых чисел n и m

Пример. Функция мультипликативная при любых .

В самом деле,

В частности, функции — мультипликативны.

Свойства мультипликативных функций.

1)Пусть f(x) мультипликативна. Тогда f(1)=1.

Доказательство. Выберем так, что . Тогда

■

2)произведение двух мультипликативных функций также является мультипликативной функцией.

Доказательство. Пусть , где f и g — мультипликативны. Тогда

Для любых взаимно простых n и m.

■

3)Пусть f(n) — мультипликативная функция; — попарно взаимно простые числа. Тогда

Доказательство. Поскольку при всех , то

Поэтому

Продолжая тот же процесс получим требуемое.

■

4)Пусть f(n) — мультипликативная функция, — каноническое разложение числа n.

Доказательство. Следует из свойства 3.

Замечание. Для того, чтобы построить мультипликативную функцию f (n) достаточно положить f (1)=1 и произвольно определить значения для всех простых р и всех . Для остальных натуральных чисел значения f (n) вычисляются по формуле свойства 4.

Действительно для взаимно простых n и m произведения f(nm) и f(n)f(m) будут состоять из одинаковых сомножителей, взятых, быть может, в другом порядке.

Пример. Пусть f(1)=1, при всех р и всех α.

Тогда, например,

Вообще говоря, если и взаимно просты, то и функция f (n) является мультипликативной.

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

Обозначение: — сумма по всем возможным делителям числа n.

Пусть f(n) мультипликативна. Определим новую функцию:

Пример. Если , то — сумма квадратов всех делителей числа n. Например,

Теорема. Пусть f (n) мультипликативна, — каноническое разложение числа n.

Тогда,

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

Где . Число является всевозможными делителями числа n (без пропусков и повторений). Следовательно, полученная сумма и есть .

■

п.4 Функция Мёбиуса

Определение: Функций Мёбиуса называется функция µ(n), заданная на N такая, что

Иначе говоря, µ(n)=0, если в каноническом разложении, хотя бы один показатель . В этом случае говорят, что число n не свободно от квадратов, т.е. представимо в виде .

Пример:

Если p — простое, то, очевидно, µ(p)= -1.

Из определения следует мультипликативность функции µ(n). Это обстоятельство позволяет дать равносильное определение функции Мёбиуса (смотри замечание в пункте 3).

Определение: Мультипликативная функция µ(n) такая, что при , называется функцией Мёбиуса.

Теорема: Пусть f(n) — мультипликативная функция; . Тогда

Доказательство:Произведение µ(n)f(n) мультипликативно (свойство 2, п.3). Применяя к функции теорему из п.3, и учитывая, что и при , получим:

■

Замечание: Если n = 1, то .

Выбирая различные мультипликативные функции f(n) можно получить серию полезных тождеств для функции Мёбиуса. Например,

1)

2)

Замечание: Приведем другое доказательство полученных тождеств. Пусть . Перечислим все делители n, для которых

.

Тогда

Аналогично,

Функция Мёбиуса позволяет установить обратную связь между данной функцией f(n) и функцией

Теорема: (закон обращения Мёбиуса)

Пусть f(n) — произвольная функция, определена на N и

— (1)

Тогда — (2)

Верно и обратное утверждение: если f(n) определена формулой (2), то g(n) вычисляется с помощью (1).

Доказательство:При n=1 имеем и утверждение теоремы верно. Пусть . По определению g(n) имеем:

 

Домножим это равенство на µ(d) и просуммируем по всем d:

Двойная сумм справа берется по всем парам (d; c) таким, что dc делит n. Но эти пары можно перебирать в другом порядке:

Поэтому

Согласно тождеству для функции Мёбиуса, сумма, взятая в скобки, ровна нулю всегда, кроме случая . Значит, внешняя сумма по переменной С состоит только из одного ненулевого слагаемого (при с = n):

■

Пример 1: Если f(n)= 1, то (см. п.3)

По формуле обращения Мёбиуса:

.

Например, возьмем n = 12.

Тогда

Пример 2: Возьмем в качестве f(n) функцию Мангольд, то :

Вычислим . Пусть . Тогда (при выборе других делителей ). Тогда, по определению , .

Применим закон обращения Мёбиуса:

.

Так как ln1=0, а при , то окончательно получим

.

Закон обращения Мебиуса можно обобщить.

Теорема: Пусть — некоторые натуральные числа, среди которых могут быть повторяющиеся. Пусть им соответствуют, по некоторому правилу, действительные (или комплексные) числа . Обозначим

,

Тогда .

(Суммы конечны, так как чисел и их делителей d — конечно число)

Доказательство:

■

Убедимся в том, что закон обращения Мёбиуса есть частный случай доказанной теоремы.

Пусть f(n) — произвольная функция, определенная на N.

Зафиксируем некоторое n и обозначим —

все возможные делители n. Соответствие установим по правилу:

Тогда ,

|Обозначим . Тогда или, что то же самое, | = , где — функция введенная ранее.

Итак, утверждение теоремы принимает вид .