(1962), 230-254]. Чтобы доказать теорему, мы сначала рассмотрим некоторые вспомогательные теоретико-числовые результаты, представляющие и самостоятельный интерес.

Лемма Р. Пусть р - простое число, а е - положительное целое число, такое, что р > 2. Если

x = 1 (по модулю р*), x 1 (по модулю р"*"), (l)

х = 1 (по модулю р), х 1 (по модулю р). (з)

Доказательство. Если х не кратно р, то оно может быть представлено в виде X = 1 + qp для некоторого целого д. По биномиальной формуле получаем

= ..,P-(i.i(5),P.i(),V.-.i(p,-y-")

Величины в скобках являются целыми числами, и к тому же каждый член внутри скобок, за исключением первого, кратен р. Для таких к, что 1 < к < р, биномиальные коэффициенты () делятся на р (см. упр. 1.2.6-10); следовательно.

делится на Последний член qP-pip->~ также делится на р, поскольку

(р - 1)е > 1, когда р" > 2. Итак, хР = I + 5р+ (по модулю р+), что и завершает доказательство. [Замечание. Обобщение этого результата приведено в упр. 3.2.2-11, (а).) I

Лемма Q. Пусть число тп допускает разложение на простые множители в виде

m=pl\..pt. (3)

Длина периода Л линейной конгруэнтной последовательности, определенной параметрами {Хо,а,с,тп), является наименьшим общим кратным длин Xj периодов линейных конгруэнтных последовательностей (Хо mod р, а mod р, с mod р, pf), l<j<t.

Доказательство. Если использовать индукцию по t, то достаточно доказать, что если mi и тг - взаимно простые числа, то длина Л линейной конгруэнтной последовательности, определенной параметрами (Хо,а, с, тхгпг), является наименьшим общим кратным длин Ai и Аг периодов последовательностей, определенных параметрами (Xomodmi, а mod mi, с mod mi, mi) и (Xomodma, amodm2, с mod ТП2, ТП2). В предыдущем разделе мы заметили (см. (4)), что если элементы этих трех последовательностей соответственно обозначены через Х„, У„ и Zn, то справедливо равенство

Уп - Хп mod mi и Zn = Хп mod тп2 для всех п > 0. Поэтому по закону D из раздела 1.2.4 находим, что

Хп = Xk тогда и только тогда, когда Yn = Yk и Zn = Zk- (4)

Пусть Л - наименьшее общее кратное Ai и Лг- Необходимо доказать, что А = А. Так как Хп = Ап+л для всех достаточно больших п, У„ = У„+а (следовательно, А кратно Ai) и Z„ = Zn+\ (следовательно, А кратно Аг). Таким образом, получим, что А > А. Более того, известно, что У„ = У„+а и Z„ = Zn+y для всех достаточно больших п; поэтому из (4) следует, что ЛГ„ = Хп+\- Это доказывает, что А < А.

Сейчас мы готовы доказать теорему А. Из леммы Q следует, что теорему достаточно доказать для случая, когда т является степенью простого числа, поскольку

=a = lcm(Ab...,At)<Ai...At <рГ...рГ

(1cm - наименьшее общее кратное. - Прим. перев.) выполняется тогда и только тогда, когда Xj = р для 1 < j < t.

Предположим поэтому, что т = р", где р - простое число, а е - целое положительное число. Поскольку утверждение теоремы очевидно при а - 1, можно считать, что а > 1. Период может иметь длину тп тогда и только тогда, когда каждое целое число х, такое, что О < х < т, встречается в этом периоде. Действительно, никакое значение х в периоде не может встретиться более одного раза. Таким образом, период имеет длину тп тогда и только тогда, когда период последовательности с начальным значением Ао = О имеет период длиной тп. Поэтому достаточно доказать теорему, когда Хо = 0. Из формулы 3.2.1-(6) следует, что

Если с и m не взаимно простые числа, то значение А„ никогда не может быть равно 1. Следовательно, условие (i) теоремы необходимо. Период имеет длину тп тогда и только тогда, когда наименьшее положительное значение п, для которого Хп = Хо = О, равняется п = тп. Из (5) и условия (i)следует, что доказательство нашей теоремы сводится к доказательству следующего утверждения.

Лемма R. Предположим, что 1 < а < р, гдер -простое число. Если X - наименьшее целое положительное число, для которого (а- - 1)/(а - 1) = О (по модулю р), то

. е Г а= 1 (по модулюр), где р>2,

Х = р тогда и только тогда, когда < , ,

(. а = 1 (по модулю 4), где р = 2.

Доказательство. Предположим, что А = р. Если а 1 (по модулю р), то (а" - 1)/(а - 1) = О (по модулю р*) тогда и только тогда, когда а" - 1 = О (по модулю р). Значит, условие ор" - 1 = О (по модулю р) влечет равенство аР = 1 (по модулю р), но из теоремы 1.2.4F следует, что аР = а (по модулю р). Таким образом, предположение, что а 1 (по модулю р), приводит к противоречию. Если р = 2 и а = 3 (по модулю 4), то из упр. 8 следует

(а" - 1)/(а - 1) = О (по модулю 2).

Эти рассуждения показывают, что в большинстве случаев необходимо, чтобы а = 1 + ЯР i где pf > 2 и q не кратны р, всякий раз, когда А = р.

Остается показать, что это условие достаточно для того, чтобы X = р. Применив лемму Р, находим, что для всех д>0

аР" = 1 (по модулю p), аР ф 1 (по модулю

следовательно.

(аР - 1)/(а - 1) = О (по модулю р»), {аР" - \)1{а - 1) 5 О (по мод>ЛЮ

В частности, {а - 1)/(а - 1) = О (по модулю р). Сейчас для конгруэнтной последовательности, определяемой параметрами (0,а, Х„, справедливо Х„ = (а" - 1)/(а - 1) modp. Значит, ее период равен Л, т. е. X„ = О тогда и только тогда, когда п кратно Л. Следовательно, р кратно Л. Это может случиться, тапько если Х=рЯ для"некоторых д и соотношения (6) означают, что Х = р.

Итак, теорема А доказана.

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

Хп+1 - а,Хп mod тп (7)

и значение Х„ = О может появиться, только если последовательность вырождается в нуль. Вообще, если d - любой делитель т и если Хп кратно d, все последующие элементы мультипликативной последовательности Xn+i, Хп+2, будут кратны d. Так что когда с = О, необходимо, чтобы Х„ и m были взаимн() простыми числами для всех п, что и ограничивает длину периода максимум до tp(m) - числа целых взаимно простых чисел с т, лежащих между О и т.

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

Согласно лемме Q период последовательности зависит исключительно от периодов последовательностей при т = р. Рассмотрим эту ситуацию. Итак, Хп = а"Хо mod р и ясно, что период будет иметь длину 1 (здесь можно только сказать, что дли1й1 периода не больше, чем е. - Прим. ред.), если а кратно р. Поэтому будем считать, что аир взаимно простые. Тогда период будет наименьшим целым числом А, таким, что Хо = аХо modp*. Если наибольшим общим делителем Хо и является, р, то это условие эквивалентно условию

а = 1 (по модулю р~). (8)

По теореме Эйлера (упр. 1.2.4-28) аР"> = 1 (по модулю р~-); следовательно, А является делителем

ip(p-f)=pf-(p-l).