выполняются далеко не всегда. Кроме того, как следует из алгорит-

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

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

будем искать такие числа щых число n = 2k и, кроме того,

в качестве примитивного элемента w можно выбрать также некото-2

быстрое преобразование Фурье на ЭВМ, где используется двоичное представление чисел.

Теорема. Если n = w = 2q = при M = wn/2 + 1 ент n

является обратимым элементом кольца жмент w -прими-

Нам потребуются две леммы.

Лемма 1. В коммутативном кольце с единицей для любого элемента и n = 2k выполняется равенство

Доказательство. Применим индукцию по При k = 1 ра-

k - 1 k

= (1 + а)Е

i=o i=o

По предположению индукции получаем

a2i

]ra2i (1 + (а2)+ ),

что и требовалось доказать.

Лемма 2. При M = wn/2 + 1 О = w G всех 1 < i < n имеем

Ywij = О (mod M)

Доказательство. Согласно лемме 1 достаточно показать, что при всех 1 i < вдется j такое, что

i2j

= О (mod M)

Если i = 2s ще то полагаем j = k - 1 - s. Тогда

1 + wi2j =1

= 1 + (wn/2)* = 1 + ( - 1)* = О (mod M),

так как t нечетно.

числа n=2 M=wn/2+1=2qn/2+ ты. Элемент w=2q=1, причем wn/2 =-1+M=-1 (mod Mтсюдawn=1 (mod M). Наконец, лемма 2 гарантирует выполнение третьего условия, необходимого для

□

п. Элементы теории чисел

§ 8. Непрерывные дроби и их свойства

8.1. Напомним, что алгоритм Евклида для нахождения наибольшего общего делителя чисел и B A > B, заключается в последовательном выполнении операции деления с остатком применительно к последовательности чисел A = r-i,B = ro,ri,г2,rk до получения нулевого остатка rk+i = вде ri-2 = diri-i + ri i = 1,... ,k и rk-1 = dk+1 гда (A,B) = rk. Рассмотрим теперь получающуюся в данном алгоритме последовательность di,d2,..., dk+i. Нетрудно видеть, что эти числа удовлетворяют равенству

d2 +

Для краткости будем обозначать правую часть этого выражения через [di,d2,..., dk+i] и называть непрерывной (или цепной) дробью.

Непрерывные дроби появились в математике еще в XVI в. Широкое распространение они получили после работ X. Гюйгенса (XVII в.), который применял их для подбора зубчатых колес, с заданным передаточным отношением. Теория непрерывных дробей была систематически разработана Л. Эйлером, а затем Ж. Лагранжем.

Отметим простейшие свойства таких дробей.

и di , d2 , . . . , dn

равенства

[di,d2,...,dn] = di+

[di ,d2 ,...,dn] = k = 1, . . . , и - 1

[di,d2,...,dn\ =

[d2 ,...,dn j

di , d2, . . . , dn-2, dn-i + 1

di , . . . , dk +

[dk+1 ,...,dnj\

Теорема (о фундаментальном соответствии). Для любой последо-

ai , a2 , . . . , an, . . .

[ai,a2,... ,anj =

и =1,2,...

выполняются в том и только в том случае, когда выполняются матричные равенства

a2 1

Pn Pn-i

и = 2,3,

Po = 1 Qo = 0

Доказательство проводим индукцией по При и = 1 утверждение и- 1

ции для непрерывной дроби [аг,..., а„] = должно выполняться

равенство

f Xn-1 Xn-2 Yn-1 Yn-2J

с другой стороны, эти дроби связаны соотношением

= [ai, а2, , а„] = ai +

= ai

ai 1 + 1

" " [a2,... ,anj Xn-1

что полностью соответствует матричному равенству

Xn i

Pn Pn-i

Qn Qn-i

ai 1

1 Xn i Xn 2

Yn i Yn

□

Дроби [ai, аг,..., а„] = п= 1,2,... называются подходящими дробями. В качестве следствия из этой теоремы мы получаем практически все основные свойства подходящих дробей.

1. PnQn-1 - Pn-1 Qn =(-1)\ и =1, 2,...

Pn Qn и = 1, 2, . . .

Р„ (-1)" г1-\2

4- l: = «l

Pn Qn

Pn=anPn-i +Pn-2 Qn=anQn-i +Qn-2 и=2, 3, . . . 6. Q„ = a„Q„ i + Q„ 2 > Qn-i + Qn-2 > Ща-2 > , n = 2,3,...

8.2. Рассмотрим теперь вопрос о представлении действительных чисел непрерывными дробями. Пусть а - некоторое положительное действительное число. Выделим в нем целую и дробную части: а = [aJ + (а тагаем а1 = [а если {а} = О, то заканчиваем, а если {а} О, то получаем равенство а = ai + Повторяя

тельность а1, а2, , an, при каждом n выполняется равенство а = [а1, а2, , an, an n = 1, 2, тела an(an) называются неполными (полными) частными.

Возможны два случая: либо процесс закончится на некотором шаге ето равенство а = [а1, а2, , an при всех n выполняются неравенства а = [а1,а2, , an ]. В случае бесконечной последовательности а1, а2, , an, определим значение бесконечной непрерывной дроби [а1, а2, , an, ] как предел

lim -- = lim

(-1)" A

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

[ai, аг,..., а„] = п = 1,2,... для получившейся в результате применения данной процедуры (конечной, или бесконечной) последовательности а1, а2, , an,

n + 1 а

подходящей дроби, то выполняется одно из двух неравенств:

Рп -Рта+1 Qn Qn+1

-- <о. <

Доказательство. Рассмотрим действительную функцию / (x) = [а1, а2, , an-1, x]. Очевидно, что

/ (an) =

= а,

аи J 1 \

an+1 /

Рп+1

Qn+1

В силу приведенных выше свойств подходящих дробей для функ-

/(x)

/(x)=

хРп-1 + Рп-2 xQn-1 +Qn-2

/(x)

ной функцией. "Учитывая неравенства а„<а„ + <а„ +

, полу-

чаем, что в зависимости от того, монотонно возрастает или убывает /(x)

□

На самом деле нетрудно видеть, что должны выполняться неравенства

P1 Pa Р4 Р2

< < а < <

Q4 Q2

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

Теорема 1. Рациональные числа однозначно представляются в виде конечных непрерывных дробей с целыми неполными частными.

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

Предположим, что имеется два различных представления рационального числа а = [а1, а2, , an] = [61, 62, , сть ak = 6k - первое отличие в данных последовательностях. Тогда при некоторых О е< иО й< 1 должно выполняться равенство

(ak + e)Pk-1 + Pk-2 (6k + )Pk-1 + Pk-2

(ak + e)Qk-1 + Qk-2 (6k + )Qk-1 + Qk-2

Отсюда, рассуждая аналогично лемме, в силу монотонности гиперболы получаем, что ak + е = 6k + еорема доказана. □ Теорема 2. Иррациональные действительные числа однозначно представляются в виде бесконечных непрерывных дробей с целыми неполными частными. Наоборот, значением всякой бесконечной