АРИФМЕТИКА. Теория делимости 2 страница

.

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

,

что невозможно. А если , то , что тоже невозможно. Это доказывает единственность разложения.

Следствие. Ввиду того, что в разложении (13.2) могут быть одинаковые сомножители, их можно собрать вместе и представить разложение в виде произведения степеней простых чисел, которое называется каноническим разложением числа . Именно:

, где при , . (13.3)

Элементы теории непрерывных дробей

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

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

, ,

. . . . . . . . . .

, .

Это в итоге дает разложение числа в непрерывную дробь:

.

Если – число иррациональное, то и всякое , тоже будет иррациональным, поэтому в этом случае процесс разложения может быть продолжен неограниченно.

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

, ,

, ,

, ,

. . . . . . . . . . . . . . . . . . .

, ,

, .

Это приводит к разложению

.

Числа естественно называть неполными частными (в особенности это касается рационального случая). Дроби

, , , . . .

называются подходящими дробями. Они представляют собой приближения к разлагаемому числу. Представим способ описания подходящих дробей. Это сделать достаточно легко, если заметить, что при вычислении в выражении для заменить число на число . Будем описывать подходящую дробь в виде при этом полагая для единообразия , а . Равенство будем понимать как . Тогда имеем

,

,

, . . .

Далее, легко проверить индукцией, что

. (13.4)

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

(13.5)

					. . .
					. . .
					. . .
					. . .

Опишем схему вычисления для рационального случая.

Пример 13.2. Разложить в непрерывную дробь число . Найдем неполные частные, применяя алгоритм Евклида. Имеем

,

,

,

,

.

В итоге получаем разложение

.

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

Лемма 13.8. При имеет место равенство

.

Доказательство. Обозначим левую часть соотношения через . Тогда при получим, что . Вычислим .

.

Таким образом, видно, что с изменением аргумента на единицу левая часть соотношения меняет знак. Теперь с учетом значения получаем требуемое.

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

Понятно, что это разложение можно продолжать неограниченно долго.

Арифметические функции

Здесь рассмотрим некоторые специальные функции, широко используемые в арифметике.

Определение 13.7. Арифметической функцией называют отображение или .

Пример 13.4. . Это функция тождественно равная нулю.

Пример 13.5. .

Пример 13.6

Пример 13.7. где .

Пример 13.8. , здесь (и далее) суммирование распространено на все положительные делители числа .

Определение 13.8. Арифметическая функция называется мультипликативной, если она отлична от тождественного нуля (т.е., от ) и выполняется условие:

.

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

Пример 13.9. .

Пример 13.10. .

Пример 13.11. Функция из примера 13.8.

Определение 13.9. Мультипликативная функция называется вполне мультипликативной, если

.

Пример 13.12. Функция из примера 13.9.

Пример 13.13. Пусть , где есть количество различных простых делителей . Тогда мультипликативна, но не вполне мультипликативна.

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

Рассмотрим некоторые свойства мультипликативных функций. Эти свойства представим в виде лемм.

Лемма 13.9. Пусть . Тогда .

Доказательство. Так как по определению не равна тождественному нулю, то пусть будет таким, что . Тогда имеем

.

Лемма 13.10. Каждая мультипликативная функция вполне определяется своими значениями на степенях простых чисел.

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

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

Доказательство. Самостоятельно.

Лемма 13.12. Если , то .

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

.

Лемма 13.13. Пусть . Тогда для

.

Доказательство следует из того, что произвольный делитель числа имеет следующий вид: , где , .

Пример 13.15. Рассмотрим функцию из примера 13.8. Тогда для имеем:

.

называется функцией делителей.

Определение 13.10. Функцией Мёбиуса называется арифметическая функция, удовлетворяющая следующим условиям для :

Лемма 13.14. .

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

.

Лемма 13.15. Если , то для справедливо равенство

.

Доказательство. Тривиальное следствие определения и леммы 13.13.

Следствие 1. При получаем

Следствие 2. При получаем

Теорема 13.5 (формула обращения Мёбиуса).

Пусть – арифметическая функция. Тогда

.

Доказательство. Необходимость.

.

Здесь использовали следствие 1 из леммы 13.15.

Достаточность. Имеем

.

Здесь использовали то, что , значит, , т.е., , и снова применили следствие 1 из леммы 13.15. Теорема доказана.

Наконец, приведем еще одну полезную лемму, использующую свойства функции Мёбиуса.

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

,

где пробегает натуральные числа, делящие хотя бы одно значение .

Доказательство. По лемме 13.15 имеем

.

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

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

.

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

Лемма 13.17. Если – простое число, , то

, .

Новый результат получить несколько сложнее.

Лемма 13.18. .

Доказательство. Применим лемму 13.16. Положим все , а в качестве возьмем величины , . Тогда . По лемме имеем, что , где пробегает натуральные числа, делящие хотя бы одно значение , т.е., . Остается выяснить природу . Вновь по лемме это будет количество чисел вида , кратных . Ясно, что это будут делители числа вида , где изменяется от 1 до . Таким образом, . Откуда получаем формулу