непрерывной дроби с целыми неполными частными является иррациональное число.

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

lim -- = lim

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

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

□

8.3. В заключение отметим без доказательства еще два замечательных свойства непрерывных дробей. Во-первых, последовательности неполных частных, получаемые при разложении действительных чисел, могут рассматриваться как рациональные приближения этих чисел. При этом оказывается, что непрерывные дроби дают в определенном смысле наилучшие рациональные приближения. Во-вторых, бесконечные периодические непрерывные дроби и только они представляют множество чисел, являющихся квадратичными иррациональ-ностями, т. е. действительными решениями квадратных уравнений с целыми коэффициентами (Лагранж).

Отметим интересную связь непрерывных дробей с календарными стилями. Как известно, продолжительность года составляет 365,24220... суток. Этому числу соответствует периодическая дробь [365,4,7,1,3,...j, первые подходящие дроби которой равны соответственно

17 8

365, 365-, 365-, 365-.

4 29 33

Приближение 3651; - это так называемый Юлианский календарь, введенный в 47 г. до н. э. Юлием Цезарем, где каждый четвертый год - високосный. Новый Григорианский календарь дает приближение 365, что немного больше, чем 365 Jj. Этот стиль отличается

тем, что каждый сотый год - не високосный, кроме тех, число сотен которых делится на е. 40 имеют не 100 лишних суток). Хотя отставание Юлианского календаря было замечено еще в XV в., реформа была проведена только в конце XIX в. Наиболее же точный календарь ввел в Персии в 1079 г. персидский астроном и матема-

високосным считался четвертый, а восьмой раз - пятый. Это как раз приближение 365, так как имеется 8 лишних суток в 33 года.

§9. Квадратичные вычеты

9.1. Пусть p - те число. Целое число a называется квадратичным вычетом по модулю равнение x2 = a (mod p) имеет решение.

a mod p a p

вместо чисел цементы кольца вычетов Zp. Отметим простейшие свойства квадратичных вычетов.

1. Среди чисел {1,2,... ,p - 1} ровно половина являются квадратичными вычетами, а оставшиеся числа - нет.

Для доказательства рассмотрим отображение : x x2 мультипликативной группы кольца Zp в себя. Очевидно, оно является гомоморфизмом с ядром KerLp = {-1,образом p(Zp) будет множество ненулевых квадратичных вычетов.

2. Если Zp = {1,в,в2,...,вр-2}де в - примитивный элемент поля мемент a = ej будет квадратичным вычетом в том и

2y = j (mod p- 1)

p- 1

9.2. Символ Лежаждра. При изучении свойств квадратичных вычетов обычно выделяют две проблемы. Во-первых, как можно узнать является ли данное число квадратичным вычетом (задача распознавания), и, во-вторых, как найти решение данного сравнения (задача поиска решений). Мы покажем, что ответ на первый вопрос дать несложно. Для этого надо просто вычислить соответствующий символ Лежандра, что является алгоритмически несложной задачей. В то же время, задача поиска решений является алгоритмически сложной задачей и для нахождения решений требуется построение специальных алгоритмов.

Символ Лежандра, введенный им в 1798 г., определяется следующим образом:

О, 1,

а = О (mod p),

3 x, x2 = a (mod p), a mod p = 0, 2 x, x2 = a (mod p), a mod p = 0

Приведем основные свойства символа Лежандра. 1. -Бели ai = а (mod р), то {) = {).

2 (критерий Эйлера). () = (modp).

Доказательство. При а = О (mod p) равенство очевидно. а

а = 1 (modр), откуда =±1 (modр). При этом, если а = где О - wpvmwivmnbm элемент кольца Z„, то

а"" =1 (mod р)

:»i=0 (modp-1).

Последнее равносильно тому, что тао и а является квадратичным вычетом, т.е. () = 1. Аналогично рассматривается случай () = -1. □

3.(f) = ()().

Это и следующие два свойства являются очевидными следствиями свойства 2.

4.. Если {a,p)=l,mo{) = {). 5. (i) = l,(if) = (-l)"-

Для дальнейшего нам потребуется следующая лемма.

*-1 - 1

(mod 2)

22-2

s2 = 1 (mod 8)

Доказательство первого сравнения вытекает из равенства

(mod 2)

l(st-s-t + l) = l(s-l)(t-l),

где в правой части стоит четное число. Для доказательства второго

(s - 1)(s + 1) 8

( p2 - 1)

(р-1)-

. Рассмотрим функ-

x = 1 (mod 2), x = О (mod 2)

Так как число 8 является периодом этой функции, то можно рассматривать ее как функцию, заданную на элементах кольца вычетов та (в) леммы для нечетных и t выпол-/(st) = /(s)/(t)

Определим величину G € GF (p2) равенством

G /(j)wj

Покажем, что G = 0. Имеем

G = w - w3 - w5 + w7 = 2(w - w3),

так как w4 = Отсюда G2 =4(w2 - 2w4 + w6) = 8 = 0, a, следовательно, и G = оле GF(p2).

Подсчитаем теперь двумя способами величину Gp. С одной стороны

GP = {GyG=8G = С другой стороны.

Наконец, третье сравнение вытекает из равенства

l(.2t2-.2-t2 + l) = l(.2-l)(t2-l),

□

6.() = (-1).

{1, -1}

бом расширении поля Zp, то можно рассматривать данное равенство в поле GF (p2). В силу пункта (б) леммы справедливо сравнение p2 = 1 (mod 8 сегда содержится элемент w порядка 8 (например, надо взять примитивный элемент, имеющий

p /(x)

Gp = /(p)/(pj)upj = /(p)J2 /(Pj)uPJ = /(P)G.

j=o j=o

Теперь, приравнивая оба выражения и сокращая на О, получаем

□

9.3. Квадратичный закон взаимности Гаусса. Докажем еще одно замечательное свойство символа Лежандра, называемое квадратичным законом взаимности. Эмпирически он был открыт в 1783 г. Л. Эйлером. Первое полное доказательство бьшо дано в 1796 г. 19-летним К.Гауссом. Всего он предложил семь различных доказательств квадратичного закона взаимности.

равенство

Доказательство. Поступаем полностью аналогично доказательству последнего свойства. Перейдем к такому расширению OF(pm) шля держится элемент щдка q (на-

m=q-1

pq-1 = 1 (mod q)). Рассмотрим величину

G=y 1Ъ.

j=o q

Так как () = 0, то можно изменить нижний предел у обеих сумм.

k jk

.,j(1-k) =

выражение

k q - 1 q - 1

=i q

= (+1)

+ (-1)

= 0.

§ 9. КВАДРАТИЧНЫЕ ВЫЧЕТЫ Наконец, учитывая, что

q= [0- a=0,

j=o q, a = 0,

получаем

О2 =

1- El- Е

q k=i q j=o

,ji1-k) =

q={-l)q.

Отсюда О2 = тательно, и О = 0 тле OF(pm).

Подсчитаем теперь двумя способами величину Op. С одной стороны

GP={{-l)q) G={-1)

0-1 q-1 p-1

"2--2-

pitzi /q

О (mod p) .

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

OP =

j=o q

i,,pj

Gp=j:

j=o q

q j=o

V я У

Теперь, приравнивая оба выражения и сокращая на G, получаем требуемое равенство. Теорема доказана.

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

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

a a mod p a p

a = pl1 p2 .. .pkk и переходим к разложению в произведение