книги из ГПНТБ / Чандрасекхаран, К. Введение в аналитическую теорию чисел
.pdf70 |
Г л. VI. Арифметические функции и целые точки |
Ясно, что D(N) представляет собой число целых точек «первого» квадранта (т. е. верхнего правого квадранта), лежащих на или ниже гиперболы xy— N, при этом це лые точки, лежащие на осях координат, исключаются, так как для них х у = 0.
Чтобы оценить порядок роста D(N), нам потребуется следующая теорема:
Теорема 7. Пусть g — монотонно убывающая функ
ция действительного переменного t, определенная при t^O, причем g(i) > 0 при t^. 1. Тогда
|
х |
2 |
g(n) = § g (t)d t+ A + 0(g(X)), |
1 <п*сХ |
1 |
где п — целое положительное число, Х ^ 1 и А — посто
янная, зависящая только от g.
Доказательство. |
Рассмотрим замкнутый интервал |
[п, п + 1 ]. Так как g — убывающая функция, то |
|
|
п+1 |
g ( n + |
1 )< | g(t)d t< g (n ). |
|
П |
Следовательно,
п+ 1
0 < А я = g (я)— J g ( t ) d t < g ( n ) — g ( n + 1).
П
Пусть М и N — произвольные положительные целые числа и Л4<+/. Тогда
2 |
А ,< 2 |
\ g ( n ) — g ( n |
+ 1)} = g ( M ) |
— |
g ( N + 1), |
n=M |
n—M |
|
|
|
|
и из условия g(t) > 0 при |
1 мы получаем |
||||
|
N |
|
|
|
|
|
2 |
At +? g Ш) |
для всех N > |
М . |
(5) |
|
п=М |
|
|
|
|
|
|
ОО |
|
со |
|
В частности, |
£ |
так что ряд |
|
Ап сходится. |
|
П=1 |
П=1 |
|
|
|
|
§ 3. Функция d(n) |
|
?1 |
|||
Положим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I ]АЯ = А. |
|
|
||
|
|
|
|
|
п= 1 |
|
|
|
|
Тогда в силу (5) |
мы имеем |
|
|
|
|
||||
|
N |
|
|
о° |
N |
|
|
|
|
А = Л а я+ |
2 |
Ля = 2 л я + 0 ( г ( ^ |
+ 1)) |
|
|||||
или |
Л — 1 |
|
n= N + l |
Я=1 |
|
|
|
||
N |
|
|
|
л+1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
А = 2 |
{^(л) — j ^ (о л } + |
0(g(N + |
1)), |
|
|||||
|
/1 = 1 |
|
|
|
п |
|
|
|
|
откуда |
следует, |
что |
|
|
|
|
|
||
|
Л! |
|
АЧ-1 |
|
|
|
|
|
|
|
2g (ra) = j |
#(/)<# + Л + |
0(£(ЛГ + |
1)). |
|
||||
|
л=1 |
|
1 |
|
|
|
|
|
|
Положим Л/^ f Z ] . |
Тогда |
последнее равенство |
перепи |
||||||
шется в виде |
|
|
|
|
|
|
|
|
|
|
|
m+i |
|
|
|
|
|
||
И |
ff(n) = |
J |
г(/)*# + Л + |
0 (g ([X ] |
+ 1)), |
|
|||
1<л<Х |
|
1 |
|
|
|
|
|
|
|
где п пробегает только целые значения. |
|
|
|||||||
Но функция g |
положительная и убывающая, |
так что |
|||||||
m+i |
|
|
|
|
|
|
|
|
|
|
j g (f)d t< g (X ), |
0-<g([X ] + l )< g ( X ) , |
|||||||
откуда |
х |
|
|
|
|
|
|
|
|
|
|
|
|
X |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
£ |
g(n) = |
\g(t)dt + |
A -f 0(g(X)), |
|
||||
|
1 < n<X |
|
|
1 |
|
|
|
|
|
что и требовалось |
доказать. |
|
|
|
|||||
Следствие 1. Существует постоянная у (постоянная Эйлера), такая, что
2 - J - “ l°gX + v + o ( - l - ) .
1<я<Х |
' |
7 |
72 |
Гл. VI. Арифметические функции и целые точки |
Следствие 2. Так как
х
Г- Ё — = log log X — log log 2, J t log/
TO
2 < n < X
где В — константа.
Мы можем теперь доказать следующую теорему:
Теорема 8. D(N)=N\ogN-\-0(N).
Доказательство. Как уже отмечалось, D (N) представ ляет собой число целых точек в правом верхнем квадран те (х, у) -плоскости, которые лежат на или ниже гипер болы xy= N , но не лежат на координатных осях. Очевид но, эти точки лежат левее прямой x — N и ниже прямой y = N (рис. 3). Сосчитаем число целых точек на каждой
|
|
|
X |
N |
|
|
|
|
Рис. 3. |
из |
вертикальных |
прямых, пересекающих ось абсцисс |
||
в |
целых |
точках. |
Число |
целых точек на вертикальной |
прямой, |
ординаты которых не превосходят величины |
|||
N/x, равно [N/x], |
так что |
|
||
N
я(ло = 2 Г—
I х
§ 3. Функция d(n) |
73 |
Положим [N/x] = N /x —б*, где O ^G ^Cl. Тогда
N N N
d (N) = n .'£1 ± |
- 1£ |
qx = n Z |
± + o (N), |
~ |
X |
л:=1 |
*= 1 |
x |
|
x = l |
|
|
||
N |
|
|
|
|
поскольку ^ 0*<Af, и по следствию 1 |
теоремы 7 |
|
||
*=i |
|
|
|
|
D (N )= N lo g N + 0 (N ).
Теорема доказана.
Теорема 8 может быть значительно усилена. В каче стве первого шага мы докажем следующий результат:
Теорема 9 (Дирихле). |
D(N)=N\ogN-\-(2y |
— 1)А7-f- |
|
-f-0( N) , где у — постоянная Эйлера. |
|
||
Доказательство. |
Гипербола x y = N симметрична от |
||
носительно прямой |
х = у . |
Следовательно, |
области |
ABGEO и CDOFG (рис. 4) содержат одно и то же число
целых точек. Общее число целых точек в первом квад ранте, которые лежат на или ниже гиперболы (но не ле жат на осях координат), равно поэтому удвоенному чис лу целых точек в области ABGEO минус число целых то
74 Г л. VI. Арифметические функции и целые точки
чек в квадрате OFGE. Таким образом, |
|
||||||||
D(N) = 2 |
|
1 — [К АГ]2 = 2 |
2 |
|
2 |
1 — [V N Y = |
|||
1 <x < Y n |
|
|
|
|
1<x < Y n |
l<y<N/x |
|
||
l<xy<N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- a S |
-jv- |
\Vn}\ |
|
|
|
|
|
|
|
x |
|||
|
|
|
|
|
|
K |
x < Y n |
|
|
Пусть [Nlx]=N/x—дх, |
О < 0 * < 1 , |
и [VN\ = V N —Q, |
|||||||
O ^ 0 < 1 . Тогда мы получим |
|
|
|
|
|||||
D(N) = 2N |
£ |
— — 2 |
J |
Qx — ( Y n — 0)2 = |
|||||
1< x < Y n |
|
|
i < x <-Yn |
|
|
|
|
||
= |
2N |
Y i |
-----^ —2 £ |
|
0^ + 20 j/N — б2. |
||||
Ho |
|
|
|
|
|
|
|
|
|
|
£ _ 0 , = |
O (K tf), |
Q2 — 0(1); |
|
|||||
|
l < x < Y n |
|
|
|
|
|
|
|
|
следовательно, |
|
|
|
|
|
|
|
|
|
D(N) = 2N |
V |
_ L _ a/ + |
0 ( ] / F ) . |
||||||
В силу следствия 1 |
теоремы 7 |
|
|
|
|
||||
D(N) = N |
logjV +(2y— 1)jV + 0 ( У Щ , |
||||||||
что и требовалось доказать.
Остаточный член О ( У N) в теореме 9 был улучшен
Г. Вороным и доведен до О (N1/3\og N ). Существует ги потеза, что остаточный член на самом деле есть
0(JV1/4+E). С другой стороны, известно, что остаточный член в теореме 9 не может быть доведен до 0 (N 1/i)-
§ 4. Функция а(п). Связанная с функцией d(ti) арифметическая функция о(п) определяется как сумма положительных делителей числа п. В общем случае мы можем определить
§ 4. Функция а(п) |
75 |
°k (я) = 2 dk, k = 0 ,\ ,2 ......
d\n
так что 0 o(n)=d(ti) и о(п) =oi(n).
Теорема 10. Арифметическая функция ак(п) мульти
пликативна.
Доказательство. Рассуждения, аналогичные рассуж дениям теоремы 2, показывают, что если (m, n) = 1, то
У й % й ' = 2 d*.
d|m d'|n |
d*\mn |
Отсюда следует мультипликативность а(п). Подобным
же образом доказывается и мультипликативность ah(n).
Г
Теорема 11. Пусть n = J~[ Р?1— каноническое разло-
i= i
жение числа п > 1 . Тогда
|
г |
(аг-Н)6 |
|
|
= П |
• |
<6 ) |
|
/-1 |
р * --1 |
|
Доказательство. |
Поскольку функция аи{п) |
мульти |
|
пликативна, мы имеем |
|
|
|
Г |
Г |
|
|
М « ) = П аМ ) = П I1 |
+ р? + . . .-ьр“<й)= |
||
i= l |
i= l |
|
|
|
-п |
|
|
i—1 |
|
и, в частности, при k = 1 |
|
|
г |
( а ;+1) _ |
|
0! (/г) = 0 (я) = [~ [ |
--- --------- -— . |
(7) |
»=i |
Pi — 1 |
|
|
|
С функцией о(п) связана старая проблема совершен ных чисел. Положительное число N называется совер
76 |
Г л. VI. Арифметические функции и целые точки |
шенным, если o {N )—2N, т. е. N равно сумме всех его положительных делителей, меньших N. Например, 6 и 28 являются совершенными числами.
Целые числа вида 2™— 1 называются числами Мерсенна, а простые числа такого вида называются просты ми числами Мерсенна.
Связь между простыми числами Мерсенна и совер шенными числами устанавливается следующей теоремой:
Теорема 12- Если |
2п+1— 1 является простым числом, |
то 2n(2n+1— 1) есть совершенное число. |
|
Доказательство. |
Пусть N — 2п(2п+1— 1 ) = 2 пр, где р |
простое. Тогда, согласно (7),
a(N) = (2n+1— 1) (pH-1) = (2»+'— 1)2“+1 =2Л^.
Следовательно, N — совершенное число.
|
Эйлер заметил, что этот результат можно частично |
||||
обратить, |
а именно, справедлива следующая теорема: |
||||
|
Теорема 13 |
(Эйлер). Каокдое четное совершенное |
|||
число имеет вид 2пр, |
где р = 2n+1— 1 есть простое число |
||||
Мерсенна. |
|
|
|
|
|
|
Доказательство. |
Пусть N = 2 nN' — совершенное чис |
|||
ло, где |
1, и N' — нечетное число. Тогда |
||||
|
|
|
a(N) =2N — 2n+1N'. |
||
В |
силу мультипликативности о мы имеем |
||||
|
|
|
a (N )= a (2 n)a(N'), |
||
и |
так как, согласно |
(7), а (2 п) = 2 п+1— 1, то |
|||
|
|
|
(2n+'— l)o (N ')= 2 n+lN'. |
||
Следовательно, |
(2n+I— 1) |Л7'. Если мы положим N' = |
||||
= (2»+1— 1 )N", |
то o (N ')= 2 n+lN", где N "<N '. Но N '+ |
||||
~{-N"=2n+lN" = o(N'). |
Таким образом, и N', и N" де |
||||
лят N' и их сумма равна a(N'). Значит, число N' не мо жет иметь других делителей и потому оно является про стым. Но N'—(2n+l— 1 )N". Следовательно, N' = 2n+l— 1, N"= 1. Тем самым теорема 13 доказана.
Неизвестно, будет ли бесконечным множество четных совершенных чисел (т. е. неизвестно, будет ли бесконеч
§ 5. Функция Мёбиуса у(п) |
77 |
ным множество простых вида 2п— 1). Неизвестно также, существуют ли нечетные совершенные числа.
Простые числа Мерсенна — это простые числа вида 2"— 1. Легко видеть, что если n > 1, а — положительное
целое число и ап— 1 является простым числом, |
то а = 2 |
||
и п также должно быть простым числом. |
Действительно, |
||
если а > 2 , то {а— 1) |(ап— 1). Если же |
а = 2 |
и n = kl, |
|
\ < k ^ l, то (2ft— 1) |(2n— 1). |
|
|
|
§ 5. Функция Мёбиуса |
р(и). Функция |
Мёбиуса |
|
р ( « ) — это арифметическая |
функция, которая |
опреде |
|
ляется следующим образом: |
|
|
|
(i)ц(1) = 1;
(ii)р(п) = (— l ) ft, если п есть произведение k различ
ных простых чисел;
(iii) р(д) = 0 в противном случае, т. е. если п делится на квадрат целого числа, отличного от единицы.
Из определения сразу же вытекает
|
Теорема |
14. |
Функция |
Мёбиуса |
р(п) |
мультиплика |
||||
тивна. |
|
|
|
|
|
|
|
|
|
|
|
Теорема 15. |
Справедливо соотношение |
|
|||||||
|
|
V! |
... |
[ 1, |
если п = |
1, |
|
|||
|
|
d,„ |
|
I 0, |
если п > |
1. |
|
|||
|
|
|
|
|
|
|
тп |
|
|
|
|
Доказательство. |
Пусть |
|
п = П р“* — |
каноническое |
|||||
|
|
|
|
|
|
|
i=1 |
‘ |
|
|
разложение числа /г > 1. |
Делители d |
|
числа п, для кото |
|||||||
рых p(d) ф 0, имеют вид |
|
|
|
|
|
|
||||
1, |
Pi, Р2, .... |
Pm, PiPi(i¥-j), |
PiPiPh(i¥:j=£k), . .., P\P2-Pm. |
|||||||
Тогда |
|
|
|
|
|
|
|
|
|
|
£ |
p (d) = p (1) + |
£ |
p (pt)-f |
Yi M'(P« Pi) + ... + p (рхРг-Рт) |
||||||
d\n |
|
l |
|
|
{ < / |
|
|
|
||
и, |
следовательно, |
|
|
|
|
|
|
|
||
s ^ . - ( 7 ) + C ) - ( r ) + . . . = « - n - o .
din
78 |
Г л. VI. Арифметические функции и целые точки |
Заметим, что функцию Мёбиуса можно определить, ис пользуя теорему 15, и вывести из нее свойства (i), (ii), (Ш).
Наиболее важные приложения этой функции основа ны на так называемых формулах обращения Мёбиуса.
Теорема 16 (первая формула обращения Мёбиуса).
Пусть f — арифметическая функция и
g(n) = h f(d ).
d\n
Тогда
|
|
d\n |
|
|
|
|
Доказательство. |
Мы имеем |
|
|
|
|
|
2 ^ ) g |
2 v ( d ) 2 w |
= |
|
|
|
|
d in |
din |
|
|
|
|
|
|
|
= |
|
2 /(<*') |
2 |
^ |
|
|
dd'\n |
|
d 'ln |
I |
n |
|
|
|
|
|
|
d' |
и, следовательно, по теореме 15 |
|
|
|
|
||
|
2 |
|
= |
^ л)- |
|
|
|
din |
|
|
|
|
|
Справедливо и обратное утверждение: |
|
|
||||
Теорема 17. Если |
|
|
|
|
|
|
а И |
= 2 |
= |
2 |
^ |
|
|
|
d\n |
|
d\n |
|
|
|
TO
f(n )= Y i h(d)-
din
|
§ 5. |
Функция Мёбиуса у(п) |
79 |
|
Доказательство. |
Мы имеем по теореме 15 |
|
||
2 м й - Е * ф - Е Е | * ( £ г ) « о - |
|
|||
d\rt |
d\n |
dm |
п |
|
|
|
d |
\~d |
|
- 2 / И 1 |
S |
- ж - |
‘ 'B |
'I-f |
|
В качестве приложения теоремы 16 рассмотрим соот ношение
^cp(d) = л, dm
которое было доказано в теореме 6 гл. II. Из теоремы 16 следует, что
ф («) = 2 |
= |
' |
(8) |
d\n |
|
dirt |
|
Другое приложение этой теоремы связано с функцией Мангольдта А, которая определяется следующим об разом:
А . ч_flog р, |
если п = |
рт, |
р простое, т > О, |
|
1 |
0 |
, если п =f= рт. |
||
Теорема 18. ^A fd) =log п. |
|
|
||
d\n |
|
|
г |
|
Доказательство. |
Пусть п = |
|
||
ПР^ — каноническое |
||||
|
|
|
t=i |
|
разложение числа n > |
1. Тогда |
по |
определению А мы |
|
имеем |
|
|
|
|
£ Л (Ф = |
£ £ Л (р ?)= |
S a i logP t ~ logn - |
d\n |
1=1 a = l |
1=1 |
Тем самым теорема доказана.