5) если pi = 2 и ai нечетно, вычисляем ();

степени ai применяем квадратичный закон взаимности;

7) если необходимо, возвращаемся к п. 1. Например,

/126\ /20\ \53)

[53)

/ 5 \

\53/

=(-1

,26-2

9.5. Символ Якоби. Изложенный выше метод вычисления символа Лежандра является неудобным в связи с тем, что при его выполнении приходится прибегать к сложной операции факторизации натуральных чисел. Чтобы избавиться от необходимости факторизовать числа рассмотрим обобщение символа Лежандра, называемое символом Якоби.

множители n=pj1 p2 foro целого числа а символ Якоби определяется равенством

в данном случае равенство () = 1 вовсе не обязательно означает, что число miM вычетом по модулю n. Например,

VisJ

=(-1)(-1)=1,

функции от двух аргументов. Замечательное свойство этого символа заключается в том, что он удовлетворяет практически всем тем же свойствам, что и символ Лежандра.

1. Если ai=a (mod n), то {) = (). 2-(l) = (S)(t)-

Ъ.Если (a,n)=l, mo(4) = (). 4.(i) = l, () = (-l)". 5.() = (-l)".

Доказательство этих свойств проводится с помощью п. (а) и (в) леммы из п. 9.2. Их предлагается выполнить самостоятельно в качестве упражнения.

Докажем лишь обобщение квадратичного закона взаимности.

= (-1)

-1 д-1 f п\

2 2 -

(m, n) = 1

тивном случае обе части равенства равны нулю. Предположим, что mn

pak

pk

Тогда no определению и свойствам символа Якоби получаем

j=1 i=Apj

Oj hi

\Рз)

Pi \4iJ

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

ПП(-1Г-

i=1 j=1

= (-1)

□

9.6. Доказанные свойства символа Якоби позволяют для любого простого нечетного го целого а, не прибегая к факторизации числа, вычислять значение символа Лежандра () с помощью следующего алгоритма.

1) если число а отрицательно, то выделяем сомножитель (-);

а а mod n а n

3) если ето в виде произведения а = 2*а1, где («1,2) = 1, и, если t нечетно, то вычисляем (;);

4) применяем к () квадратичный закон взаимности

-1 ai-i / п\

5) если необходимо, возвращаемся к п. 1. Например,

/136\

\ьз)

/30\

2 15

=(-1)

2 1 / 53\

= 1.

§ 10. Теорема Чебышева о распределении простых чисел

10.1. Вопрос о распределении простых чисел всегда вызывал большой интерес. В разной постановке он исследовался многими математиками.

Рассмотрим вопрос о поведении функции n(x), равной числу простых чисел тервале 1 < p x. Еще четырнадцатилетний Гаусс

всего ее приб лижает функция в 1808 г. Лежандр предложил формулу, которая с достаточно большой точностью дает число простых чисел - i,-, ios3QQ- Он проверил формулу для iC < ж < Ю*". В 1850 г. П. Л. Чебышев показал, что формула Лежандра неверна, и с помощью достаточно сложной техники получил следующие оценки

0,921

<7г(ж) < 1,106

ln x

ln x

В дальнейшем им были получены значения констант, более близкие 1

тический закон 7г(ж) с помощью теории функций комплексного

переменного. Точнее они показали, что функция

dt x

ln t ln x

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

10.2. Докажем следующую теорему, являющуюся упрощенным вариантом результата П. Л. Чебышева.

Теорема. Существуют две постоянные с- и с2 ше что 0 < <с1 < 1, с2 > 1 всех x 2 выполняются неравенства

xx с\-- < 7г(ж) < С2

ln x ln x

Для доказательства данных неравенств удобнее оценивать функцию

e(x) lnp,

называемую функцией Чебышева.

Лемма 1. При всех x 2 выполняется неравенство

e(x) < (4ln2)x.

Доказательство. В силу очевидного неравенства

22n >

2и и

p<2n

>

получаем Отсюда

2иln2 >в(2и) - в(и).

в(2т) < 2ln2(1 + 2+ ... + 2m-1) < (2ln2)2m, и для x = 2 терна. При 2m-1 < x < 2m имеем

e(x) < в(2т) < (2ln2)2m = (4ln2)2m-1 < (4ln2)x. □

Лемма 2. Существует значение с> 0 то для всех x 2 выполняется неравенство e(x) > cx.

Доказательство. Введем обозначения

tp(u) = maxi{k pk < и}, op(u) = max{k pk и}.

Сначала заметим, что tp(u) = [l(ygpuJ. Вторую величину подсчитаем по формуле

tp(n)

p< 2n

V(n!)

j=1 -

*p(n)

j=1

*p (2n)

< tp(2n)

В последнем неравенстве использована очевидная оценка О [2xJ - - 2 [xJ < 1. Отсюда

2n <

n + 1 n +2 2n

Следовательно, n

2n n

p<2n

p*p(2n)

p<2n

ln2 (2n)lnp [logp 2nJ lnp =E1 + E2,

p<2n p<2n

ln p

p<2n 2= E

1п2п ln p

p<2n

lnp 1lnp < О(2n)

Отсюда вытекает неравенство

в{2п) > пЫ2 - V2nln2n > сп,

где c>О - танта. Наконец, при 2n<x2n +1 получаем

в{х) в{2п) > спс->С1Ж, С1>0. □

Доказательство теоремы. Верхняя оценка. Имеем

(ж) > 1пр > In у(7г(ж) - 7г(у)) In у(7г(ж) - у).

Следовательно, с учетом леммы 1 получаем

, , 20(х) , ж ж

Ф) <-г + л/<81п2--+ Vx<C2--

ln x ln x ln x

при некоторой константе c2 > 1.

Нижняя оценка. Из неравенства

0(x) = lnp n(x) ln x

с помощью леммы 2 получаем

, , 0(x) x -г >с:

ln x ln x □

10.3. В качестве следствия из доказанной выше теоремы получа-n

pn n

кие константы О < сз < c4, что при всех достаточно больших п выполняются неравенства

can ln n < pn < C4n ln

Доказательство. При x = pn формулировка теоремы приобретает вид

pn pn

Cl-- <П<С2--.

ln pn ln pn

Верхняя оценка. Логарифмируя левое неравенство получаем

lnpn + ln с1 - lnlnpn < ln n, n

Inpn <lnp„+lnci -lnlnp„, 12

Pn < - nlnpn < - nlnn = С4П1ПП.

pn > n

p„ > - nlnpn > - nlnn = cnlnn. □ pn n

константах 0 < c5 < сб справедливы неравенства

C5 ln n < pn+1 - pn < C6 ln □