\input style
\chapter{��������� �� �����������}
���������, ����ɵ��˵ � ������ ���¾�ɵ� �����, ���������ǵ�� ��� ���
�����¾�µ�̽�� �������º�, °� � ��� ����������� ����¸�. ��ô��, ����
�� ���������� ���Ǹ�� �������, ¾�̺� Ǹ°� µ���� � �� ��������
����ǵ���� ��ľ���Ƹ� ��� ��ȵ��� ���Ƹ��̽�� ����� � µ� ���˼ ��
���°���� ���� ���ü˲��� ¾, �¾ �˻� ���Ǹ°��. ����� ¾��, �� ���ȵ
����� ���Ǹ���� ¾, �¾ ���� �º�˲��� ��� ����. ߾�¾��
ÿ�������� �������� ������ ǰ��� ������ ������; �˻� �����������
����������˵ ����º�, �¾�� �¾����� ÿ��������, � ��¾���
�� ����������� ��� ����� ����ȵ ��ľ���Ƹ� � ��¾�˵ �˻� �� ��µ����� ��Ȱ��.

Ҿ ������ ������ ������ ÿ�������� ������ �������Ⱥ� � �����Ǹµ�̽�
��ô�˼�. װǰ���� �¾ �ǵ�� ��ô����, °� ��� ����� µ�, ��� �����ÿ��� �
��ȵ��� ����Ǹ, Ǹ°µ�� ��Ϸ�µ�̽� ������ �����°����� ����, ����̺�
������� ù��� � ���� �� �¾ ��ȵ��� (���ǵ �� ����� ����� ¾�̺�
����������� ��� ����Ǹ). ڻ����ǵ���� �������� ����� ϲ�ϵ��� �����
�ǰ��� ѵ������ "Ը����ǵ���� ����������������"; �¾ ������ ����������
����°, � ��¾��� � ���Ƶ ������ ����� ��� �ñ����� "��������� �
���������µ������ ��������" ������ Ƶ�˹ �ϴ �����, ��� ���ϴ� � ��ñ�����
�ɵ ����ȵ��˼� ���������� �����ǰ���� �����Ǹµ�̽� �������̽˵ �������.
Ӿ�����, �¾ ������� �¾-¾ ������� �-�� ѵ������, ��� �»�Ǹ��
ÿ�������� �� ���������µ������ �������, � ¾� �²�¸�: "���� ��
����µ ��ȸ�� ������, �¾---ÿ��������; � ���¸���� ���ǰ� �¾---��������".

ܾ��� ������¸ ����� ������� � ���̷� ¾��, �¾ � ����� ¸�� �¾� ������
���� ��� ���������µ������ ��������, °� � �ǵ�� �����˵ ÿ��������, � ���
¾�� �¾�� Ǹ°µ�� �� ���ž������ ������ ������ ��� µ�, ����� ����ǰ
������, � ����� ��ô���, �� ����� "�Ƶ���", ��¾�˵ ú��˲��� �µ����
��ô���¸ ������� ÿ��������. �¸ �Ƶ��� ����� ������ɵ� ���ǵ���:
\descrtable{
\bf �Ƶ���  & \bf ޱ�������� \cr
00 & ������ǰ��� ������ ÿ��������, �� ��¾��� ����� �²�¸�� ����� ��,
     ���� ����� ��µ���� µ��°, � ��¾��� ���¸ ������ ����� ��ȸ�� "� ü�".\cr
%% 11
10 & ����°� ����ǰ, ��¾��� ���°��ϵ� ���ü����� ��� ���Ǹ°��˼
     ��µ������, �� �� �����°��ϵ� ������� ������ ��ô���µ�. ݰ ��ȵ��� °���
     ����Ǹ ����õ��� �� ����ȵ ����� ������; � ���Ƶ��� ��ȵ��� �����
     ������������ �������� � �ü���. \cr
20 & װ��ǰ ������� ��ô���¸, ��������ɰ� ���������, ������̺� ž��Ⱦ
     ����� µ���. ݰ ¾ �¾�� ���� ��ǵ��˲��ɸ� �²��, ����õ��� ��������
     15--20~�����. \cr
30 & װ��ǰ ü������� ��ô���¸ �/��� �������¸, ��� ô����²���µ�̽���
     ��ȵ��� ��¾��� ����õ��� ����ȵ ���� ǰ���. \cr
40 & �ǵ�� ��ô��� ��� ��ô������ ����ǰ, ��¾���, �����½�, ����õ�
     ����Ǹ�� � ���� ����¸ǵ���� ����¸�. ��������������, �¾ ��ô��� �����
     ��ȸ�� °��� ������, �� ��� �¾�� ��� ������õ��� ���Ǹµ�̽˹ �������
     �������; ����ǰ ��Ȱ���� ���������̽˼ �������. \cr
50 & ���������µ������ ��������, ��¾��� (������̺� �¾ �˻� �����½� ��¾��
     � ������ ���������) �ɵ �� ����Ǹ�� ô����²���µ�̽��� ��ȵ���. ����
     Ǹ°µ�� ������ ��ȵ��� �¾� ����Ǹ, ��� ���¾�µ�̽� ������ ��ñ��������
     ���; ����� ¾��, ��¾� ������ ����� �ô�� �ǵ�� ������µ���, ���� ���
     ����ɰ� ��ȵ���, ��� ����� ������� (��� �������, �¾ ��� ������̽�). \cr
}

ؽµ�������� �� �¾� "������ļ�ǵ����" Ⱥ���, ����� ���������, �¾
����ǰ�� �α�� �������¾ǽ�� �Ƶ���. ݰ������, �Ƶ���~17 ������� � ¾�,
�¾ ������ ÿ�������� ���� ���ǵ, ǵ� ÿ�������� ������� ��ô���¸. װ��ǰ
� �Ƶ����~50, ���� ��� �ô�� ��ȵ�� �����-���� Ǹ°µ���, � ������ɸ�
�������� ������ ����� ����� ����� ö� �Ƶ���~45.

в¾� ǵ�½� �°����� ������ �����¸��˵ �Ƶ���, �� ¾��, �¾ ���°��ϵ�
����Ǹ, ��ô�� ����������, ������̺� ��ô�˼� �¸ ����Ǹ �������� ���
����-¾ ��ó���; � ¾�� �� � ������� ǵ������ ��ɵ�²õ� ����������˹ ¸�
�����, ��¾�˵ �� ��Ȱ�� �������. ݰ�����, �¾ ���°�����˵ ���� �Ƶ���
���� ������̽�� �����°������ � �µ���� ��ô���¸ �����, �� � ��ɵ�
�� �ö�� ������������ ��� �����¸����ǽ˵, � �� ������½˵.

�° ����� �������� ��� Ǹ°µ��� ����� ������ �µ����� ��µ��¸ǵ����
�����¾��� � ����ȵ����¸, ���¾�� ����¾�˵ ÿ�������� ���������ǵ��
¾�̺� ��� Ǹ°µ��� � ��µ��¸ǵ���� ú�����. ���� � �����-����
ÿ�������� ��µ��¸ǵ���� ����¸� ��� ���û�°�� �����̷����� ����� ȸ����,
ǵ� �¾ ����ž���� ��� µ�, ���� � ������ �ǵ���� ��µ���õ�
���������������� ������¼��, ¾ ����� �Ƶ���� °���� ÿ��������
�°����� �ú�� "\emph{�}". ���� ��� ��ȵ��� ÿ�������� ����õ���
������ ���ȵ� ��µ��¸�� � ����ȵ� ������, ǵ� �¾ ���� � ���¾�ɵ�
%% 12
�����, ¾ �°����� �ú��~"\emph{��}". ߾��º�~"\emph{��}" �½δ� ��
ϲ�ϵ��� �����µ���²�� ¾��, �¾ ������ ÿ�������� ��ô���.

ߵ��� ����¾�˼� ÿ�������ϼ� �¾�� �������~"$\btr$"; �¾ ����ǰ��, �¾
������ ÿ�������� �������� ���Ǹµ�̽� � ��� ��������õ��� ��Ϸ�µ�̽�
�˿������. ᰼� ����� ���ü�����, ���¾ �� �������, �¾ Ǹ°µ�� (���
��ô���) �ô�� ��Ȱ�� ��� ����Ǹ, ��¾��-¾ �������� ������˵ �� ��� �
�˴�����. �¾ ������ �� ���Ǹ�, �¾ ��ó�� ����Ǹ �� �¾�� ��Ȱ��! ڰ��˹
Ǹ°µ�� ������ �� ������� ���� ����°���� ��ȸ�� ��� ����Ǹ �
�Ƶ����~10 � ����; ������� �� ������� �˱����, ����� ����Ǹ � �����
�������� �Ƶ����� ����õ� ��ȸ�� � ������ �ǵ����.

� ����ȸ��²� ÿ�������� ��������� �²���; ��� ����ɵ�� � ���Ƹ��̽��
������� � ���Ƶ �����. ߾�̷ùµ�� ��� �ô��;
� �²�� ������µ ¾�̺� ����� ¾��, ��� �� ��������� ���°¾ǽ� ������,
�¾�� ��ȸ�� ������ �����¾�µ�̽�, ��� �� ���� ��� ��ȵ��� ������
����Ǹ � ��� ��� �������. ���� ����ǵ� ����²���˹ �²��, ���� ���� ��
����²�µ�̽� ��°���� ��ȸ�� ������, ¾�̺� � �¾� ���ǰ� �²��,
����ɵ��˹ � �����, �ô�� ���Ǹµ�̽˼ � ������˼. ڰ� �������, �²��� �
����ǰ� ���������� �ǵ�� ���º�, �ŵ��¸ǽ�, °� ��� ��������������, �¾
Ǹ°µ�� ö� ǵ�½� ��°��� ��ȸ�� ������ ����²���˼� ������. ؽ���� �
����������� ��ȵ��� ������ ����ȵ ��ľ���Ƹ�, ǵ� ����ȸ������,
ǰɵ---��������. ҿ���� ��������, �¾ ����ǵ��˹ ���� �²�� �������� ���ȵ
�²�°, ����ɵ����� � �����, ��� �� �����µ �ȸ��� � �¾� �²�µ; � °���
���ǰ� ��¾� �˻ �� �ǵ�� ��Ϸ��, ���� �� �� ��� ����� ������ ��������
����ɸ�� ��� �� �¾�. � ��������ɸ� �������� ���¾�ɵ� �����
�ô�� ����ɵ�� ö� ������������ ��ȵ��� ����µ � ������ ��� ��¾��.

\bigskip
\centerline{\bf Ჾ��� �������� ������ǵ���}
\ctable{
\emph{#}\bskip\hfil&\bskip#\hfil\cr
$\btr$ &  ൺ�����õ��� \cr
� & � ��µ��¸ǵ���� ú����� \cr
�� & ����õ� ������ "���ȵ� ��µ��¸��" \cr
00 & ����õ� ������������ �²�° \cr
10 & ����¾� (�� ���� ������) \cr
20 & ������� ��ô���¸ (�� ǵ²���� ǰ��) \cr
30 & ߾��ȵ���� ��ô���¸ \cr
40 & Ի� "��¿���¸�ü�" \cr
50 & ���������µ������ �������� \cr
}

\excercises
\ex[00] �¾ ����ǰ�� ����º�~"\emph{�20}"?

\ex[10] ڰ��� ���ǵ��� ��� Ǹ°µ�� ����� ÿ��������, ����ɰ��˵ � �ǵ������?

\ex[�50] Ծ����µ, �¾ ����~$n$---Ƶ��� Ǹ���, $n>2$, ¾
���������~$x^n+y^n=z^n$ �������ȸ�� � Ƶ��� ������µ�̽�� Ǹ����~$x$, $y$, $z$.

%% 13
\chapno=2\chapnotrue\chapter{��ǰ��˵ Ǹ���} % 3
\epigraph
��Ϻ��, �¾ ��°�� �������� � ���ļ�¸ǵ���� ��¾��� ����ǵ��� ���ǰ����
Ǹ���, ���ȵ� ��� ��Ϻ�� ��������.
\signed Զ�� ľ� ݵ���� (1951)

\epigraph
��ó�˵ Ǹ��� ������ İ��ȸ��.
\signed �ͼ�ͻ� Զ����� (����� 1750)

\epigraph Lest men suspect your tale untrue, \goodbreak
Keep probability in view%
\note{1}%
{�¾�� �δ� �������� ��ȸ� ��������ϼ, �����µ �
 �����½��¸.---{\sl ����. �����.\/}
}.
\signed Զ�� �͹ (1727)

\subchap{��������} % 3.1
"��ǰ��� �˱����˵" Ǹ��� ����˲����� ������˼� ��� ����� �����ǽ�� Ƶ���.
 Ҿ� ����¾�˵ �������:
\medskip
a)~\emph{ܾ�����������.} ھ��� � ������� ��Ǹ���µ�̽��
��ȸ�� ������������ �������˵ ϲ�����, ���ǰ��˵ Ǹ���
��������� ���������� ������ � ����̽��¸. ܾ����������� ������ϵ��� ��
������ ��������: �� ϴ����� ĸ���� (ǰ�¸�� �����˲��� ���ǰ��˵
��ô������) �� ���µ����� ������� (������, �δ� �ž��� � ���� ǵ���
���ǰ��˵ ��µ����� �������).

b)~\emph{�˱����.} ��¾ �˲���, �¾ �������� ���� ��������� ������¾�
����¸ǵ��� �����ɵ�²���. ⾳�� �� ����¾�˵ ������� ������ϵ� ����Ǹ��
�²��� ���ǰ���� �˱����.

c)~\emph{������˹ ������.} Ի� ��ȵ��� ������� ����� ��Ǹ���µ�̽��
��µ��¸�� �˻� �������°�� �����ü��� µŽ���, �����̷��ɰ� ���ǰ��˵
Ǹ���. ޱ �¾� ������� �ϴ ����.

d)~\emph{���������������� ��� ��Ǹ���µ�̽�� ��ȸ�.} ��ǰ��˵ ���ǵ���
��ö�� ž��ȸ� ��¾ǽ���� ������ ��� ����°��� ��ĵ�¸����¸ �����ǽ��
������¼�� ��� ��Ǹ���µ�̽�� ��ȸ�. � �¾� ����� ��� �ô�� � ��������
��µ�������� ������ °��� �����̷������ ���ǰ���� Ǹ���. ߾�¾�� ������
ǵ� ������ ���� � ��ó�� ������¼��, �����, � ����̵� �����, �ô��
����������� ���ǰ��˵ Ǹ���.

e)~\emph{�����¸� ��ȵ���.} Ӿ�����, �¾ ������ �ú�����µ�� ���������
��ȵ���, ������ ����º� ��� ���¸. 徴�� ����
%% 14
���Ÿ, �¾ ����¾�˵ ���ĵ����� � ��������� ���������� ����Ű ������
°��� �������. ؽ���� �˲��� ����� ��������� �����ȵ��� ����������˵
��ȵ���. ߾����� ������������� °��� ����������� ��� ������¼��,
������ϵ��� � ��Ǹ���µ�̽�� ��ȸ���, �������� � ���ǰ��, ����� �����¸�
��µ�������������� ��ȵ��� ����� ������¸ � ���������� �ǵ°.
��ǰ������, ����� ¾��,---��ɵ�²����� ǰ��� ��¸���̽�� ����µ��� �
µ���� ���.

f)~\emph{ష���ǵ���.} ܽ���� �������� �����, °��� �����, ������ ���¸
��� ����δ�� �� ������� �û�º�, � ��ž��� � �¾� ������������
ô������²��. ⰺ�� �����Ƹ���˼ �����̷������� ���ǰ���� Ǹ���
������ϵ���, ��ǵ�� µ���� "ܾ�µ-ڰ���" ��ö�� ��ɸ� ������������� ���
���� ������¼��, � ��¾��� ��������� ���ǰ��˵ Ǹ���.
\medskip
�°�� ���ǽ˼ � �¾� ���µ �����ɰ�� ������̺� ����Ƶ� ĸ����������
���ö����� ¾��, �¾ �� °��� "���ǰ������". � ����¾��� ������ °����
�����°, ��� ���ǰ���� Ǹ���, ����¾ ���. Ằ���, ������---�¾ ���ǰ����
Ǹ���? Ế��� �� ������� � \emph{���������µ�̽��¸ �����������} ���ǰ����
Ǹ��� � ����������˼ \emph{������� �������������,} � �¾ ����ǰ��, ��ñ�
������, �¾ ������ Ǹ��� �˻� ����ǵ�� ���˼ ��������̽˼ �������,
��� ��Ϻ�� ��Ϸ� � ��ó��� ǻ����� ���������µ�̽��¸, � �¾ � ���� ����
������������ �����½���� ��������� � �α�� �������� ��µ�����.

\dfn{ల������˼} ���˲����� °��� �������������, ��� ��¾��� ������
��������� Ǹ��� ����������½�. ޱ�ǽ�, ���� ���Ƹ��̽� �� ���������
�¾-���� ����, ����� � ���� ���������˵ �������������.

ڰ���� �� ����¸ Ƹ�� ��~$0$ ��~$9$ ���°��ϵ� �������� ���� ������� ǰ���
���� Ƹ�� �� ��Ϻ�� ���ǰ���� (�����������) ���������µ�̽��¸ Ƹ��. �α��
�������� ���� ���� �������� Ƹ�� ������ ���°����� ��������
$\frac1/{100}$~ǰ��� ���� ���, �����ǰ�ɸ��� � ���������µ�̽��¸,
�~�.~�. ⵼ �� �����, ���� �� ���������� �����-���ô� ������½�� ���ǰ����
���������µ�̽���� �� �������� Ƹ��, � ��� ������ �� ��Ϸ�µ�̽�
�������� ����� $100\,000$~�û��, $100\,000$~������ �~�.~�. �
����²�µ�̽��¸ �����½���� °���� ����¸� �ǵ�� ����. װ������������ ��
�˿���ϵ��� � ������� ��� \emph{���������µ�̽��¸} °��� ���������µ�̽��µ�.

�α�� �������� ���������µ�̽���� �¾�� �� �����½�, ��� �
���������µ�̽����, ���¾�ɰ� �� ����� \emph{�û��.} Ѿ��� ¾��, �����¸�,
�¾ �� �˱����� ���ǰ��˼ ������� ���������µ�̽���� �� �������� Ƹ��.
����� ���������, �¾ ����˵ $999\,999$
%% 15
�� ��� ����� �û�. � � �¾� ���ǰ� �����½���� ¾��, �¾ ��������� Ƹ���
�ô�� �û��, ��� �ɵ � ¾ǽ��¸ �����~$\frac 1/{10}$, ���� �˱����
����²�µ�̽� ���ǰ����. Ի� ������ �¸ �²�������� ���ǰ� ��� ��������,
�� �� ����� ���� � ��� ��� ���¸����Ǹ�.

��ɵ�²õ� ������̺� �������� �ľ��û������� ž��ȵ� �������½��
����������� ���ǰ���� ���������µ�̽��¸. �� �ɵ �������� � �¾��
��µ������� ������� �~\S~3.5. ߾�� �� ���°¾ǽ� ���ø¸��� ������ ����.

ఽ�ȵ �ǵ�˵, �ö���ȸ��� ��� ����� ������ � ���ǰ���� Ǹ����,
�������˲��� �����, ������� ���¸ ��� ��°������� Ȱ�� �� ����, ��¾���
��������µ�̽� "��� ����õ� ������". � 1927~�.\ �.~⸿���� ��ñ�������
°�����, �������ɸ� ���ȵ $40\,000$~���ǰ���� Ƹ��, "��������̽� ������ ��
��ǵ¾� � ��������". ߾��� �˻� �������ø������ ���Ƹ��̽˵ ��ȸ��,
��Ű��ǵ��� �������˲��ɸ� ���ǰ��˵ Ǹ���. ߵ���� °��� ��ȸ�� �
1939~�.\ �����̷����� �.~Զ.~ڵ����� �~�.~�ͱ���¾�-Ἰ� ��� ��������
°����, ����ǰ�ɸ� 100~����� ���ǰ���� Ƹ��. � 1955~�.\ �������� RAND
Corporation ��ñ�������� ž��Ⱦ �����½˵ °����� � ��������� ���ǰ����
Ƹ��, ����ǵ���� ��ó�� °��� ��ȸ���. ط���½�� ��ȸ�� ERNIE,
�������˲��ɰ� ���ǰ��˵ Ǹ���, �������ϵ� �˸����ȸ� ������ �
���°����� ��µ���. [�.\ �°�̸ ڵ������ � �ͱ���¾�-Ἰ° �
{\sl Journal of the Royal Statistical Society,\/}
Series~A, {\bf 101} (1938), 147--166, � Series~�, {\bf 6} (1939), 51--61,
� °��� ����� �~{\sl Math.\ Comp.,\/} {\bf 10} (1956), 39--43.]

������ ����� �������� ��Ǹ���µ�̽�� ��ȸ� ��ǰ���� ������ ��ĵ�¸����
��¾��� ����ǵ��� ���ǰ���� Ǹ���, ��������� ��� �����̷������ �
����������. � ����Ƹ�� ����� ����°�� � � °���ư��, ������, �¾� ��¾�
����� ������ǵ���, ��Ϸ���˵ � ����ǽ˼ ������� ����¸ ��ȸ� � �����°��
������� ��� ����� Ǹ��� � ��ȸ�� � ¾� ���ǰ�, ����� °���ư ����˲�����
���Ⱥ�� ����º��. ����� ¾��, �����̽� ������½� ��¾���� °�����
�������, �� � ����ɵ ����� � ���� ����. ܾ��� ������������ � ��� ��ȸ��
¸�� ERNIE, �� � �¾� ���� ����˲����� ��ô����²���µ�̽˼, ��¾�� �¾
��� �»���� ��������� ���������� �����������¸ �¾��ǽ� ��Ǹ������,
�������˵ �����.

ݵ�����ȵ��²� ���� �¸� ��¾��� ����ô��� ��µ��� � ����ǵ��� ���ǰ����
Ǹ��� � ������� ���ļ�¸ǵ���� �����Ƹ� ��Ǹ���µ�̽�� ��ȸ��. ߵ��˼
°��� ���ž� � 1946~�.\ ��������� Զ�� ľ� ݵ����, �����̷����ȸ� ��¾�
"�������� ������°". ش�� �����ǰ���� � ¾�, �¾ ����˴�ɵ� ���ǰ����
Ǹ��� ���������� � �������, � ��µ� �� ���û�°° ����������� �������
Ƹ���. �����, ��������, �� �������˲��� ����¸���ǽ˵ Ǹ��� � �����¸�,
�¾ ����˴�ɵ� Ǹ��� �˻� �����~$5772156649$;
%% 16
������� ��� � �������, ����Ǹ�
$$
33317792380594909201,
$$
� ���¾�� ������ɵ� Ǹ��� �����~$7923805949$.

ܵ¾� �˷˲��� �����̽� �ǵ������ ����������. ڰ� ����� ���� ���ǰ����
������°���� °��� �������� ���������µ�̽����, ���� ����˹ �� ǻ��
��������� ��������� ����� ����ȵ�²�������?

�²�� �����ǰ���� � ¾�, �¾ �° ���������µ�̽���� \emph{��} ���ǰ���
�� \emph{�˳�ϴ��} ��� ���ǰ����. � ¸��ǽ�� ����������� ���ǽ� �� �����
���ǵ���, ��� ��Ϸ��� ��ó � ��ó�� ��� ��������ɸ� Ǹ���
���������µ�̽��¸; °��� �������, �����ǰ��˹ Ű���µ�
���������µ�̽��¸ �� ϲ�ϵ��� ������µ�̽˼. ؽ�ø¸��� ��¾� ��������
������° ������ �����̽� ž��Ⱦ "������ȸ����" ����˴�ɵ� Ǹ���.

� ���ǽ�-µŽ�ǵ���� ��µ������ ���������µ�̽��¸, �������˲���˵
��µ������������ ���������, ���˲����� \emph{���������ǰ��˼�} ���
\emph{��������ǰ��˼�.} ״��� �� �� �ô�� ���˲��� �� ����¾ ���ǰ��˼�
���������µ�̽���ϼ�, �������, �¾ ��� ¾�̺� \emph{����������
���ǰ»����} ���ǰ����. ݰ������, ���, �¾ ����� ������� � ���ǰ����
���������µ�̽��¸, �¾ ¾, �¾ ��� "�� ���Ƚ��� ���� ���ǰ����". �ǽ˵
��µ��¸ǵ���� ����������� ���ǰ����¸ ������ �~\S~3.5. ������°��˵
��µ������������ ��¾���� ���ǰ��˵ Ǹ��� ��������� �������˼� ���¸ ���
���� ���������� (ž��, ����ǽ�, ��� �� ����� �������� ERNIE � ��µ����).

޴���� �������ǰ�̽˹ "��¾� �������� ������°" ľ� ݵ����� ��������
������µ�̽� ��ô�˼ ��¾ǽ���� ���ǰ���� Ǹ���. ݵ���°¾� ���
�����ǰ���� � ¾�, �¾ ���������µ�̽��¸ ����� µ����Ƹ� ������ɰ���� �
����º�� Ƹ��� ���¾���ɸ��� ͻ����¾�. ݰ������, ���� �����-���ô� ǻ��
���������µ�̽��¸ �������� ����˼ �û�, ��� ��������ɸ� ǻ��� °���
�ô�� �ûϼ�. � ��ǰ�� ��¸������� ����� ����¾�˵ �ǵ�˵
��������� ͺ���������� � ��¾��� �������� ������°. Զ.~�.~������,
����°�ȸ� � ǵ����ŷ��ǽ˼� (� �� � ����¸���ǽ˼�) Ǹ�����, ��������
16~Ǹ��� � ��ǵ�²� ��ǰ�̽�� ���ǵ��� ���������µ�̽��µ� ޺�������,
�¾~12 �� ��� ��������� ���������µ�̽��¸, ����Ǹ���ɸ��� Ƹ����~$6100$,
$2100$, $4100$, $8100$, $6100$,~\dots, � ��� ���������µ�̽��¸ ����������
� �û�. ޱȸ��˵ ͺ���������� �� ������������ ��¾�� �������� ������°
������ �.~ܵ��������, ����������ȸ� �����˼ ������� ����ǽ˼� Ǹ�����.
ఱ�°� � 20-����ϴ�˼� Ǹ�����, �� �������, �¾ ��ɵ�²õ�
������ư�� �����ǽ�� Ƹ����, � ��¾�˵ ����� ����������
���������µ�̽��¸; ����� ������� ������ ����Ⱦ�� �� ��� �����~$142$.
ڰ� ¾�̺� ���������µ�̽���� ����������� � �û�, �����̽� ����� ��ǰ��
������º� ���ǰ���� Ǹ��� ������. Ӿ����� ��ô��� ��������
%% 17
� �����˼� Ƹ�����. ��� �� �.~仾�� (��.~ÿ�.~7) ���������
�����ü�˹ ��¾�, ��������ɸ� ���������������� ������������� Ƹ��� �
���������µ�̽��¸. ܵ¾� 仾��� ����õ� ������Ⱦ� ����¸ ��ȸ��,
ò���Ǹ���� ����� ������º� ���ǰ����� Ǹ��� ����� � ��� ���� � ����� ��
����������õ�, ��� ¾�̺� � ���������µ�̽��¸ ��ϲ�ϵ��� �����ǰ�ȵ���
����� Ǹ���.

⵾��¸ǵ���� �����°º� ��¾�� �������� ������° ���ö������ � ÿ�.~9
�~10. � ��ó�� �¾����, �¼�¸�, �¾, ����°� � 38-����ϴ�˼� ����ǽ˼�
Ǹ�����, �.~ܵ�������� �����ö�� ���������µ�̽����, ���¾����
�� $750\,000$~ǻ����, �»�ǰ�ɸ��� ��ó �� ��ó�. �°¸�¸ǵ���� µ���
���²������ ���ǰ��˹ Ű���µ� ����ǵ���� ���������µ�̽��¸ ��
$750000 \times 38$~��¾�. �¾ ���²�������, �¾, �������� ��¾� ��������
������°, \emph{�����} ����Ǹ�� ������˵ ���û�°��. ⵼ �� ����� ���
��������µ�̽�� ��ô������ ��Ǹ������ ��� �� �¾�� ����Ƚ� ��������.

ܽ���� ���Ǹ�� ���ǰ���� Ǹ���, ���û���˵ ���ǰ�, �����°¾ǽ� ž��ȸ.
����� ���̷���µ��� ����¸���� µ����Ƹ� �������� �� ���ǵ���. Ծ���̽�
ǰ�¾ �����-���ô� �°�˹ ������µ�̽� ��ô����²���µ�̽˹ ��¾�
���������� �� ������ ����������° � ��ó��� �������, � �������Ƚ��
���̷���µ�� ö� ��ǵ�� �� ����� �� ��� �����°º��. � �¾� ����� ��
ñ������, �¾ ����ô�� ���Ǹ�� ���˵ ����˵ �����²� ���Ǹ���
���ǰ���� Ǹ��� � ���Ǹ���� ��������� �¸ ������.

ط�����¸ ����¾� ���Ǹ� ���ǰ���� Ǹ��� �� °� �����. ݵ����̺� ��� �����
�¾� İ�� �������� �� ��¾�� ����Ⱦ� ���ǰ»����. ޽ ¾��� ��°���
������� İ�°�¸ǵ��� ž��ȸ� ���Ǹ� ���ǰ���� Ǹ��� �� ������
������ɵ�� ������������� ��¾��.

\alg K.(԰�Ǹ� "��������ǰ����" Ǹ���.) � ������� �¾�� ������¼� ������
����¸���ǽ�� ����¸ǽ�� Ǹ���~$X$ ����� ������������� � ��ó�� Ǹ���,
��¾���, ��� ��������������, ϲ�ϵ��� ������ɸ� ǻ���� ���ǰ����
���������µ�̽��¸. ڰ������ ��, ������¼ ������ϵ� ������°�� ���°¾ǽ�
���ǰ���� ���������µ�̽����, �� ����������, �¾ �¾ ������ �� °�.
���Ǹ�� ��ô�Ǹ ����������� ����. (�°µ�� ��� �ö�� ���Ⱥ�� ������� �
��°��. Ծ�°¾ǽ� ñ������� � ����Ⱦ� �������¸ ������¼�.)

\st[�˱���� Ǹ��� �µ��Ƹ�.] ��°������~$Y\asg\floor{X/10^9}$, ����� ���
����˼ �°�ȵ� Ƹ��� Ǹ���~$X$. (�� ���¾��� $Y+1$~��� Ȱ�� �~\stp{2}
��~\stp{13} ����Ǹµ�̽�. ��ó��� �������, ���ǰ���� Ǹ��� �ô��
��Ǹ������� \emph{���ǰ����} Ǹ��� ���.)

\st[�˱���� ���ǰ��˹ Ȱ�.] ��°������~$Z\asg\floor{X/10^8}\bmod 10$,
�.~�.~���������~$Z$ ���ǵ���, ������ �¾��� �� �°�ȸ��²� Ƹ��� Ǹ���~$X$.
ߵ���¸ � �˿������� Ȱ��~\stp{$(3+Z)$}.
%% 18
(��ó��� �������, ����� �� �˿���ϵ� \emph{���ǰ���} �˱����˹ Ȱ� ���������!)

\st[ޱ����Ǹ��~$X\ge 5\cdot 10^9$.] ����~$X<5\cdot 10^9$, ¾
��°������~$X\asg X+5\cdot 10^9$.

\st[������� ������°.] װ������~$X$ Ǹ����~$\floor{X^2/10^5}\bmod 10^{10}$,
�.~�.\ ��������� ������° Ǹ���~$X$.

\st[㼽�����.] װ������~$X$ ��~$(1001001001 X) \bmod 10^{10}$.

\st[����������������.] ����~$X<10^8$, ¾ ��°������~$X\asg X+9814055677$,
� ���¸���� ���ǰ�~$X\asg 10^{10}-X$.

\st[ߵ���°���� ���������.] ߾������ ���°�� $5$~�°�ȸ� � $5$~����ȸ�
Ƹ��, �.~�.\
��°������~$X\asg 10^5 \floor{X \bmod 10^5}+\floor{X/10^5}$, ���,
��-��ó���, ����� ������� $10$~Ƹ�� Ǹ���~$(10^{10}+1)X$.

\st[㼽�����.] (�.~Ȱ�~\stp{5}.)

\st[㼵��ȸ�� Ƹ���.] 㼵��ȸ�� �� ������� ������ �»�ǽ�� �� �û� Ƹ���
Ǹ���~$X$ (� ����¸ǽ�� �����°������).

\st[ܾ��ĸƸ������ ��~$99999$.] ����~$X<10^5$, ¾
��°������~$X\asg X^2+99999$, � ���¸���� ���ǰ�~$X\asg X-99999$.

\st[ݾ�����������.] (״���~$X$ �� ����� ���� ����˼ �û�.) ����~$X<10^9$,
¾ ��°������~$X\asg 10X$ � ���¾���� �¾� Ȱ�.

\st[ܾ��ĸƸ�������� �������� ������°.] װ������~$X$
��~$\floor{X(X-1)/10^5}\bmod 10^{10}$, �.~�.\ ����� ������� 10~Ƹ�� Ǹ���~$X(X-1)$.

\st[߾�¾����?] ����~$Y>0$, ¾ ü���ȸ��~$Y$ ��~$1$ � ��������� ��
Ȱ�~\stp{2}. ����~$Y=0$, ������¼ �����ȵ�, ���ǵ� µ��ɵ� ���ǵ���~$X$
�Ǹ°���� �����˼ ���ǰ��˼ Ǹ����.
\algend
(�µ���� �������� ���¾�̺� ������� ���������, ����������� �������˹ ��ȵ
������¼, �¾�� ǵ�����, Ǹ°�ɸ� �� µ���, �� ��� �� ��� ����������
����������, �¾ �� � ��� ��������.)

�Ǹ�˲�� ��� ���� ������¾������¸, ������˵ � ������¼�~K, �� �������
�� ������ ������������˼, �¾ � ��� ������� ����� ����Ǹ�� �������ǽ��
������²� ������½� ���ǰ���� Ǹ���? ݵ�! � ����²�µ�̽��¸, ��� ¾�̺�
�¾� ������¼ �˻ ���������� �� ���, ���¸ ����� �� �µ��Ƹ� ��Ȼ��� �
Ǹ���~$6065038420$, ��¾���, � ���û�°µ �������½��� ����������,
��������õ��� ���� � ���� (��.~°��.~1). ��� ��ó�� ��ǰ�̽�� ���ǵ���
���������µ�̽����, ��Ǹ��� � ǻ��� � �������~$7401$, ���¾�ϵ��� � ������
�������~$3178$.

ܾ���� �¾� ��¾��� �����ǰ���� � ¾�, �¾ \emph{���ǰ��˵ Ǹ��� ���̷�
�������˲��� � ������� ���ǰ��� �˱������� ������¼�.} �ö�� �����-���ô�
µ����.

� �¾� ����� �� ���������� ��¾�� ������º� ���ǰ���� Ǹ���, ������ž��ɸ�
��¾� �������� ������° � ������¼~K � ¾� �½�ȵ���, �¾ ��� ��� �����
µ���¸ǵ��� �����¸������
%% 19
\htable{ⰱ��ư~1}%
{ھ������̽�� ����������: Ǹ��� 6065038420 ��������õ��� � ���� � ������� ������¼�~K}%
{\strut #\bskip\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip&\vrule\bskip#\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip\cr
谳 & \hbox{$X$ (� ���Ƶ Ȱ��)} \span & 谳 & \hbox{$X$ (� ���Ƶ Ȱ��)}\span \cr
K1  & 6065038420 &     & K9  & 1107855700 \cr
K3  & 6065038420 &     & K10 & 1107755701 \cr
K4  & 6910360760 &     & K11 & 1107755701 \cr
K5  & 8031120760 &     & K12 & 1226919902 & Y=3\cr
K6  & 1968879240 &     & K5  & 0048821902 \cr
K7  & 7924019688 &     & K6  & 9862877579 \cr
K8  & 9631707688 &     & K7  & 7757998628 \cr
K9  & 8520606577 &     & K8  & 2384626628 \cr
K10 & 8520506578 &     & K9  & 1273515517 \cr
K11 & 8520506578 &     & K10 & 1273415518 \cr
K12 & 0323372207 & Y=6 & K11 & 1273415518 \cr
K6  & 9676627793 &     & K12 & 5870802097 & Y=2\cr
K7  & 2779396766 &     & K11 & 5870802097 \cr
K8  & 4942162766 &     & K12 & 3172562687 & Y=1\cr
K9  & 3831051655 &     & K4  & 1540029446 \cr
K10 & 3830951656 &     & K5  & 7015475446 \cr
K11 & 3830951656 &     & K6  & 2984524554 \cr
K12 & 1905867781 & Y=5 & K7  & 2455429845 \cr
K12 & 3319967479 & Y=4 & K8  & 2730274845 \cr
K�  & 6680032521 &     & K9  & 1620163734 \cr
K7  & 3252166800 &     & K10 & 1620063735 \cr
K8  & 2218966800 &     & K11 & 1620063735 \cr
    &            &     & K12 & 6065038420 & Y=0 \cr
}
�˿������� ������������ �����² ���ǰ���� ���������µ�̽��¸ � ������²��
����������. �ô�� �������� ����¾�˵ ��°��, ������Ǹ���ɸ� °���
���ǰ���� ���������, � ô����� �������� µŽ��� ���������� ���ǰ���� Ǹ���.
� ǰ�½��¸, ��������, �ô�� ��������, ��� °������ ����� � �������
��������� ���~���.

\excercises
\rex[20] �����������, �� ž¸µ, �� �����̷�� ���, ����Ǹ��
���ǰ���� ����¸ǽ�� Ƹ���. ڰ��� �� ����Ǹ������� ���� ��¾��� �� �������µµ?

a)~�º���µ µ��ľ��˹ ������ǽ�� � ��������̽�� ���µ (�.~�.\ º��µ ����Ƶ�
�ô� ó����) � ���̼�µ ������� Ƹ��� ������� �����ȵ����
������ �� �˱������ ���� ������Ƶ.

b)~ᴵ���µ ¾ �� �����, �� ������̷ùµ�� ����ȵ� Ƹ���� ������
\emph{��������.}

%% 20
c)~�����µ ����� � ľ��� ������̽��� �����ʹ��, ������ �� ����ư¸ ������
��¾���� ����ǵ�� Ƹ�����~$0$, $0$, $1$, $1$,~\dots, $9$, $9$. װ��ȸµ
Ƹ���, ��¾��� �ô�� ����ǵ�� ���Ž�� ����� ��°�����ȵ��� ���¸. (Ի�
ͺ��������° ��������õ��� ���̷������� �¾��� � ²����� ���¾� �ú��� �����Ž�����.)

d)~߾�°��µ �� ������ �ϴ�� � ��¾ǽ���� �������¸����� ����ǵ��� �ǵ�Ǹ�
ӵ����� (�����µ ���� ������¾������¸). Ҿ����̷ùµ�� ����ȵ� Ƹ����
Ǹ��� ���ǵ¾�, ����������� �ǵ�Ǹ���. (��������������, �¾ ������������
�ǵ�Ǹ� �����˲��� Ǹ��� ���ǵ¾� � ����¸ǽ�� ���� � ����� ��ǰ���
ͺ��������° �� �˻ ��°������ �� �û�.)

e)~ҷ��Ͻ�µ �� ���� ǰ�� �, ���� ���ý���� ������� ��ž�����
����� Ǹ�����~$6n$ �~$6(n+1)$, �˱���µ Ƹ���~$n$.

f)~߾�����µ ����µ�� ���ü��� ���ǰ���� Ƹ��� � ����� �� ��� �� �������.

g)~����� ¾ �� ����� ������� ��� ����ó.

h)~�����������, �¾ � ������ �ǰ�²õ� $10$~������½� �������½��
��� ��Ȱ���. ᾲ��ȵ��� ��������̽� ����ü��ùµ �� Ƹ����� ��~$0$
��~$9$. Ҿ����̷ùµ�� ������� ������µ�� ������.

\ex[�22] ڰ���� �����½���� �����ö��� ����� $100\,000$~ͺ��������� �α��
�������� ������� Ƹ��� � ���ǰ���� ���������µ�̽��¸, ���¾�ɵ� ��
$1\,000\,000$~����¸ǽ�� Ƹ��?

\ex[10] ڰ��� Ǹ��� ����Ǹ��� ����� ���������� ��¾�� �������� ������°
� Ǹ���~$1010101010$?

\ex[10] ߾ǵ�� ��� �˿������� Ȱ��~K11 ������¼�~K ���ǵ���~$X$ �� �����
���� ����˼ �û�? �¾ ������Ȼ� �� � ������¼��, ���� ��~$�$ ����� ���� �û��?

\ex[15] ޱ�����µ, ��ǵ�� � �α�� ���ǰ� ���̷� �������
����ǵ��� "�������ǽ��� ������²�" ���ǰ���� Ǹ��� � ������� ������¼�~K
(���� ���� �� �� ������Ȼ� ����������, ������������ � °��.~1), �Ǹ°�
������� �����½˼ ¾� İ��, �¾ �α�� ���������µ�̽����, ������°���� �
�����̷������� �¾�� ������¼�, � ���Ƶ ���ƾ� �°��� �������ǵ����?

\rex[�20] �����������, �¾ �� ž¸� ������°�� ���������µ�̽���� Ƶ���
Ǹ���~$X_0$, $X_1$, $X_2$,~\dots{} � ��µ�����~$0\le X_n < m$.
�����~$f(x)$---�α�� �ý�Ƹ�, °���, �¾ ����~$0 \le x < m$, ¾~$0\le f(x)<m$.
��������� ���������µ�̽����, ����ǵ���� � �������
���½�ȵ���~$X_{n+1}=f(X_n)$. (��������� ϲ������ ��¾� �������� ������°
� ������¼~�.)

a)~߾����µ, �¾ ���������µ�̽���� � ���Ƶ ���ƾ� �°�������
�������ǵ����, �.~�.\ ��ɵ�²��� °��� Ǹ���~$\lambda$ �~$\mu$, �¾
���ǵ���~$X_0$, $X_1$,~\dots, $X_\mu$,~\dots, $X_{\mu+\lambda-1}$ �����ǽ�,
��~$X_{n+\lambda}=X_n$,  �����~$n\ge \mu$. ݰ���µ ��������̽�� �
�������̽�� �������˵ ���ǵ���~$\mu$ �~$\lambda$.

b)~߾����µ, �¾ ��ɵ�²õ�~$n>0$, °���, �¾~$X_n=X_{2n}$;
�������ȵ� ���ǵ��� �¾��~$n$ ����� � ��µ�����~$\mu \le n \le \mu+\lambda$.
׽�ǵ���~$X_n$ ϲ�ϵ��� �����²���˼ � ¾� ������, �¾
����~$X_n=X_{2n}$ �~$X_r=X_{2r}$, ¾~$X_r=X_n$ (�������µ�̽�, $r-n$
���½�~$\lambda$).

\rex[20] �������µ ���û�°�� ����˴�ɵ�� ÿ��������, �¾��
��������� ����¸ǽ˹ ������¼ ������º� ���ǰ���� Ǹ���, ��������ɸ�
���Ǹ� ¸��~$X_{n+1}=f(X_n)$. Ұ� ������¼ ������: a)~�������� �����²��
�����°��������� ������º� ���ǰ���� Ǹ��� ���������µ�̽��¸, ���
¾�̺� ���¾�ϵ��� ����� �����ǰ�ȵ��� Ǹ���, b)~������°�� �� ����ȵ�
����~$\lambda$ ͻ����¾� ����� ��°������, ž�� ���ǵ���~$\lambda$ �������
�������½�, �~c)~�����̷����� ��������� ���ϳ� (�.~�.\ �� �����Ȱ����.
����¾ ���������� ��� ��Ǹ�����˵ ���������µ�̽˵ ���ǵ���).

\ex[28] ߾������� �������µ ��¾� �������� ������° ��� ���ǰ�
��÷��ǽ�� Ǹ���. a)~�� ����� ��ǰ�� � �α��� �� 100~���������
���ǵ���~$00$, $01$,~\dots, $99$. � ����̺�� ���ǰ�� �� � ���Ƶ ���ƾ�
������ � ���¾����� Ƹ���~$00$, $00$,~\dots? [\emph{������.} ݰǰ� �~$43$,
�� ����Ǹ� ���������µ�̽����~$43$, $84$, $05$, $02$, $00$, $00$,
$00$,~$\ldots\,$.] b)~Ế�̺� ����� ����Ǹ���� �����ǽ�� Ƹ����? ڰ���� �����
������� ������ �������� Ƹ���? c)~ڰ��� ��ǰ�̽�� ���ǵ���
%% 21
������ϵ� ����Ǹ�� ����� ������� ���������µ�̽���� �����¾���ɸ��� ͻ����¾�?

\ex[�14] Ծ����µ, �¾ ��¾� �������� ������°, �����̷��ɸ�
$2n\hbox{-���ǽ˵}$ Ǹ��� � ����������~$b$, ����� ������ɸ� �����°¾�:
��Ǹ��� � Ǹ���~$X$, � ��¾���� �°�ȸ� $n$~Ƹ�� ����� �û�, ���
��������ɸ� ͻ������ ���������µ�̽��¸ �°������� ��� ����ȵ � ����ȵ,
���� �� ��������� � �û�.

\ex[�16] ������� ������������� ����˴�ɵ�� ÿ��������, �¾ ����� �������
� ���������µ�̽��¸ ͻ����¾�, ������ɸ� �� Ǹ����~$X$, �
��¾���� \emph{���˵ ����ȸ�} $n$~Ƹ�� ����� �û�? �¾, ���� ����ȸ�
$(n+1)$~Ƹ�� ����� �û�?

\rex[�26] ��������� ���ǰ��˵ ���������µ�̽��¸,
�������˲���˵ ���Ǹ���� ¸�� ���������� � ÿ�.~6. ���� �� �˱�����~$f(x)$
�~$X_0$ ���ǰ��� � ������������, �¾ �α˵ �� $m^m$~���������
�ý�Ƹ�~$f(x)$ � $m$~��ǰ�̽�� ���ǵ���~$X_0$ ����������½�, ¾ ������
�����½���� ¾��, �¾ � ���Ƶ ���ƾ� ���������µ�̽���� ���������, �������
Ƹ�� � ������ �������~$\lambda=1$?

[\emph{װ��ǰ���.} �������������, ������˵ � �¾� ����ǵ, ����
����������� ������ ��µ�²���˼ ������� ���ü����� � "���ǰ����" ���Ǹ��
���ǰ���� Ǹ��� ��������� ¸��. ܾ��� �������, �¾ ��¾�, ������˹
������¼�~K, ������ ���� ��ž��� �� ������� ���Ǹ�, �����������˹ �����.
�ȵ��� ����Ǹ ���� ���� ¾��, ������̺� "��������̽�" �� ����� ����
����������, ����������� � °��.~1.]

\rex[�31] �����̷�� ������������� ����˴�ɵ�� ÿ��������, �����µ �������
����� Ƹ���, ��¾�˹ �����õ��� � ���������µ�̽�����. ڰ��� ������� �����
���¸���� ���������µ�̽����, ������ ǵ� ��ǰ�� Ƹ�������? (� ������ǵ����
ÿ�.~6 �� ž¸� ���������� ������� ���ǵ���~$\lambda$ �~$\mu+\lambda$.)

\ex[�42] ����~$f(x)$ �˱������� ���ǰ��� � ������ ÿ�.~11, ������
������� ����� \emph{������ ��������} Ƹ���, ����ǵ����� � ���û�°µ
��������� ��ǰ�̽��� ���ǵ���~$X_0$? [\emph{װ��ǰ���.} �²�� �����µ�
��� ���Ƹ��̽��� ���ǰ�, ����� � ��ǵ�²� �ý�Ƹ�~$f(x)$ ���������������
�����°�����; ��. ÿ�.~1.3.3-23.]

\ex[�38] ����~$f(x)$ �˱������� ���ǰ��� � ������ ÿ�.~11, ������ �������
Ǹ��� �����ǽ�� Ƹ����, ����ǰ���� � ���û�°µ ��������� ��ǰ�̽���
���ǵ���? (��.~�~ÿ�.~8(b).)

\ex[�15] ����~$f(x)$ �˱������� ���ǰ��� � ������ ÿ�.~11, ������
�����½���� ¾��, �¾ �� ���� �� Ƹ���� �� ����� �����~$1$,
����½���µ�̽� � �˱���~$X_0$?

\ex[15] ߾�������µ�̽����, �������˲����� � ������� ��¾��, ����������
� ÿ�.~6, ������ ��ǰ�� ���¾������ ����� ������� ����� ������º�
$m$~���ǵ���. �����������, �¾ �� ����ɸ�� ��¾� °�, �¾ $X_{n+1}$~µ����
������� �� ¾�̺� ��~$X_n$, �� � ��~$X_{n-1}$. �����̽� �����~$f(x, y)$
�ô�� °��� �ý�Ƹ�, �¾ ����~$0\le x$, $y<m$, ¾~$0\le f(x, y)< m$.
ݰǸ���� ������� ���������µ�̽���� � ��������̽��� �˱���~$X_0$ �~$X_1$.
װµ� ��������
$$
X_{n+1}=f(X_n, X_{n-1}) \rem{��� $n>0$.}
$$
ڰ��� ��������̽�� ����� ������� ����� ����Ǹ�� � �¾� ���ǰ�?

\ex[10] ޱ��ɸµ ���� ����˴�ɵ�� ÿ�������� °�, �¾�� $X_{n+1}$~��������
�� $k$~����˴�ɸ� ���ǵ��� ͻ����¾� ���������µ�̽��¸.

\ex[�22] ����ü��µ ��¾�, �������ǽ˹ ������������� � ÿ�.~7,
��� �����ö���� Ƹ��� ���Ǹ�� ���ǰ���� Ǹ��� ��ɵ�� ����,
�������������� � ����˴�ɵ� ÿ��������.

\ex[�50] �ȸµ ����Ǹ, ���°�����˵ � ÿ�.~11--15, ��� �����
��ɵ�� ���ǰ�, ����� $X_{n+1}$~������� �� ����˴�ɸ� $k$~ͻ����¾�
���������µ�̽��¸. ڰ���� ��~$m^{m^k}$ �ý�Ƹ�~$f(x_1, x_2,~\ldots, x_k)$
������ ��������������� ��� ����������½��. [\emph{װ��ǰ���.} ھ��ǵ�²�
�ý�Ƹ�, ���ɸ� \emph{��������̽˹} ������, ���������� � ÿ�.~2.3.4.2-23.]

%% 22
\subchap{��������� ���������� �������������� ��������� �����} % 3.2
� �¾� �������ĵ �� ���������� ��¾�� ����ǵ��� ���������µ�̽��¸
���ǰ���� ������, �.~�.\ ���ǰ���� \emph{����²�µ�̽�� Ǹ���~$U_n$,
���������� �������������� ����� �û�� � �����Ƶ�.} ⰺ ��� �
��Ǹ���µ�̽�� ��ȸ�� ����²�µ�̽�� Ǹ��� ������ �����°��ϵ��� �
������ǵ���� ¾ǽ�����, İ�¸ǵ��� �� �ô�� ������������ Ƶ�˵ Ǹ���~$X_n$
� ��µ����� ��~$0$ �� ����¾����~$m$. ⾳�� �����
$$
U_n=X_n/m
\eqno(1)
$$
������� � ��µ���� �� �û� �� �������. ޱ�ǽ�~$m$ �� ������� ����ȵ
��������̽��� Ǹ���, ��¾��� ����� �������� � ��ȸ���� ����� [($m$ �����
\emph{������� �����} (word size)]. ߾�¾��~$X_n$ ����� ��µ����¸������
(��������¸���) ��� Ƶ��� ���������� ��ȸ����� ����� � ����¸ǽ��
����¾�, ������������� ������, �~$U_n$ ����� �Ǹ°�� (�������̽�) ������,
�������ɵ��� � ¾� �� �����, � ����¾� � ������� ����� ����Ƹ�.

\subsubchap{۸����˹ ������ͽ½˹ ��¾�} % 3.2.1
ݰ����ȸ� �� �����½�� ������� ���Ǹ��� ���ǰ���� Ǹ��� �����°����� �����
ǰ�½˵ ���ǰ� ������ɵ� �ŵ��, ������������ �.~X.~۵����� �~1948~�.\
[�. Proc. 2nd Symposium on Large-Scale Digital Computing Machinery
(Cambridge: Harvard University Press, 1951), 141--146.] �˱����� ǵ����
"����ǵ���� Ǹ���":
$$
\vcenter{\halign{
$#$\hfil\bskip&#\bskip\hfil&\bskip\hfil$#$&${}#$\hfil\cr
X_0, & ��ǰ�̽�� ���ǵ���; & X_0&\ge 0; \cr
  a, & �����µ��;          &   a&\ge 0; \cr
  c, & �����ɵ���;         &   c&\ge 0; \cr
  m, & ���û�;             &   m&> X_0, m>a, m>c.\cr
}}
\eqno(1)
$$
⾳�� ������� ���������µ�̽���� ���ǰ���� Ǹ���~$\<X_n>$ ����ǰ���� �� ���½�ȵ���
$$
X_{n+1}=(aX_n+c) \bmod m, \rem{$n\ge 0$.}
\eqno (2)
$$

޽� ���˲����� \dfn{�������� ������ͽ½�� ���������µ�̽�����.}
%% 23

ݰ������, ���~$X_0=a=c=7$, $m=10$ ���������µ�̽���� �˳�ϴ�� °�:
$$
7,\; 6,\; 9,\; 0,\; 7,\; 6,\; 9,\; 0,\;~\ldots
\eqno (3)
$$
ڰ� ����� �� ������������ �������, ���������µ�̽���� �� ������
����˲����� "���ǰ����", ���� �˱�����~$X_0$, $a$, $c$, $m$ ��������̽�. �
��������ɸ� �������� �¾� ����� �ô�� �������� ����������� ����Ƹ��
�˱��� �¸� ���ǵ���.

������~(3) ���������õ� ¾� İ��, �¾ ������ͽ½˵ ���������µ�̽��¸
������ "��Ƹ���������", �.~�.\ � ���Ƶ ���ƾ� Ǹ��� �������� Ƹ��, ��¾�˹
���¾�ϵ��� �������ǽ�� Ǹ��� ���. �¾ �����²� �����ɵ ����
���������µ�̽���ϼ, ����ɸ� ��ɸ� ���~$X_{n+1}=f(X_n)$; ��.~ÿ�.~3.1-6.
߾�¾���ɸ��� Ƹ�� ���˲����� \dfn{��������.} Ի��� ������� �
���������µ�̽��¸~(3) �����~$4$. ൰�̽˵ ���������µ�̽��¸, ��¾�˼�
���̷�����, �����, ����ǽ�, ������µ�̽� ����Ⱦ� ������.

῵Ƹ��̽��� ÿ�������� ����ö����� ǰ�½˹ ���ǰ�~$c=0$, ����� ���Ƶ��
������º� ���ǰ���� Ǹ��� �����ž��� ������̺� �������. ߾��� �� ò����,
�¾ ������ǵ���~$c=0$ ü���Ȱ�� ����� ������� ���������µ�̽��¸, �� ���
�¾� ��� �ɵ ����� ����Ǹ�� �½���µ�̽� ����Ⱦ� ������. � �������ǰ�̽��
��¾�� ۵���� �˻� �����¾~$c=0$, ž�� ��¾� � ÿ��Ͻû �����������
�����̷������~$c\ne 0$. ش�� ����ǵ��� ����� ������� ���������µ�̽��µ�
�� �ǵ� ����ɵ���~$c\ne 0$ ����������� ⾼����
[{\sl Comp. J.,\/} {\bf 1} (1958), 83, 86] � ���������� �µ������
[{\sl JACM,\/} {\bf 7} (1960), 75--77].

ܽ����� ��¾���� µ����� \dfn{�û�¸�����¸��˹ ������ͽ½˹ ��¾�} �
\dfn{���Ȱ��˹ ������ͽ½˹ ��¾�} ����������� ��� ������ǵ��� ��������
������ͽ½�� ��¾��� �~$c=0$ �~$c\ne0$ ���²���²����.

Ҿ ���� �¾� ����� �ú��~$a$, $c$, $m$, $X_0$ �ô�� �����̷������� � ¾�
������, ��� �¾ �����¾ ��ȵ. Ѿ��� ¾��, �¾�� ÿ���¸�� ������ ��ȸ
ľ��û�, ����˲����� ������˼ ����������
$$
b=a-1.
\eqno(4)
$$
ܾ��� ����� �� �±������ ���ǰ�~$a=1$, °� ��� ��� �¾� $X_n=(X_0+nc) \bmod m$,
� �ǵ�����, �¾ ���������µ�̽���� �� ���ǰ����. Ұ�����~$a=0$
�ɵ �ö�. ỵ����µ�̽�, ��� ����¸ǵ���� Ƶ��� �� ����� ������������, �¾
$$
a\ge 2, \qquad b \ge 1.
\eqno (5)
$$

⵿��� ����� ����ɸ�� ���½�ȵ���~(2),
$$
X_{n+k}=(a^k X_n+(a^k-1)c/b) \bmod m,
\rem{$k\ge 0$, $n\ge 0$},
\eqno (6)
$$
������� $(n+k)\hbox{-�}$~ǻ�� ��ϼ� ǵ���~$n\hbox{-�}$. (ỵ�õ� ����¸��
�������� �� ǰ�½˹ ���ǰ�~$n=0$.) ߾�������µ�̽����, ���°�������
%% 24
�� ������� $k\hbox{-��}$~ǻ��� ��ȵ� ���������µ�̽��¸
�����õ� ��ó�� �������� ������ͽ½�� ���������µ�̽���� �
�����µ���~$a^k$ � �����ɵ����~$((a^k-1)c/b)$.

\excercises
\ex[10] � �������~(3) ���������õ��� ���ðƸ�, �����~$X_4=X_0$, °�
�¾ ���������µ�̽���� ����� ��Ǹ������ ���ǰ��. ݰ���µ ������ °���
�������� ������ͽ½�� ���������µ�̽��¸ �~$m=10$, � ��¾���
$X_0$~�����ǰ���� ¾�̺� ���� ���.

\rex[�20] ߾����µ, �¾, ����~$a$ �~$m$ ������� �����˵, Ǹ���~$X_0$
�ô�� �������ǵ��� ���¾������.

\ex[�10] ޱ�����µ, ��ǵ��, ����~$a$ �~$m$ �� ϲ������ ������� �����˼�,
���������µ�̽���� � �����-¾ ������ ��ô�ǽ�� �, �����½�, ��
���Ⱥ�� ���ǰ����. ߾�¾��, ����ɵ ������, �� �ô�� �°������ �˱�����~$a$
�~$m$  ������� �����˼�.

\ex[11] Ծ����µ ���½�ȵ���~(6).

\ex[�20] ι½�ȵ���~(6) �˿���ϵ��� ���~$k\ge 0$. ���� �¾ ��������,
����Ǹµ ľ��û�, ����������~$X_{n+k}$ ǵ���~$X_n$ � ���
\emph{����ưµ�̽��} ���ǵ���~$k$.

\subsubsubchap{�˱�� ���û�}%3.2.1.1
ὰǰ�� ���ô��, ��� ������̽� �˱����� Ǹ���~$m$. �� ž¸�, �¾��
���ǵ���~$m$ �˻� ���°¾ǽ� ����ȸ�, °� ��� ����� ������� �� ����� ����
����ȵ~$m$. (԰�� ���� ��������� ¾�̺� ���ǰ��˵ �û� � �������,
�� ����õ� �����~$m=2$, °� ��� ��� �¾� � ���ȵ� ���ǰ� ����Ǹ��� �����
$$
\ldots, 0, 1, 0, 1, 0, 1,\ldots\,!
$$

ܵ¾�� �����̷������ ���������� �������������� ���ǰ���� Ǹ��� ���
����ǵ��� ���������µ�̽��¸ �û�� � ������ ���ö������ �~\S~3.4.)

��ó�� İ�¾�, �����ɸ� �� �˱��~$m$---�¾ �������� ������º� Ǹ���: ��
ž¸� ��������� °��� ���ǵ���, �¾�� ������� ��Ǹ�����~$(aX_n+c)\bmod m$.

��������� � ��ǵ�²� ������� ��ȸ��~\MIX. �� ����� ��Ǹ�����~$y \bmod
m$, ����ɰ�~$y$ � ��������~|A| �~|X|, ��������ɸ� �������� ��~$m$.
�����������, �¾~$y$ �~$m$---������µ�̽˵ Ǹ���, ����� ñ�������, �¾ �
���û�°µ � ��������~|X| ��������~$y\bmod m$. ݾ °� ���
�������---������µ�̽� ��������� �����Ƹ�, �� ����� �������� �� �ǵ� �����
ô������ �˱���~$m$, ����ϲ ��� ����˼ \emph{������� �����} (�.~�.~��
������� ����ȵ ��������̽��� Ƶ���� Ǹ���, �����ɰ�ɵ���� � �����
��Ǹ���µ�̽�� ��ȸ��).

�����~$w$---°��� ��������̽�� Ƶ��� Ǹ���. ⾳�� �����Ƹ� ��������
������������ �� ���û�~$w$, � ü������� �� ���û�~$w$ °��� ������µ�̽�
����¾, °� ��� �ö�˹ ���û�°� ����ǰ���� � ����ȸ� ����ϴ��
������������. ⰺ�� �������, ������ɰ�
%% 25
��������� ��ĵ�¸��� ��Ǹ��ϵ�~$(aX+c)\bmod w$:
$$
\vcenter{
\mixcode
LDA  & A
MUL  & X
SLAX & 5
ADD  & C
\endmixcode
}
\eqno(1)
$$

൷û�°� ����ǰ���� � ��������~|A|. � ���Ƶ �˿������� �¾�
���������µ�̽��¸ ������ ����� �������¸ ������������, ������ ��¾����
����� �˺��Ǹ��, ������� ����� �� ��������� ��������~"|JOV *+1|".

ܵ��� ȸ���� �����½�� ¾���� µŽ��� ����� �����̷����� ��� ��Ǹ������ ��
���û�~$(w+1)$. ߾ ���Ǹ���, � ��¾��� �ô�� ������� ����, ���~$m=w+1$ ��
���ǽ� ��������~$c=0$. ߾�¾�� ��� �ö�� ��Ǹ����� ����¾~$(aX)\bmod(w+1)$.
�¾ ������ ������ɰ� ���������:
$$
\vcenter{
\mixcode
LDAN & X
MUL  & A
STX  & TEMP
SUB  & TEMP
JANN & *+3
INCA & 2
ADD  & =W-1=
\endmixcode
}
\eqno(2)
$$

� ��������~|A| µ���� ���������� ���ǵ���~$(aX)\bmod (w+1)$. ھ��ǽ�, ���
����� ���� �α˼ � ��µ����� �����~$0$ �~$w$. ߾�¾�� Ǹ°µ�� ������
������� ����� ��������, ��� ����� �������� °� ����� ���ǵ��� � �������
|A|-��������! (�ǵ�����, �¾ � �������� �� ����� ����ɰ���� Ǹ���,
����ȸ�, ǵ�~$w-1$.) �²�� ���¾�� � ¾�, �¾ ������������ ����������
¾��� � ¾�̺� ¾���, ����� ���û�°� �����~$w$ (� �������������, �¾
������ ������������ �˻ ����� �˺��ǵ�).

Ի� ������µ���²� ¾��, �¾ ���������~(2), � ����� ����,
��Ǹ��ϵ�~$(aX)\bmod (w+1)$, ����¸�, �¾ � ������~04 �� ��Ǹ°��
������� �������� ������������ �� �°�ȵ�. ߵ���������� ��� �¾�
�������¸ �� �����, �, ����~$aX=qw+r$, ���~$0\le r < w$, � ��������~|A|
����� �˿������� ������~04 �������� ���ǵ���~$r-q$. װ��¸�, �¾
$$
aX=q(w+1)+(r-q),
$$
� °� ���~$q<w$,  �����~$-w < r-q < w$. ỵ����µ�̽�,
$(aX)\bmod(w+1)$~����ϵ��� ����~$r-q$, ����~$r-q+(w+1)$ � ���������¸ ��
¾��, ����� �� ��������²~$r-q\ge 0$ ���~$r-q<0$ �˿���ϵ���.
���� �� ���̷õ��� ������ͽ½˼ ��¾��� �~$m=w+1$, �±���˲���
���ǵ���~$w$, ���� ��� ����ǰ����, �˲��� ���ǽ�
%% 26
�����, �������� � ���������~(2) �������
$$
\vbox{
\mixcode
JOV & * +1 \global\pcntr=-1
\dots \global\pcntr=8
JNOV & *+3
LDAN & A
JMP  & *-4
\endmixcode
}
\eqno(3)
$$

� ������� ��ž��� µŽ��� ����� ��Ǹ����� ������������ ���� Ǹ��� ��
���û�~$(w-1)$; ��.~ÿ�.~8.

� ��������ɸ� �������� ��� ������õ��� ü��� �����°�����~$m$ � ����
������������ ������� Ǹ���. �¾ ������� ������̽� �˱���� �����µ��~$a$.
� °��.~1 ���������� İ�¾����Ƹ� Ǹ��� ����~$w\pm 1$ ���¸ ��� ����
�����½�� �������� ����. Ѿ��� ����˵ ����˵ ����� ���¸ � �����
�.~ڰ������ͼ� �~X.~�ô���� (Factorization of~$y^n\pm 1$, Francis Hodgson,
London, 1925) ��� ����Ǹ�� � ������� ��¾��� �.~4.5.4.

�°µ�� ����� ������ ����������˹ ������, ��ǵ�� ��� °� ���������
���ǵ���~$m=w\pm1$, ���� ô���²� �˱���~$m=w$ ���¾�̺� �ǵ�����?
���Ǹ�� �����ǰ���� � ¾�, �¾ ���~$m=w$ \emph{����ȸ� Ƹ��� Ǹ���~$X_n$
������� ����� ���ǰ���, ǵ� �°�ȸ�.} ����~$d$ ϲ�ϵ��� ����µ���~$m$ � ����
% !!! �¸�� ������ ������ ���� °���, �¾�� �� ��°�� ��� ������
% � ���Ž�� ��������.
$$
Y_n=X_n \bmod d %
\hbox{\note{1}%
{���û�~(4) �������ϵ� ����� ���������µ�̽���� ��°º��~$\gamma_0$,
 $\gamma_1$,~\dots, $\gamma_n$, \dots, ��� ��¾���
 �˿������~(5).---{\sl ����. ���.\/}},
}
\eqno(4)
$$
¾, ��� ����� ����� ��������,
$$
Y_{n+1}=(aY_n+c)\bmod d
\eqno(5)
$$
(��� �������� ����¾��� Ƶ���~$q$, ��� ��¾����~$X_{n+1}=aX_n+c-qm$, �
���¾�� ����~$d$ ϲ�ϵ��� ����µ���~$m$, ¾, ����ž�� � ��������� ��
���û�~$d$, ����Ǹ�~(5)).

�¾�� ����������������� �������� ���½�ȵ���~(5), �����������, ��������,
�¾ ������� ����ǽ�� ��Ǹ���µ�̽�� ��ȸ��. ����~$m=w=2^e$, ¾ ����ȸ�
ǵ���� ��°~$X_n$ �����°����� Ǹ���~$Y_n=X_n\bmod 2^4$. ��ɽ����
ľ��û�~(5) �����ǰ���� � ¾�, �¾ ����ȸ� ǵ���� ��°~$X_n$ ��������
������ͽ½�� ���������µ�̽���� � ��������, �� �����Ȱ�ɸ�~16. �ǽ� °�
�� ����ȸ� ���� ��¾� �������ǽ� � ��������, ����˼ �����
����ȵ�~32. ᰼˹ �� ����ȸ� ���~$X_n$ ���� ������ϵ� ���¾Ͻ��� ���ǵ���,
���� ������ �������ǵ��� �����ϵ��� �� �û� �� �������.

߾������ ���ðƸ� �� ���������, �����~$m=w\pm 1$. � �¾� ���ǰ� ����ȸ�
����~$X_n$ ����� ���� °� �� ���ǰ���, ��� � �°�ȸ�. ݰ������, ǻ���
���������µ�̽��¸ ���~$w=2^{35}$ �~$m=2^{35}-1$
%% 27
{\catcode`.=\active\def.{\cdot}\offinterlineskip
\htable{ⰱ��ư 1}%
{ష�������~$w\pm 1$ �� �����˵ �����µ��}%
{\strut\hfil$#$\bskip&\vrule\hfil\bskip$#$\bskip\hfil\vrule&\bskip$#$\hfil\cr
2^e-1 & e & 2^e+1 \cr
\noalign{\hrule}
                             7.31.151 & 15 & 3^2.11.331 \cr
                           3.5.17.257 & 16 & 65537 \cr
                               131071 & 17 & 3.43601 \cr
                          3^2.7.19.73 & 18 & 5.13.37.109 \cr
                               524287 & 19 & 3.174763 \cr
                       3.5^2.11.31.41 & 20 & 17.61681 \cr
                          7^2.127.337 & 21 & 3^2.43.5419 \cr
                          3.23.89.683 & 22 & 5.397.2113 \cr
                            47.178481 & 23 & 3.2796203 \cr
                    3^2.5.7.13.17.241 & 24 & 97.257.673 \cr
                          31.601.180l & 25 & 3.11.251.4051 \cr
                          3.2731.8191 & 26 & 5.53.157.1613 \cr
                          7.73.262657 & 27 & 3^4.19.87211 \cr
                    3.5.29.43.113.127 & 28 & 17.15790321 \cr
                        233.1103.2089 & 29 & 3.59.3033169 \cr
              3^2.7 .11 .31 .151 .331 & 30 & 5^2.13.41.61.1321 \cr
                           2147483647 & 31 & 3.715827883 \cr
                     3.5.17.257.65537 & 32 & 641.6700417 \cr
                       7.23.89.599479 & 33 & 3^2 .67.683.20857 \cr
                       3.43691.131071 & 34 & 5.137.953.26317 \cr
                     31.71.127.122921 & 35 & 3.11.43.281.86171 \cr
              3^2.5.7.13.19.37.73.109 & 36 & 17.241.433.38737 \cr
                        223.616318177 & 37 & 3.1777.25781083 \cr
                      3.174763.524287 & 38 & 5.229.457.525313 \cr
                     7.79.8191.121369 & 39 & 3^2 .2731.22366891 \cr
              3.5^2.11.17.31.41.61681 & 40 & 257.4278255361 \cr
                      13367.164511353 & 41 & 3.83.8831418697 \cr
              3^2.7^2.43.127.337.5419 & 42 & 5.13.29.113.1429.14449 \cr
                     431.9719.2099863 & 43 & 3.2932031007403 \cr
               3.5.23.89.397.683.2113 & 44 & 17.353.2931542417 \cr
                7.31.73.151.631.23311 & 45 & 3^3.11.19.331.18837001 \cr
                  3.47.178481.2796203 & 46 & 5.277.1013.1657.30269 \cr
                   2351.4513.13264529 & 47 & 3.283.165768537521 \cr
         3^2.5.7.13.17.97.241.257.673 & 48 & 193.65537.22253377 \cr
                 179951.3203431780337 & 59 & 3.2833.37171.1824726041 \cr
3^2.5^2.7.11.13.31.41.61.151.331.1321 & 60 & 17.241.61681.4562284561 \cr
          7^2.73.127.337.92737.649657 & 63 & 3^3.19.43.5419.77158673929 \cr
         3.5.17.257.641.65537.6700417 & 64 &274177.67280421310721 \cr
\noalign{\hrule\smallskip\hrule}
                               10^e-1 &  e & 10^e+1\cr
\noalign{\hrule}
                       3^3.7.11.13.37 &  6 & 101.9901\cr
                         3^2.239.4649 &  7 & 11.909091\cr
                    3^2.11.73.101.137 &  8 & 17.5882353\cr
                        3^4.37.333667 &  9 & 7.11.13.19.52579\cr
                   3^2.11.41.271.9091 & 10 & 101.3541.27961\cr
                     3^2.21649.513239 & 11 & 11^2.23.4093.8779\cr
              3^3.7.11.13.37.101.9901 & 12 & 73.137.99990001\cr
         3^2.11.17.73.101.137.5882353 & 16 & 353.449.641.1409.69857\cr
\noalign{\hrule\smallskip\hrule}
}
}
%% 28
�ô�� �� ���Ⱥ�� ���ǰ���, ���� ��Ǹ����� ��ǵ�� �� ���û�~$31$, $71$,
$127$ ���~$122921$ (��.~�~°��.~1). � ¾ �� ����� ����ȸ� ���� �ô��
������ ���ǰ��� (�� ����� ������������� ��� ��ǵ�� ǻ����
���������µ�̽��¸, ����ǵ��˵ ��� ��������� �� ���û�~$2$).

��ó�� �����������---�¾ �˱�� � ��ǵ�²�~$m$ �������ȵ�� ����¾�� Ǹ���,
����ȵ��, ǵ�~$w$. ճ� ����� ���¸, �������� µŽ��� �.~4.5.4, � ��¾���
���� � °���ư ���²���²��ɸ� ����ȸ� ������� Ǹ���.

Ի� ����ȸ��²� ���������� ����ȸ� ���� �� ��ɵ�²����, � �˱��~$m=w$
ϲ�ϵ��� ������ ô����²���µ�̽˼ ��� �������, �¾ �����������,
���̷��ɸ��� ���ǰ��˼� Ǹ�����, ������ �¾ ���ü��.

\excercises

\ex[12] ط ÿ�.~3.2.1-3 �� �����Ǹ��, �¾ � ����� ���ȸ�
������ͽ½�� ���Ǹ��� Ǹ���~$a$ �~$m$ ������� �����˵. ߾����µ, �¾ �
�¾� ���ǰ� ����� ����Ǹ��~$(aX+c)\bmod w$ � ��������~$X$ � ������� �����
\emph{����} ������~\MIX, � �� ǵ�����, ��� � �������~(1).

\ex[16] ݰ��ȸµ ������������~\MIX, ô����²������� ���� ������ϼ:
\descrtable{
     ޱ��ɵ���: & |JMP RANDM| \cr
 ������� �ž��: & � �ǵ���~|XRAND| ���������� Ƶ��� Ǹ���~$X$. \cr
������� ��ž��: & $X\asg |rA|\asg(aX+c)\bmod w$, $|rX|\asg 0$,
                  ������������ "�˺��ǵ��".\cr
}
(ⰺ�� �������, � ���û�°µ ����ɵ��� � �¾� ������������ �ô��
����ǵ�� ������ɵ� ���ǰ���� Ǹ��� �������� ������ͽ½�� ���������µ�̽��¸.)

\ex[20] ڰ� ������� �� Ϸ˺� ��¾����~\MIX{} ����°���~$w-1$ ���������� ��
������� ���°?

\ex[10] ޱ�����µ ����� ���������µ�̽��¸ ������~(3).

\ex[20] ԰��, �¾ $m$~����ȵ ��������̽��� Ƶ����, ����ɰ�ɵ���� � �����,
�~$x$ �~$y$---������ưµ�̽˵ Ƶ�˵ Ǹ���, ����ȸ�, ǵ�~$m$. ߾����µ, �¾
��� ��Ǹ������ ������¸~$(x-y)\bmod m$ ���°¾ǽ� ǵ����� ������~\MIX{} � ��
�ö�� �����Ƹ� �������. ڰ���� ������Ȱ� ��������� ���
��Ǹ������ �ü��~$(x+y)\bmod m$?

\rex[20] � ����˴�ɵ� ÿ�������� ��������������, �¾ ��Ǹ°��� ��~$\bmod m$
���ɵ, ǵ� �������� ��~$\bmod m$. ��������µ ���������µ�̽��¸,
�������ɸ��� �� �������
$$
X_{n+1}=(aX_n-c) \bmod m.
$$

��ɵ�²���� �� ��� �»�ǰ���� �� �������� ������ͽ½��
���������µ�̽��µ�, ������������ � µ��µ? 㴾���� �� ��� ���
��ĵ�¸����� ��Ǹ������ �� ��ȸ���?

\ex[�24] ڰ��� Ű���µ��˵ ���������¸ °��.~1 �� ����µ �¼�¸��?

\rex[20] ݰ��ȸµ \MIX-��������� ��� ��Ǹ������~$(aX)\bmod (w-1)$,
�������ǽ��~(2). ׽�ǵ���~$0$ �~$w-1$ �� �ž�� � ��ž�� ��ȵ� ���������
����õ� �Ǹ°�� ͺ�������½˼�.

\ex[23] ݰ��ȸµ \MIX-��������� ��� ��Ǹ������~$(aX)\bmod (w-2)$,
�������ǽ�� ������ɵ��� � ÿ�.~8.

\subsubsubchap{�˱�� �����µ��}%3.2.1.2
 � �¾� ����ý�µ �� �������, ��� �˱����� �����µ��~$a$, �¾�� ����ǰ��
\emph{������ ��������̽��
%% 29
�����.} Ի� �α�� ���������µ�̽��¸, ���������ǵ���� ��� �����̷������ �
��ǵ�²� ��¾ǽ��� ���ǰ���� Ǹ���, ����� ����Ⱦ� ������. Ե��²�µ�̽�,
��� �� žµ����, �¾�� ������ �������� ���Ǹµ�̽� ����ȵ Ǹ���, ǵ� �¾
����ž���� ��� ��ȵ��� �����-���� ����� ����Ǹ. ߾�¾�� �������� �����
������ �������. �°µ�� ����õ�, ������, �������, �¾
����Ⱦ� ������---�¾ ¾�̺� ���� �� ����ž����� ��������� ���ǰ����¸ ��ȵ�
���������µ�̽��¸. ҿ���� �������� ������½� �����ǰ��˵
���������µ�̽��¸ � �ǵ�� ����ȸ� ��������. ݰ������, ���~$a=c=1$
���������µ�̽���� �������� ����¾ �~$X_{n+1}=(X_n+1)\bmod m$. �ǵ�����,
�� ������ �����~$m$, µ� �� ����� �� ����� ���̷� ������� ���ǰ����.
��ó�� �����������, �����ɸ� �� �˱�� �����µ��, �ô�� ��������� � �¾�
����� �����.

ⰺ ��� �������� ¾�̺� $m$~�����ǽ�� ���ǵ���, ����� ������� �� �����
�����Ȱ��~$m$. Ծ�¸���� �� ��������̽�� �����~$m$? ���������˹ ��ȵ
������ �����˲���, �¾ ��, ž�� �˱��~$a=c=1$ � �� �������� � ��������
���������µ�̽��¸. ������õ� \emph{���} �������˵ ������� �˱���~$a$
�~$c$, ��¾�˵ ���� ������ �����~$m$. [\emph{װ��ǰ���.} ھ��� ������
����� �����~$m$, ������ Ǹ��� ��~$0$ ��~$(m-1)$ �����ǰ���� �� ������
����� ���� ���. ߾�¾�� � �¾� ���ǰ� �˱��~$X_0$ �� ���ϵ� �� ����� �������.]

\proclaim ⵾���� A. Ի��� ������� �������� ������ͽ½��
���������µ�̽��¸ �����~$m$ ¾��� � ¾�̺� ¾���, �����
\item{i)}~$c$ �~$m$---������� �����˵ Ǹ���;
\item{ii)}~$b=a-1$ ���½�~$p$ ��� �α��� ����¾��~$p$, ϲ���ɵ���� ����µ���~$m$;
\item{iii)}~$b$ ���½�~$4$, ����~$m$ ���½�~$4$.

ش�� ������µ���²� �����½� �� ����� �° ���. ߵ���� ������µ���²�
µ����� � ������ ľ��û������ �˻� ���� �.~������������ ��� ǰ�½���
���ǰ�~$m=2^e$ ({\sl JACM,\/} {\bf 8} (1961), 383--389). Ծ�°¾ǽ����
�������~(i), (ii), (iii) � ��ɵ� ���ǰ� �˻� �������� 尻��� � Ծ������
({\sl SIAM Review,\/} {\bf 4} (1962), 230--254). Ի� ������µ���²�
µ����� ���������� ���ǰ�� ����¾�˵ ��������µ�̽˵ ���û�°�� µ����
Ǹ���, ��¾�˵ ��µ����� � ���� �� ����.

\proclaim ۵���~P. �����~$p$---����¾� Ǹ���, �~$e$---������µ�̽�� Ƶ���,
°���, �¾~$p^e>2$. ����
$$
x\equiv 1 \pmod{p^e}, \quad x \not\equiv 1 \pmod{p^{e+1}},
\eqno(1)
$$
¾
$$
x^p \equiv 1 \pmod{p^{e+1}}, \quad x^p \not\equiv 1 \pmod{p^{e+2}}.
\eqno(2)
$$

\proof �� �����~$x=1+qp^e$,  ���~$q$---����¾��� Ƶ���, �� ���½��~$p$.
%% 30
߾ ľ��û� ������ ����ȵ�
$$
\eqalign{
x^p&=1+\perm{p}{1}qp^e+\cdots+\perm{p}{p-1}q^{p-1}p^{(p-1)e}+q^pp^{pe}=\cr
&=1+qp^{e+1}\left(1+{1\over p}\perm{p}{2}qp^e+{1\over p}\perm{p}{3}q^2p^{2e}+
 \cdots+{1\over p}\perm{p}{p}q^{p-1}p^{(p-1)e}\right).\cr
}
$$

��������� � �������---Ƶ��� Ǹ���, ���ǵ� ������ ��������� ���½�~$p$, ��
�����ǵ���� ������� ǻ���. � ����� ����,
����~$1<k<p$, ¾~$\perm{p}{k}$ ������� ��~$p$ (��.~�~ÿ�.~1.2.6-10).
ỵ����µ�̽�,
$$
{1\over p}\perm{p}{k}q^{k-1}p^{(k-1)e}
$$
������� ��~$p^{(k-1)e}$. ߾������� ǻ��~$q^{p-1}p^{(p-1)e-1}$ �������
��~$p$, °� ���~$(p-1)e>1$ ���~$p^e>2$. ⰺ�� �������, $x^p=1+q'p^{e+1}$,
���~$q'$---Ƶ��� Ǹ���, ��¾��� �� ������� ��~$p$. ⵼ ���˼
������µ���²� �����ȵ��. (\emph{װ��ǰ���:} ����ɵ��� �¾��
���û�°° ���������� � ÿ�.~3.2.2-11~(a).)
\proofend

\proclaim ۵���~Q. {����� ����������~$m$ �� �����˵ �����µ�� ����� ���
$$
m=p_1^{e_1}\ldots p_t^{e_t}.
\eqno(3)
$$
\hiddenpar
Ի���~$\lambda$ ������� �������� ������ͽ½�� ���������µ�̽��¸,
�������ϵ���~$(X_0, a, c, m)$, ����� �������ȵ�� ��ɵ�� ���½���
����~$\lambda_j$ �������� �������� ������ͽ½�� ���������µ�̽��µ�
$$
(X_0 \bmod p_j^{e_j}, a p_j^{e_j}, c p_j^{e_j}, p_j^{e_j}),
\rem{$1\le j \le t$.}
$$
}

\proof ؽ�úƸ�� ��~$t$ ���°¾ǽ� ��������, �¾, ����~$r$ �~$s$---�������
�����˵ Ǹ���, �����~$\lambda$ ������� �������� ������ͽ½��
���������µ�̽��¸, �������ϵ���~$(X_0, a, c, rs)$, ����� �������ȵ��
��ɵ�� ���½��� ����~$\lambda_1$ �~$\lambda_2$ ��������
���������µ�̽��µ�~$(X_0 \bmod r, a \bmod r, c \bmod r, r)$
�~$(X_0 \bmod s, a \bmod s, c \bmod s, s)$.

� ����˴�ɵ� ������� (��.~ľ��û�~(5)) �� ������, �¾ ���� ������Ǹ��
ͻ������ �¸� ���� ���������µ�̽��µ� ���²���²����~$X_n$, $Y_n$, $Z_n$,
¾ �˿�������� ������ɸ� ���½�ȵ���:
$$
Y_n=X_n \bmod r \hbox{ � } Z_n=X_n \bmod s
\rem{��� ����~$n\ge 0$.}
$$
%% 31
߾�¾�� �� �����²�~D �.~1.2.4 ��ž���, �¾
$$
X_n=X_k  \rem{¾��� � ¾�̺� ¾���, �����~$Y_n=Y_k$ �~$Z_n=Z_k$.}
\eqno (4)
$$
�����~$\lambda'$---�������ȵ� ��ɵ� ���½�� ����~$\lambda_1$ �~$\lambda_2$;
�������, �¾~$\lambda'=\lambda$. ⰺ ���~$X_n=X_{n+\lambda}$ ��� ����
���°¾ǽ� ����ȸ�~$n$, �����~$Y_n=Y_{n+\lambda}$ (�������µ�̽�,
$\lambda$ ���½�~$\lambda_1$) �~$Z_n=Z_{n+\lambda}$ (�������µ�̽�,
$\lambda$ ���½�~$\lambda_2$), � ���¾��~$\lambda\ge\lambda'$. � ��ó��
�¾����, �� �����, �¾~$Y_n=Y_{n+\lambda'}$ �~$Z_n=Z_{n+\lambda'}$ ���
���� ���°¾ǽ� ����ȸ�~$n$. ߾�¾�� �� ���������~(4)
�����~$X_n=X_{n+\lambda'}$, �� ǵ�� ����ǰ��~$\lambda\le\lambda'$, °�
�¾~$\lambda=\lambda'$.
\proofend

⵿��� �� ��¾�� �������� µ�����~A. ؼ�� � ���� �����~Q, ���°¾ǽ�
�������� µ����� ��� ���ǰ�, ����� $m$~���� �µ���� ����¾�� Ǹ���. �
����� ����, ��������²�
$$
p_1^{e_1} \ldots p_t^{e_t}=\lambda=\���(\lambda_1,~\ldots, \lambda_t)
\le \lambda_1 \ldots \lambda_t \le p_1^{e_1}\ldots p_t^{e_t}
$$
����� ���� ����������� � ¾� � ¾�̺� ¾� ���ǰ�,
����~$\lambda_j=p_j^{e_j}$ ���~$1\le j \le t$.

߾�¾�� �����������, �¾~$m=p^e$, ���~$p$---����¾�, �~$e$---������µ�̽��
Ƶ��� Ǹ���. �ǵ�����, �¾ ���~$a=1$ µ����� �����������, ���¾�� �����
�Ǹ°��~$a>1$. Ի��� ������� �����~$m$ ¾��� � ¾�̺� ¾���, ����� ������
Ƶ��� Ǹ���~$x$, °���, �¾~$0 \le x < m$, �����ǰ���� �
���������µ�̽��¸ �� ����϶���� ������� (������̺� �� ���� �� ���ǵ���
�� ����� �����¸���� �� ������ ����� ������ ����). ⰺ�� �������, ������
����� �����~$m$ � ¾� � ¾�̺� ¾� ���ǰ�, ���� ����� �������
���������µ�̽��¸ �~$X_0=0$ �����~$m$, �¾
������˲��� �������������~$X_0=0$. ط. ľ��û�~3.2.1-(6) �����
$$
X_n=\left({a^n-1 \over a-1}\right) c \bmod m.
\eqno (5)
$$
���� Ǹ���~$c$ �~$m$ �� ϲ������ ������� �����˼�, $X_n$ ������� �� �����
���� �����~$1$. ߾�¾�� �������~(i) ����˲����� ����ž���˼. ߵ����
����� �����~$m$ ¾��� � ¾�̺� ¾���, ����� �������ȵ� ������µ�̽��
���ǵ���~$n$, ��� ��¾����~$X_n=X_0=0$, °����, �¾~$n=m$. ⵿��� �
����~(5) � �������~(i) ��Ȱ µ����� �������� � ������µ���²� ������ɵ��
�²��������.

\proclaim ۵���~R. �����������, �¾~$1<a<p^e$, ���~$p$---����¾� Ǹ���.
����~$\lambda$---�������ȵ�  ������µ�̽��  Ƶ���, ���
��¾����~$(a^\lambda-1)/(a-1)\equiv 0 \pmod{p^e}$, ¾
$$
\lambda=p^e\hbox{¾��� � ¾�̺� ¾���, ����� }
\cases{
a\equiv 1 \pmod{p} & ��� $p>2$,\cr
a\equiv 1 \pmod{4} & ��� $p=2$.
}
$$
%% 32
\proof �����������, �¾~$\lambda=p^e$. ����~$a\not\equiv 1 \pmod{p}$,
¾~$(a^n-1)/(a-1)\equiv 0 \pmod{p^e}$ � ¾� � ¾�̺� ¾� ���ǰ�,
�����~$a^n-1\equiv 0 \pmod{p^e}$. �������~$a^{p^e}-1\equiv 0 \pmod{p^e}$
¾��� ����õ�, �¾�� �˿���ϻ��� ���½�ȵ���~$a^{p^e}\equiv 1 \pmod{p}$.
ݾ �� µ�����~1.2.4F ����õ�, �¾~$a^{p^e}\equiv a \pmod{p}$; °���
������� ����ǰ��~$a\not\equiv 1 \pmod{p}$, �¾ �������� �
���¸����Ǹ�. ���� ��~$p=2$ �~$a\equiv 3 \pmod{4}$, ¾ �� ÿ�.~8
�����~$(a^{2^{e-1}}-1)/(a-1)\equiv 0 \pmod{2^e}$. �¸ �����������
�������˲��� ����ž������� ������²�~$a=1+qp^f$, ���~$p^f>2$, �~$q$ ��
���½�~$p$ ��� �α��~$\lambda=p^e$.

��°���� ��������, �¾ �¾ ������� \emph{���°¾ǽ�} ��� �˿�������
���½�ȵ���~$\lambda=p^e$. ߾�¾��� �����̷�� �����~P, ��ž���, �¾
$$
a^{p^g}\equiv 1 \pmod{p^{f+g}}, \quad
a^{p^g}\not\equiv 1 \pmod{p^{f+g+1}},
$$
� ���¾��
$$
\eqalign{
(a^{p^g}-1)/(a-1) &\equiv 0 \pmod{p^g}, \cr
(a^{p^g}-1)/(a-1) &\not\equiv 0 \pmod{p^{g+1}}.\cr
}
\eqno(6)
$$

� ǰ�½��¸, $(a^{p^e}-1)/(a-1)\equiv 0 \pmod{p^e}$. ⰺ�� �������, �
������ͽ½�� ���������µ�̽��¸~$(0, a, 1, p^e)$
�����~$X_n=(a^n-1)/(a-1) \bmod p^e$; ���¾�� ����� �� ������� �����~$\lambda$,
�.~�.~$X_n=0$ ¾��� � ¾�̺� ¾���, �����~$n$ ���½�~$\lambda$. ỵ����µ�̽�,
$p^e$ ���½�~$\lambda$. �¾ �������� ¾�̺�, ����~$\lambda=p^g$ ���
����¾����~$g$. ط ���½�ȵ���~(6) ����ǰ��~$\lambda=p^e$, �¾ �����Ȱ��
������µ���²�.
\proofend

⵿��� �����ǵ�� � ������µ���²� µ�����~A.
\proofend

� �����ǵ��� �¾�� ������� ���������� ���Ƹ��̽˹ ���ǰ� Ǹ�¾
�û�¸�����¸���� ���Ǹ���, ��� ��¾���~$c=0$. ��� ��� �¾� ������º�
���ǰ���� Ǹ��� �����ž��� ������̺� �������, µ�����~A �����˲���, �¾
�������� ��������̽�� ����� ������� ���̷�. Ե��²�µ�̽�, �¾ ������
�ǵ�����, °� ��� ǻ��� ���������µ�̽��¸ ô����²����� ���½�ȵ���
$$
X_{n+1}=aX_n\bmod m,
\eqno(7)
$$
� ���ǵ���~$X_n=0$ ����� � ��� �����¸����, ¾�̺� ����
���������µ�̽���� ����������� � �û�. Ҿ��ɵ, ����~$d$---�α��
����µ��~$m$ � ����~$X_n$ ���½�~$d$, ��� ��������ɸ� ���ǵ���~$X_{n+1}$,
$X_{n+2}$,~\dots{} ¾�� ���½�~$d$. ߾�¾�� ���~$c=0$ ����µ�̽�, �¾��
$X_n$~�˻� ������� ������ �~$m$ ��� ����~$n$, � �¾ ������Ǹ���� ����� �������.

ܾ��� �������� ��������� ����Ⱦ�� �������, ���� ���� �� ���°�����,
�¾��~$c=0$. ߾��°���� µ���� ���¸ °��� �������,
%% 33
���������ɸ� �����µ��, �¾�� � � �¾� ǰ�½�� ���ǰ�
����� ������� �˻� ��������̽�.

������²�� �����~Q ������ ���������µ�̽��¸ ��������� �������ϵ���
��������� ���������µ�̽��µ� �~$m=p^e$, °� �¾ ���������� ������ °���
���ðƸ�. �� �����~$X_n=a^n X_0 \bmod p^e$, � ����, �¾ ����� �������
�����~$1$, ����~$a$ ���½�~$p$\note{1}%
{����~$a$ ���½�~$p$, ¾, ����ɵ ������, ������ ��
 ������ž���~$e$.---{\sl ����. ���.\/}
}. ߾�¾�� �˱����~$a$ ������� �����˼
�~$p^e$. ⾳�� ������
����� �������ȵ�� Ƶ����~$\lambda$, °����, �¾~$X_0=a^\lambda X_0 \bmod p^e$.
���� �������ȸ� ��ɸ� ����µ��~$X_0$ �~$p^e$ ����~$p^f$, �¾ �������
ͺ�������½� ������ɵ��:
$$
a^\lambda \equiv 1 \pmod{p^{e-f}}.
\eqno(8)
$$
߾ µ����� ������ (ÿ�.~1.2.4-28)
$$
a^{\varphi(p^{e-f})} \equiv 1 \pmod{p^{e-f}};
$$
�������µ�̽�, $\lambda$~���� ����µ��:
$$
\varphi(p^{e-f})=p^{e-f-1}(p-1).
$$

Ի� ������� �������~$a$ �~$m$ �������ȵ� Ƶ���~$\lambda$, ���
��¾����~$a^\lambda \equiv 1 \pmod{m}$, ���ǽ� ���˲��� \dfn{���ϴ��� ��
���û�~$m$}. ҵ��Ǹ��~$a$, ��¾��� ���²���²õ� \emph{��������̽�}
�������˹ ���ϴ�� �� ���û�~$m$, ���˲����� \dfn{�����������˼ ͻ����¾�}
�� ���û�~$m$\note{2}%
{ݵ ����õ� ��°�� �����������˹ ͻ����� � �����������˼ ������.
 ߵ���������˵ ����� ��ɵ�²��� �� ��� ����~$m$.---{\sl ����. ���.\/}
}.

ޱ����Ǹ� ǵ���~$\lambda(m)$ ���ϴ�� �������������� ͻ����°, �.~�.\
��������̽� �������˹ ���ϴ�� �� ���û�~$m$. ����˴�ɸ� ����ǰ���
�����˲���, �¾~$\lambda(p^e)$ ���� ����µ��~$p^{e-1}(p-1)$;
�� ���°��ϵ� ��ô� (��.~���� ÿ�.~11--16) ������¸
¾ǽ˵ ���ǵ���~$\lambda(m)$ � ������ɸ� ���ǰ��:
$$
\eqalignrem{
& \lambda(2)=1, \quad \lambda(4)=2, \quad \lambda(2^e)=2^{e-2}, & ���� $e\ge3$,\cr
& \lambda(p^e)=p^{e-1}(p-1), & ���� $p>2$, \cr
& \lambda(p_1^{e_1}\ldots p_t^{e_t})=\���(\lambda(p_1^{e_1},\ldots, \lambda(p_t^{e_t}))).\cr
}
\eqno(9)
$$

ݰȸ ����ǰ��� ����� �ü�������� � ������ɵ� µ�����:

\proclaim ⵾����~B. (�. ڰ������)
[R. D. Carmichael, {\sl Bull.\ Amer.\ Math.\ Soc.,\/} {\bf 16} (1910), 232--238].
ܰ������̽� �������˹ ���~$c=0$ ������ �����~$\lambda(m)$,
���~$\lambda(m)$ �������ϵ��� ��������ϼ�~(9). ⰺ�� ������ ������õ���, ����
\medskip
\item{i)}~$X_0$ �~$m$---������� �����˵ Ǹ���;
\item{ii)}~$a$---�����������˹ ͻ����� �� ���û�~$m$. \endmark

%% 34

װ����µ, �¾ ����~$m$---����¾� Ǹ���, ����� ����Ǹ�� ����� �������~$m-1$,
�¾ ����� ���� �� ������� ����ȵ ��������̽��� ���ǵ���.

Ҿ���� µ���� �����ǰ���� � ¾�, ��� ��ž���� �����������˵ ͻ������ ��
���û�~$m$. ط ÿ�������� � ���Ƶ �������İ ��µ����

\proclaim ⵾����~C. ����~$a$ ���� �����������˹ ͻ����� �� ���û�~$p^e$
¾��� � ¾�̺� ¾���, �����
\medskip
\item{i)}~$p^e=2$, $a$---��ǵ½��; ���~$p^e=4$, $a \bmod 4=3$; ���~$p^e=8$,
 $a \bmod 8=3, 5, 7$; ���~$p=2$, $e \ge 4$, $a \bmod 8=3$ ���~$5$;
 %
\hiddenpar\noindent ���
\item{ii)}~$p$---��ǵ½��, $e=1$, $a \not\equiv 0 \pmod{p}$
�~$a^{(p-1)q} \not\equiv 1 \pmod{p}$ ��� �α��� ����¾�� ����µ��~$q$ Ǹ���~$p-1$;
 %
\hiddenpar\noindent ���
\item{iii)}~$p$---��ǵ½��, $e>1$, $a$~ô����²��ϵ�~(ii)
�~$a^{p-1} \not\equiv 1 \pmod{p^2}$\note{1}%
{߾����ü�������, �¾~$p$--- ����¾�; ���� ���û� ����� ���~$2$, $2^2$,
$p^e$, ���~$p$---��ǵ½��, �����������˵ ͻ������ �ô�� � �����������˼�
����ϼ�.---{\sl  ����. ���.\/}
}. \endmark

�������~(ii) �~(iii) �¾� µ����� ����� ����������� �� ��Ǹ���µ�̽��
��ȸ�� ��� ����ȸ� ���ǵ���~$p$, ���� ��� ��Ǹ������ �µ����� �����̷�����
��ĵ�¸��˵ ��¾��, ���ö����˵ � �.~4.6.3. ݰ�����, ���� ��� ����
����Ǹ��~$a_j$, ϲ���ɸ��� �����������˼� ͻ����°�� �� ���û�~$p_j^{e_j}$,
����� ���¸ �����²����� ���ǵ���~$a$, °���,
�¾~$a \equiv a_j \pmod{p_j^{e_j}}$, $1\le j \le t$, �������� "��°����� µ�����
�� ��°º��", ��¾��� ���ö������ �~�.4.3.2. ỵ����µ�̽�, $a$~�ô��
�����������˼ ͻ����¾� �� ���û�~$p_1^{e_1}\ldots p_t^{e_t}$. �¾ ����
��� �����̽� ��ĵ�¸��˹ ������
��Ǹ������ �����µ���, ô����²����ɸ� ������� µ�����~�,
��� �α��� ���ǵ���~$m$. ޴���� � ��ɵ� ���ǰ� ��Ǹ������ ����˲�����
������̺� �����˼�.

Ի� ������� ���ǰ�~$m=2^e$ ���~$e\ge 4$ ���������˵ ��ȵ ������� ��������
� �����²������ ����¾�� ����������,
�¾��~$a \equiv 3\hbox{ ��� } 5 \pmod{8}$.
� �¾� ���ǰ� ǵ²��°� ǰ��� ���� ��������� �����µ��� ����
��������̽˹ ������.

�¾��� �������� ��������������˹ ���ǰ�, �¾~$m=10^e$. ߾�̷���� �������~�
�~Q, ����ô�� ����Ǹ�� ����ž���˵ �
���°¾ǽ˵ ������� ���¸����� ��������̽��� ������� ��� ����¸ǽ��
��Ǹ���µ�̽�� ��ȸ��.

\proclaim ⵾����~D. ����~$m=10^e$, $e\ge 5$, $c=0$ �~$X_0$ �� ���½�~$2$
���~$5$, ������ �������� ������ͽ½�� ���������µ�̽��¸
�����~$5\times10^{e-2}$ � ¾� � ¾�̺� ¾� ���ǰ�, �����~$a \bmod 200$
��������� ����
%% 35
�� ������ɸ� $32$~���ǵ���:
$$
\eqalign{
& 3,11,13,19,21,27, 29, 37, 53,59, 61, 67, 69,77, 83,91,109,117,\cr
& 123,131,133,139,141,147,163,171,173,179,181,187,189.197.~\endmark\cr
}
\eqno(10)
$$

\excercises
\ex[10] ڰ���� ����� ������� �������� ������ͽ½��
���������µ�̽��¸ �~$X_0=5772156648$, $a=3141592621$, $c=2718281829$, $m=10000000000$?

\ex[10] Ӱ���¸�õ� �� �˿������� ������ɸ� ���� �������:
(i)~$c$~��ǵ½��, (ii)~$a\bmod 4=1$, ��������̽�� ����� �������,
�����~$m=2^e$, �.~�.\ �µ���� ������?

\ex[13] �����������, �¾~$m=10^e$, ���~$e\ge 3$, �~$c$  �� ���½� ��~$2$,
��~$5$. ߾����µ, �¾ �������� ������ͽ½�� ���������µ�̽���� �ô�� �����
��������̽� ����Ⱦ� ������ ¾��� � ¾�̺� ¾���, �����~$a\bmod 20=1$.

\ex[20] 絼� ����� ���ǵ���~$X_{2^{e-1}}$, ����~$a$ �~$c$ ô����²�����
������ϼ µ�����~A, $m=2^e$, $X_0=0$?

\rex[20] ݰ���µ ��� �����µ��~$a$, ô����²����ɸ� ������ϼ µ�����~A,
�����~$m=2^{35}+1$ (�����˵ �����µ�� Ǹ���~$m$ ����� ���¸ �� °��.~3.2.1.1-1).

\ex[20] ݰ���µ ��� �����µ��~$a$, ô����²����ɸ� ������ϼ µ�����~A,
���~$m=10^6-1$ (��.~°��.~3.2.1.1-1).

\rex[�24] ߵ���� ������ͽ½�� ���������µ�̽��¸ �� ��Ϸ�µ�̽� ��Ǹ����
�~$X_0$. ޴���� �� ������ ����� ���¸ �������~$\mu\ge0$, $\lambda>0$,
°���, �¾~$X_{n+\lambda}=X_n$ ��� �α��~$n\ge\mu$, ���ǵ�~$\mu$
�~$\lambda$---�������ȸ� ���ǵ���, �������ɸ� �¸� �����²��.
(��.~�~ÿ�.~3.1-6 �~3.2.1-1.) �����~$\mu_j$, $\lambda_j$ ���²���²���
���������µ�̽��¸~$(X_0 \bmod p_j^{e_j}, a \bmod p_j^{e_j},
c \bmod p_j^{e_j},  p_j^{e_j})$ �~$\mu$, $\lambda$
���²���²��� ���������µ�̽��¸~$(X_0, a, c, p_1^{e_1}\ldots p_t^{e_t})$;
�����~Q ��°���������, �¾ $\lambda$~���� �������ȵ� ��ɵ� ���½��
���~$\lambda_1$,~\dots, $\lambda_t$. 絼� ����� ���ǵ���~$\mu$, ����������
ǵ���~$\mu_1$,~\dots, $\mu_t$? ڰ��� ��������̽�� ���ǵ���~$\mu$ �����
����Ǹ��, �������~$X_0$, $a$ �~$c$ ���
ĸ�����������~$m=p_1^{e_1}\ldots p_t^{e_t}$?

\ex[�20] ߾����µ, �¾ ����~$a \bmod 4=3$, $e>1$,
¾~$(a^{2^{e-1}}-1)/(a-1) \equiv 0 \pmod{2^e}$. (�����̷ùµ �����~P.)

\rex[�22] (�.~⾼���.) Ի�~$c=0$ �~$m=2^e\ge 8$ µ�����~B �~C �²�������,
�¾ ����� ������� �����~$2^{e-2}$ � ¾� � ¾�̺� ¾� ���ǰ�, �����
�����µ��~$a$ ô����²��ϵ� ���½�ȵ��ϼ~$a\bmod 8=3$ ���~$a \bmod 8=5$.
߾����µ, �¾ ������ °��� ���������µ�̽���� � ��ɽ��¸ ϲ�ϵ���
�������� ������ͽ½�� ���������µ�̽����� �~$m=2^{e-2}$, ����ɵ�
\emph{����˹} ������ � ������ɵ� ������:
\medskip
\item{a)}~����~$X_{n+1}=(4c+1) X_n \bmod 2^e$ �~$X_n=4Y_n+1$, ¾
$$
Y_{n+1}=((4c+1) Y_n+c) \bmod 2^{e-2};
$$
\item{b)}~����~$X_{n+1}=(4c-1)X_n \bmod 2^e$ �~$X_n=((-1)^n (4Y_n+1))
\bmod 2^e$,  ¾
$$
Y_{n+1}=((1-4c)Y_n-c)\bmod 2^{e-2}.
$$
[\emph{װ��ǰ���.} � �¸� ľ��û��~$c$---��ǵ½�� Ƶ���. � ��µ������ �����
�����¸�� �²�������� � ¾�, �¾ ���������µ�̽��¸ �~$c=0$, ô����²����ɸ�
%%  36
������ϼ µ�����~B, ������̺� ����� ���ǰ���, ǵ� µ, ��¾�˵
ô����²����� ������ϼ µ����� �, �������� �� ¾, �¾ � ���ǰ� µ�����~B
������ � ǵ���� ���� ����ȵ. �¾ ÿ�������� ����������� ������˵ �²��������.]

\ex[�21] Ի� ����� ���ǵ���~$m$ ����������� ������²�~$\lambda(m)=\varphi(m)$?

\ex[�28] �����~$x$---��ǵ½�� Ƶ��� Ǹ���, ����ȵ�~$1$.
  %
\hiddenpar
(a)~߾����µ, �¾ ��ɵ�²õ� �����²����� Ƶ���~$f>1$, °���, �¾
$x\equiv 2^f \pm 1 \pmod{2^{f+1}}$.
  %
\hiddenpar
(b)~��� �������, �¾~$1<x<2^e-1$, �~$f$---���²���²��ɵ� Ƶ��� Ǹ���
��~�.(a), ������µ, �¾ ���ϴ��~$x \pmod{2^e}$ �����~$2^{e-f}$.
  %
\hiddenpar
(c)~� ǰ�½��¸, �¾ �����˲��� µ�����~C(i).

\ex[�26] �����~$p$---��ǵ½�� ����¾� Ǹ��� Ծ����µ �¾ ����~$e>1$,
¾~$a$---�����������˹ ͻ����� �� ���û�~$p^e$ � ¾� � ¾�̺� ¾� ���ǰ�,
�����~$a$---�����������˹  ͻ����� �� ���û�~$p$ �~$a^{p-1}\equiv 1 \pmod{p^2}$.
(����������µ, �¾~$\lambda(p^e)=p^{e-1}(p-1)$. �¾ �����˲����� ���� �
ÿ�.~14 �~16.

\ex[�22] �����~$p$---����¾� Ǹ��� �~$a$ �� ϲ�ϵ��� �����������˼
ͻ����¾� �� ���û�~$p$. ߾����µ, �¾ ����~$a$ ���½�~$p$
����~$a^{(p-1)/q}\equiv 1 \pmod{p}$ ��� ����¾���� ����¾�� Ǹ���~$q$,
����ɵ��~$p-1$.

\ex[�18] �����~$e>1$, $p$---��ǵ½�� ����¾� �~$a$---�����������˹ ͻ����� ��
���û�~$p$, ������µ, �¾ ¾��� ����~$a$, ����~$a+p$---�����������˹
ͻ����� �� ���û�~$p^e$. [\emph{㺰�����:} ��.~ÿ�.~12.]

\ex[�29] (a)~�����~$a_1$, $a_2$ ������� �����˵ �~$m$. ����� ��� �¸�
Ǹ���  ���ϴ�� �� ���û�~$m$ �����~$\lambda_1$, $\lambda_2$ ���²���²����.
Ծ����µ �¾ ����~$\lambda$---�������ȵ� ��ɵ� ���½��~$\lambda_1$
�~$\lambda_2$, ¾~$a_1^{\kappa_1}a_2^{\kappa_2}$ ����� ���ϴ��~$\lambda$
�� ���û�~$m$ ��� �˱������ �������ɸ� �������~$\kappa_1$, $\kappa_2$.
[\emph{㺰�����}. ��������µ ���ǰ�� ���ǰ�, �����~$\lambda_1$
�~$\lambda_2$---������� �����˵ Ǹ���.]
(b)~�����~$\lambda(m)$---��������̽˹ �� ���� ͻ����°� ���ϴ�� ��
���û�~$m$. Ծ����µ, �¾~$\lambda(m)$ ���½� ���ϴ�� �� ���û�~$m$ ���
�α��� ͻ����°. ��ó��� �������, ������µ,
�¾~$a^{\lambda(m)} \equiv 1 \pmod{m}$ ��� �α���~$a$, ������� ����¾�� �~$m$.

\rex[�24] �����~$p$---����¾� Ǹ���.
(a)~�����~$f(x)=x^n+c_1 x^{n-1}+\cdots+c_n$, ��� ���~$c$---Ƶ�˵ Ǹ���,
� ������ °��� Ƶ���~$a$, �¾~$f(a) \equiv 0 \pmod{p}$.
߾����µ, �¾ ��ɵ�²õ� �������~$q(x)=x^n+q_1x^{n-2}+\cdots+q_{n-1}$ � Ƶ�˼�
����ĸƸ��°��, °���, �¾~$f(x)\equiv (x-a)q(x) \pmod{p}$ ��� ���� Ƶ���~$x$.
(b)~�����~$f(x)$---�������, �a��� �e, �a� � �~(a). �o����µ, �¾~$f(x)$
�����  ����� ����ȵ� $n$~�����ǽ�� "������" �� ���û�~$p$, �.�.\
��ɵ�²õ� ����� ����ȵ� $n$~Ƶ��� Ǹ���~$a$, °���,
�¾~$f(a)\equiv 0 \pmod{p}$, $0\le a < p$.
(c)~� ÿ�.~15(b) �²���������, �¾ �������~$f(x)=x^{\lambda(p)}-1$ �����
$p-1$~�����ǽ�� ������; �������µ�̽�, ��ɵ�²õ� Ƶ���~$a$ � ���ϴ���~$p-1$.

\ex[�26] ݵ ��� ���ǵ���, ����Ǹ�����˵ � µ�����~D ����� ����Ǹ��
��¾���, ��������˼ � µ��µ. ݰ������, Ǹ���~$11$ �� ϲ�ϵ���
�����������˼ ͻ����¾� �� ���û�~$5^e$. ڰ� �¾ ����� ���� ����~$11$ (�
���²���²��  � µ������~D)---�����������˹ ͻ����� �� ���û�~$10^e$?
ڰ��� �� Ǹ���, ����Ǹ������� � µ�����~D,---�����������˵ ͻ������ ��� ��
���û�~$2^e$, °� �~$5^e$?

\ex[�25] Ծ����µ µ�����~D. (��.\ � ����˴�ɸ� ÿ���������.)

\ex[40] ��°��µ °����� ����¾��� ž��ȸ� �����µ���~$a$ ��� ������� ��
���ǵ���~$m$, ����Ǹ������� � °��.~3.2.1.1-1, � �������������~$c=0$.

\ex[�24] ڰ���� ����� ������� �������� ������ͽ½�� ���������µ�̽��¸,
��� ��¾��� (i)~$X_0=0$; (ii)~$a$---�����������˹ ͻ����� ��
���û�~$p_j^{e_j}$, $1\le i \le t$; ��� ���� �µ����� ������� Ǹ��� �
����������~$m=p_1^{e_1}\ldots p_t^{e_t}$ �� �����˵ �����µ��; (iii)~$c$
�~$m$ ������� ������?

\subsubsubchap{ܾɽ����\note{1}%
{� ��������� "potency",--- {\sl ����. �����.\/}}}%3.2.1.3
 � ����˴�ɵ� ������� �� ��������, �¾ ��������̽˹ ������ ����� ����Ǹ��
���~$b=a-1$, ���½��
%% 37
���� �����˼ ����µ�ϼ Ǹ���~$m$ ($b$ °��� ������ ���� ���½�~$4$, ����
$m$~������� ��~$4$). ����~$z$---���������, ��¾��� �����̷õ��� � ��ȸ��
(°�, $z=2$---��� ����ǽ�� ��ȸ�� �~$z=10$---��� ����¸ǽ��), �~$m$---������
�����~$z^e$ ��ȸ��, ¾ �����µ��
$$
a=z^k+1, \rem{$2\le k < e$,}
\eqno(1)
$$
ô����²��ϵ� �¸� ������ϼ. ط µ�����~3.2.1.2.A °��� ����õ�, �¾
����� �������~$c=1$. ൺ�����½�� ���½�ȵ��� µ���� ����� ���
$$
X_{n+1}=((z^k+1)X_n+1) \bmod z^e.
\eqno(2)
$$

��� ��Ǹ������� ����� �������� ü�������; ���°¾ǽ� ����¾�� �������� � ������.

ݰ������, �����������, �¾~$a=B^2+1$, ���~$B$---������ ���° \MIX. Ҽ��¾
������, ����������� �~�.3.2.1.1, ����� �������� °��� ���������:
$$
\vcenter{
\mixcode
LDA  & X
SLA  & 2
ADD  & X
INCA & 1
\endmixcode
}
\eqno(3)
$$
����� �� �˿������� ü���Ȱ���� �~$16u$ ��~$7u$.

Ҳ��� ���������� �����µ�� ����~(1) ȸ���� ���ö������ � ��µ������ �
��������������� ������� ��¾����. ޴���� ���¸ ��¸��½�� �������ǽ˵
ͺ���������� �����˲���, �¾ \emph{����õ� �������� �����µ���, ����ɸ�
°��� ����¾� ���, ���~(1)}. ���Ǹ� ����� ������̺�. ������ ����� �����
�ǵ° �� ü���Ȱ���� �� ����� ���� �����, ��� �¾ �����ž��� �
�������~(3). ���� �������� � ��������� �������~|JMP|, |STJ|, |STA|, |JNOV|,
������µ�̽˵ ������� �ǵ° �ô�� �����~$22u$ ��� �û�¸�����¸�����
��¾�� �~$13u$ ��� ��¾��, �����̷��ɵ�� �������� � �����. ����� �¾��,
����ž���� �ǵ��� ����� ������ �������� ���������, �����̷��ɵ� ���ǰ��˵
Ǹ���. ��°� ͺ������ ��ȸ����� ������� � ���Ƶ�°� ���¸ ���¾���. � ��
������ ����������� ��ȸ��� ü������� �˿���ϵ��� \emph{�������,} ǵ� �����
� ��������!

᰼˹ ������ ���ü���, �������²��ɸ� �����̷������ �����µ��
����~$z^k+1$, �����ǰ���� � ¾�, �¾ �� �������� � �����°¾ǽ�
���ǰ��˼ Ǹ����. ޴�� �� ���Ǹ� �¾�� ��Ϸ��� � ���Ƶ�Ƹ�� "��ɽ��¸",
��¾��� �� ���ǰ� ���ô��.

\dfn{ܾɽ����} �������� ������ͽ½�� ���������µ�̽��¸ � ��������̽˼
�������� �������ϵ��� ��� �������ȵ� Ƶ��� Ǹ���~$s$, °���, �¾
$$
b^s \equiv 0 \pmod{m}.
\eqno(4)
$$
%% 38
(ⰺ�� Ƶ���~$s$ ������ ��ɵ�²õ�, ���� �����µ�� ô����²��ϵ� ������ϼ
µ�����~3.2.1.2A, � ǰ�½��¸, ���� $b$~���½� �α��� ����¾�� ����µ��~$m$.)

�� ����� ������������� ���ǰ������ ���������µ�̽��¸, ��������~$X_0=0$,
°� ��� �û� ��Ϸ�µ�̽� �����ǰ���� �� ����϶���� �� �������. � °���
���ǰ� �����~$X_n=((a^n-1)c/b)\bmod m$ �, ��������~$a^n-1=(b+1)^n-1$ ��
ľ��û� ������, ��ž���
$$
X_n=c\left(n+\perm{n}{2}b+\cdots+\perm{n}{s}b^{s-1}\right) \bmod m.
\eqno(5)
$$
��� ǻ��� �~$b^s$, $b^{s+1}$ � �.~�.\ ����� ����¸��, °� ��� ��� ���½�~$m$.

��ž�� �� ���������~(5), ���������� ����¾�˵ ǰ�½˵ ���ǰ�. ����~$a=1$,
��ɽ���� �����~$1$ �, ��� �� ö� ������,
$X_n \equiv cn \pmod{m}$, °� �¾ ���������µ�̽���� ϲ�� �� ���ǰ����.
���� ��ɽ���� �����~$2$, �����~$X_n \equiv cn+cb\perm{n}{2}$, �
����� ���������µ�̽���� ���̷� �Ǹ°�� ���ǰ����. Ե��²�µ�̽�,
$$
X_{n+1}-X_n \equiv c+cbn,
$$
°� �¾ �������� ����� ��������� ���ǰ��˼� Ǹ����� ���������� �ǵ��
����¾� ������������ ��~$n$. ����
$$
d=cb \bmod m,
$$
¾Ǻ�~$(X_n, X_{n+1}, X_{n+2})$ ������ ����� �� ����� �� ǵ�����
�������µ� � ���ż����� ���������²�:
$$
\eqalign{
x-2y+z &= d+m,\cr
x-2y+z &= d,\cr
x-2y+z &= d-m,\cr
x-2y+z &=d-2m.\cr
}
$$

���� ��ɽ���� �����~$3$, ���������µ�̽���� �˳�ϴ�� ������̺� �����
���ǰ����. ݾ~$X_n$, $X_{n+1}$, �~$X_{n+2}$ ��� �ɵ ��Ϸ��� ���̽��
������������. ష���¸~$X_{n+1}-X_n$ �������� ���������µ�̽���� �
��ɽ�����~$2$, � µ��� �����˲���, �¾ ���������µ�̽��¸ � ��ɽ�����~$3$
��� �ɵ �����°¾ǽ� ž��ȸ. ι�ɰ����, �¾ ��������˵ ���û�°�� �����
���� ����ǵ�� ��� ���ǵ��� ��ɽ��¸, �������~$4$ � ��ȵ, �� �¾
������������ ������� ��¾����. Ҹ����, ��� ���°¾ǽ� ���ǰ���� ���ǵ���
����õ��� ��ɽ����, ������ �� ����ȵ� ����~$5$.

�����������, ��������, �¾~$m=2$ �~$a=2^k+1$. ⾳��~$b=2^k$, °� �¾
���~$k \ge 18$ ���ǵ���~$b^2=2^{2k}$ ���½�~$m$: ��ɽ����
�����~$2$. ����~$k=17$, $16$,~\dots, $12$, ��ɽ���� �����~$3$, �
���~$k=11$, $10$, $9$ ���¸������ ���ǵ���~$4$. ߾�¾�� � ¾Ǻ�
������ ��ɽ��¸ �����²���� ��������� °��� �����µ��, ��� ��¾���~$k\le 8$.
%% 39
�¾ ���Ǹ�, �¾~$a\le 257$, � �� ò���� �����, �¾
\emph{������ȸ�} �����µ��� °��� ����õ� ��������. �°�, ���
�����µ�� ����~$2^k+1$ ���~$m=2^{35}$ ����˲����� ����������˼�.

��� ����ȸ� �������� ����� �����µ�� ����~$2^k+1$ ������� �����. �˻
����°� � ������ � ��µ������ ���Ǹ� �~$m=2^{47}$, $a=2^9+1$ � ��ɽ�����,
������~$6$ ({\sl CACM,\/} {\bf 4} (1961), 350--352).
ݵ������ �� �¾, ���� ���� �ǵ�� ��¾����˼ � �����µ�ϼ� ¸��~(1), ��¾��
�¾ ���¸ ��� �����½˵ ��������˵ ���Ǹ�� �˻� ������ °���� ¸��. �
����²�µ�̽��¸ ���� ���������˹ ������ �� ô����²��ϵ� �°¸�¸ǵ����
µ�°� �.3.3.4.

���~$m$, ������~$w\pm1$, ���~$w$---������ �����, $m$, ����ɵ ������, ��
����������� �� ������������ ������� �µ����� ������� Ǹ���, °� �¾
����Ȱ� ��ɽ���� ���������� (��.\ ������~6). ߾�¾�� � �¾� ���ǰ�
\emph{��} �¾�� ���̷������� ��¾��� ��������̽��� �������, � ����õ�
��������� ��¾� Ǹ�¾�� ü������� �~$c=0$.

��� �ɵ ��°���� ����� ������� � �˱��� �����µ��. Ҿ��ɵ ������, �� ž¸�
��������� ��ɽ���� �������, �����µ�� ���°¾ǽ� ����ȸ� �, ����� ¾��,
�������� ���Ⱥ�� ����¾�� �� ���� ������ Ƹ�� � �����µ��. �����������,
�¾~$m=2^{35}$, � �����Ƹ� ü������� �����ϵ��� ��� ü���ȵ���
����ǵ�²� "�����ǽ��" ��¾� � �����µ��. ܾ��� �������������
(ͺ��������°�̽�) °��� �����µ��, ���~$2^{23}+2^{14}+2^2+1$.
绵�~$2^{23}$ ������ �����µ�� �����̽� ����ȸ�. 绵�~$2^2$ ������Ǹ����
������� ��ɽ����. մ���ư ����ž���� ��� ����ǵ��� ��������̽��� �������,
� $2^{14}$~������ϵ���, �¾�� �����µ�� �� �������� ���Ⱥ�� �����˼ ���
������º� ���°¾ǽ� ���ǰ���� ���������µ�̽��¸ (��.~ÿ�.~8). 绵�,
������˹~$2^{34}$, �˻ �� ����� �� �¾�� ž���, ���~$2^{23}$, °� ��� �
������������~$2^{34}X_n$ �����̷õ��� ¾�̺� ���˹ ����ȸ� ��� Ǹ���~$X_n$
(��¾�˹ �� ���Ⱥ�� ���ǰ��). ���� �������� ü������� �� ϲ�ϵ���
����¸���ɵ�, ����� "���ǰ��˹" �����µ�� (��������, $a=3141592621$),
�����½�, �������� ���Ǹµ�̽� ����� ô����²���µ�̽˼.

� ����²�µ�̽��¸ ���Ƶ�Ƹ� ��ɽ��¸ ���� ¾�̺� ���� �� ���µ���� �˱���
�����µ��; � ���� ����� �������� ������ ��ó��. ݸ��, � �.3.3.4,
���ö������ "��������̽˹ µ��" ��� �����µ��� �������� ������ͽ½��
���������µ�̽��µ�. �¾---����˹ ���µ���, ����ǰ�ɸ�, ��� ǰ�½˵ ���ǰ�,
��ɽ���� � ����Ǹ�� �����µ��. � �.3.3.4 ��, ��������, ò����,
�¾ �˱��~$2^{23}+2^{13}+2^2+1$ ������� �ö�, ǵ�~$2^{23}+2^{14}+2^2+1$.
�α�� �����µ��, ��¾�˹ �ô�� ȸ���� �����̷�������, ����õ� ���������
��������̽˼ µ�¾�.

\excercises
\ex[M10] ߾����µ, �¾ ���������� �� ¾��, ����� �������� ������ ���°~$B$
��ȸ�� \MIX, ���������~(3) ��ö�� ���Ǹ��� ���ǰ���� Ǹ��� �
��������̽˼ ��������.

%% 40
\ex[10] ڰ���� ��ɽ���� ���Ǹ��, �������������� \MIX-����������~(3)?

\ex[11] ڰ���� ��ɽ���� �������� ������ͽ½�� ���������µ�̽��¸
���~$m=2^{35}$, $a=3141592621$? 絼� ����� ��ɽ����, ����
�����µ��~$a=2^{23}+2^{13}+2^2+1$?

\ex[20] ߾����µ, �¾, ����~$m=2^e\ge 8$, ��������̽�� ��ɽ����
���¸������ ���~$a \bmod 8 = 5$.

\ex[M20] ԰��, �¾~$m=p_1^{e_1}\ldots p_t^{e_t}$
�~$a=1+kp_1^{f_1}\ldots p_t^{f_t}$, ���~$a$ ô����²��ϵ� ������ϼ
µ�����~3.2.1.2A, �~$k$ �~$m$ ������� ������. ߾����µ, �¾ ��ɽ����
�����~$\max(\ceil{e_1/f_1},~\ldots, \ceil{e_t/f_t})$.

\rex[20] ڰ��� �� ���ǵ���~$m=w\pm1$ � °��.~3.2.1.1-1 ����� ����
��ɽ����, ������ �� ����ȵ� ����~$4$? (�����̷ùµ ���û�°� ÿ�.~5.)

\ex[�20] ���� Ǹ���~$a$ ô����²��ϵ� ������ϼ µ�����~3.2.1.2A,
��� ������� ����¾ �~$m$; �������µ�̽�, ��ɵ�²õ� Ǹ���~$a'$, °���,
�¾~$aa'\equiv 1 \pmod{m}$. ߾����µ, �¾~$a'$ ����� ����¾ �������� �
�������~$b$.

\rex[�26] ԰�Ǹ� ���ǰ���� Ǹ��� �~$X_{n+1}=(2^{17}+3)X_n \bmod 2^{35}$
�~$X_0=1$ ��������� ������ɵ�� µ���. �����~$Y_n=\floor{10X_n/2^{35}}$,
¾���~$Y_n$ ������ ���� ���ǰ���� Ƹ���� �����~$6$ �~$9$, �
������~$(Y_{3n}, Y_{3n+1}, Y_{3n+2})$ ������ ��������� �α�� ��
$1000$~��������� ���ǵ��� ��~$(0, 0, 0)$ ��~$(9, 9, 9)$ � ������
�����½�����. ݾ � $30\,000$~����������� Ǹ��� ����¾�˵ ������
�����ǰ���� �ǵ�� �����, � ����¾�˵ ��ϲ�ϻ��� ������� ǰɵ ��ó��. ܾ��µ
�� �� ��������� °��� ������˹ ���û�°�?

\subsubchap{��ó�� ��¾��} %3.2.2
ھ��ǽ�, ������˵ ������ͽ½˵ ���������µ�̽��¸---�� �����²���˹ ��
������������ ��� ��Ǹ���µ�̽�� ��ȸ� ��¾ǽ���� ���ǰ���� Ǹ���. � �¾�
�ý�µ �� �������� ����� ��ó�� �������� ������ ��¾���. ݵ��¾�˵ �� ���
���°¾ǽ� ����� ¾��� ��� ��ó�� �����°����� ��µ��� ���� ���¾�̺�,
������̺� ����˲����� ������ �� °���� ž��ȸ��, ��� ������� �� ����˹ ����ϴ.

޴�� �� ��ɵ�������� ����ö�����, � ��¾�˼� ���ž����� �°���������,
����� ���� ���� � ����ǵ��� ���ǰ���� Ǹ��� �����ǰ���� � ¾�, �¾
���°¾ǽ� ����� ž��ȸ� ���Ǹ� � ������ ��� ��������, �¾�� ������°��
"�ɵ ����� ���ǰ����" ���������µ�̽����. Ծ���̽� ǰ�¾ �¾ �������.
ݰ������, �� ����� �¾ �� ľ��û�
$$
X_{n+1}=(aX_n+c) \bmod m
\eqno(1)
$$
����� ����Ǹ�� �����̽� ž��ȸ� ���ǰ��˵ Ǹ��� ݵ �ô�� �� ���������µ�̽����
$$
X_{n+1}=((aX_n) \bmod (m+1)+c) \bmod m
\eqno(2)
$$
�ɵ ����� ���ǰ����? �²�� °���, �¾ ����� ���������µ�̽���� � ����ȵ�
�����½����� \emph{�����} ���ǰ���. װ��¸�, �¾ Ƶ���½�� µ���� ��� ���
��ȸ���, � � ������²�� �����-���� µ���� � ���������
���������µ�̽��¸~(2) �� �������� � �������
���Ǹ���. ¸��~$X_{n+1}=f(X_n)$ �� ���ǰ��� �˱������ �ý�Ƹ��~$f$.
Ҽ��µ � µ� ÿ�.~3.1-11--3.1-15 �����˲���, �¾ �¸ ���������µ�̽��¸
%% 41
����� ���� ������ �� °� ž��Ⱦ, ��� ���� �� �ý�Ƹ�~(1) �˻� ǵº�
����������.

��������� ��ó�� ���ž�, ��°��� ������������ "����� ���ǰ��˵" Ǹ���.
۸����˹ ������ͽ½˹ ��¾� ����� ����ɸ��, ������¸� ���, ������, �
������¸ǽ˹ ������ͽ½˹ ��¾�:
$$
X_{n+1}=(dX_n^2+aX_n+c) \bmod m.
\eqno(3)
$$

� ÿ�.~8 ����ɰ���� µ�����~3.2.1.2A � Ƶ��� ����Ǹ�� ����ž���˵ �
���°¾ǽ˵ ������� ���~$a$, $c$ �~$d$, °���, �¾�� ���������µ�̽����,
������������ ���½�ȵ����~(3), ����� �� ��������̽˹ ������~$m$.
޳����ǵ��� ����˲����� �� ����� ���º���, ǵ� � �������� ��¾��.

Ի� ���ǰ�, ����� $m$~�����°��ϵ��� �µ����� ������, ��µ����˹
������¸ǽ˹ ��¾� ��������� �.~ھ���. �����
$$
X_0 \bmod 4 =2, \quad
X_{n+1}=X_n(X_n+1) \bmod 2^e, \rem{$n\ge 0$.}
\eqno(4)
$$
��� ���������µ�̽���� ����� ��Ǹ����� ���¸ � ¾� �� ��ĵ�¸�������,
��� �~(1), �� �������� � ������������. ޽� ����� ��µ������ ��Ϸ� �
�������ǰ�̽˼ ��¾��� �������� ������° ľ� ݵ�����. Ҿ�̼��~$Y_n$,
������~$2^eX_n$, °� �¾~$Y_n$---Ǹ���, �����°������� � ������� ¾ǽ�����
��µ� ������˲���� ������ $e$~�û�� ����ǽ��� �����°������~$X_n$.
⾳��~$Y_{n+1}$ ���¾�� � ¾ǽ��¸ �� $2e$~������� Ƹ��
Ǹ���~$Y_n^2+2^eY_n$! ⰺ�� �������, ��¾� ھ��� ���¸ ����¸ǵ� ��¾��
�������� ������° � ������� ¾ǽ�����, � ¾� �����Ƶ�, �¾ �� �����¸�õ�
����Ⱦ� ������. ܾ��� ������¸ � ���̽��ȸ� ������µ���²� ���ǰ����¸
����ǰ���� ���������µ�̽��¸ (��. ÿ�. 3.3.4-25).

��ó�� ����ɵ��� ���½�ȵ���~(1) °��� �����̽� �ǵ�����. ݰ������, ��
����� �� ����°���� ò���Ǹ�� ������ ���������µ�̽��¸. ߵ���� ��������
������ͽ½�� ���������µ�̽��¸ ������ǰ��� �����. ޱ�ǽ�, ����
$m$~������������ � ������� ��ȸ����� �����, �� ����� ���� � ���������
���ϴ��~$10^9$ � ����ȵ, °� �¾ � ¸��ǽ�� ����ǰ� �����̷õ��� ¾�̺�
�ǵ�� ����� ǰ��� ���������µ�̽��¸. � ��ó�� �¾����, ����Ǹ��
������� ���ϵ� �� �µ���� ���ǰ����¸, ��¾��� ���¸������ �
���������µ�̽��¸ (��.\ ����ǰ���, ���������˵ �����
���½�ȵ���~3.3.4-13). ߾�¾�� ���ǽ� �� ��������� ����ǰ�� ����Ⱦ� ������,
��� ǵ�� � ��ɵ�²õ� �ϴ ��¾���. � ����� �� ��� ��������
�����������~$X_{n+1}$ ��~$X_n$ �~$X_{n-1}$ ����¾ ����¾� ���������¸
¾�̺� ��~$X_n$. ⾳�� ����� ������� ����� ò���Ǹ�� ��~$m^2$, °�
��� ���������µ�̽���� ��ǽ�� ���¾������ �� ����ȵ, ǵ� �ô�� �˿������
������²�~$(X_{n+\lambda}, X_{n+\lambda+1})=(X_n, X_{n+1})$.

����µ�ȸ� ���ǰ� ���������¸~$X_{n+1}$ �� ����� ǵ� ������ �� ����˴�ɸ�
���ǵ��� ������õ��� � ���������µ�̽��¸ 丱����Ǹ
$$
X_{n+1}=(X_n+X_{n-1}) \bmod m.
\eqno (5)
$$
%% 42
�¾� ���Ǹ� �������������� � ��ǰ�� ��¸������� �����. ޽ ���� ���ǽ�
����� �������, �������, ǵ�~$m$. ޴���� µ��� � ��������������� ��������,
�¾ Ǹ���, ����ǰ��˵ �� ���½�ȵ��� 丱����Ǹ~(5), ϲ������
\emph{�����°¾ǽ�} ���ǰ��˼�. ߾�¾�� � ���¾�ɵ� ����� ľ��û�~(5)
��µ����� �����˼ ������� ��� ��������˹ "���ž� ������".

ܾ��� °��� ����������� ���Ǹ�� ����
$$
X_{n+1}=(X_n+X_{n-k}) \bmod m,
\eqno(6)
$$
���~$k$---���°¾ǽ� ����Ⱦ� Ǹ���, ����������˵ ������, Ἰ¾� � ڻ����
(Green, Smith, Klem, {\sl JACM,\/} {\bf 6} (1959), 527--537).
��� ���²���²��ɵ� �˱���~$X_0$, $X_1$,~\dots, $X_k$ �° ľ��û�
���ɰ�� �°�� ��¾ǽ���� ž��ȸ� ���ǰ���� Ǹ���. ݰ ����˹
����ϴ ���½�ȵ���~(6) �˳�ϴ�� �� ���Ⱥ�� ô���˼ ��� �����̷������ �
��ȸ��, µ� �� ����� ��ɵ�²õ� �ǵ�� ��ĵ�¸���� ���Ƶ���� ��� �� �������Ƹ�.

\alg A.(д��¸��˹ ���Ǹ� Ǹ���.) ὰǰ�� � �ǵ���~$Z$, $Y[0]$, $Y[1]$,~\dots,
$Y[k]$ ��������� ���²���²���� ���ǵ���~$X_k$, $X_k$, $X_{k-1}$,~\dots,
$X_0$, � $j$~����������� ����˼~$k$. ߾�������µ�̽�� �����̷������
������¼� �������� � ����ǵ��� ���������µ�̽��¸~$X_{k+1}$, $X_{k+2}$,
$\ldots\,$.
\st[$j<0$?] ����~$j<0$, ��°������~$j\asg k$.

\st[���������,     ��������.]    ��°������~$Z\asg Y[j] \asg (Z+Y[j]) \bmod m$.

\st[㼵��ȸ��~$j$.] 㼵��ȸ��~$j$ ��~$1$, �˴���~$Z$.
\algend

�¾� ������¼ �� Ϸ˺�~\MIX{} �˳�ϴ�� °� (��� �������, �¾ �������˹
�������~6 �� �����̷õ��� � �������� ���������):
$$
\vcenter{
\mixcode
J6NN & *+2  & A1. $j<0$?
ENT6 & K    & ��°������~$j\asg k$.
LDA  & Z    & A2. ���������, ��������.
ADD  & Y, 6 & $Z+Y[j]$ (�������� ������������)
STA  & Y, 6 & $\rasg Y[j]$.
STA  & Z    & $\rasg Z$.
DEC6 & 1    & A3. 㼵��ȸ��~$j$.
\endmixcode
}
\eqno(7)
$$
�¾� ���Ǹ� ����°�� ���ǽ� �������, ǵ� ���Ǹ��, ��������ɸ� ����˴�ɸ�
��¾��, °� ��� ����� �� ����õ��� �������� ü�������.

ᵹǰ� � °��� ����¸���� ���Ǹ�� �����½� �������. ������ ǵ� ��� �����
�ô�� �������������, ����õ� ������� µ����, ����������� ��°������
����ž���˵ ������µ�� ���ǰ����¸ �������˲����� Ǹ���, � ������¸
ȸ����� ����°��� ��� �´��̽�� ���ǵ���~$k$ �~$X_0$, $X_1$,~\dots,
$X_k$. Ի��� ������� ���ö������ � ÿ�.~11; ����ɵ ������, ��� �� �������
����ȵ~$m$. � �°�̵
%% 43
�����, Ἰ° � ڻ��� ���������, �¾ ���~$k\le 15$ ���������µ�̽���� ��
ô����²��ϵ� µ��� "�������� ��µ������", ���������� � �.~3.3.2, ž��
���~$k=16$ µ�� ���ž��� ������̽�.

��ɵ�²õ� ��ž���, �� ������� ����� ��ĵ�¸��˹ ������ û��ȵ���
���ǰ����¸ �������� ������ͽ½�� ���������µ�̽��µ�,
����~\emph{$m$---����¾� Ǹ���.} ݰ������, $m$~����� �˱���� ��� �����
����Ⱦ� ����¾� Ǹ���, ��¾��� ����� �������� � ��ȸ���� �����. ⰺ��
Ǹ��� ����� ��Ǹ����� �� ���������� �����, �������� µŽ��� �.~4.5.4.
ھ���~$m=p$---����¾� Ǹ���, �� µ���� ����ǽ�� ����� ����õ�, �¾
��ɵ�²��� °��� �����µ��~$a_1$,~\dots, $a_k$, �¾ ���������µ�̽����,
������������ ľ��û��
$$
X_n=(a_1X_{n-1}+\cdots+a_kX_{n-k}) \bmod p,
\eqno(8)
$$
����� ������ �����~$p^k-1$. ״���~$X_0$,~\dots, $X_{k-1}$ ����� ����
�˱���� ��������̽�, �� �� ������ ���� ��� ����� �û�.
(��½˹ ���ǰ�~$k=1$ ���²���²õ� �û�¸�����¸���� ������ͽ½��
���������µ�̽��¸ �� ����¾�� ���û�, � ��¾��� �� ö� �������.) �˱��
���¾Ͻ���~$a_1$,~\dots, $a_k$ �~(8) ¾��� � ¾�̺� ¾��� ���� ������˹
���û�°�, ����� �������
$$
f(x)=x^k-a_1x^{k-1}-\cdots-a_k
\eqno(9)
$$
ϲ�ϵ��� \dfn{"�����¸��˼ �����ǻ���� �� ���û�~$p$",} �.~�.\
����� ������, ϲ���ɸ��� \emph{�����������˼ ͻ����¾� ���� ��~$p^k$} ͻ����¾�\note{1}%
{�¾� ͻ�����---�������ɰ� �û�¸�����¸���� ��ÿ�� ���� Ӱ�ð, ��¾���, ���
�����½�, Ƹ���ǽ�.--- {\sl ����. ���.\/}} (��. ÿ�. 4.6.2-16).

ھ��ǽ�, ����¾� İ�� \emph{��ɵ�²������} ���ž��ɸ� ����°��~$a_1$,~\dots,
$a_k$, ������Ǹ���ɸ� ����� �������~$p^k-1$, �����°¾ǵ� ���
����¸ǵ���� Ƶ���. �� ������ ü��� \emph{��ž����} ��, �� ��������� ���
$p^k$~������¾�, °� ��� $p$~����� ���ϴ�� ������� ��ȸ����� �����. �
�ǰ����, ��ɵ�²õ� � ¾ǽ��¸~$\varphi(p^k-1)/k$ ���ž��ɸ�
�������Ƹ�~$(a_1,~\ldots, a_k)$, °� �¾ ������� �����̽� ����Ⱦ� Ȱ��
�����ö��� ���� �� ��� ����� ������̺�� ���ǰ���� ����¾�. ݾ, �����
����� ���ǵ��, ��� �ö�� ü��� ������ ����������, ϲ�ϵ��� ��~(9)
�����¸��˼ �����ǻ���� �� ���û�~$p$. ᾲ��ȵ��� ��������� �������˲���
$p^k-1$~ͻ����¾� ���������µ�̽��¸ � �������� ���¾�����! ܵ¾��
�������� ¾��, ϲ�ϵ��� �� �����ǻ�� �����¸��˼ �� ���û�~$p$,
���ö������ �������� � ڽ�¾�
(Alanen, Knuth, {\sl Sankhy\=a\/}, Ser.~A, {\bf 26} (1964), 305--328).
ܾ��� �����̷����� ������ɸ� ���µ���.

�����~$r=(p^k-1)/(p-1)$.
\medskip
\item{i)}~ҵ��Ǹ��~$(-1)^{k+1}a_k$ ������ ���� �����������˼ ������ ��
���û�~$p$ (��.~�.~3.2.1.2).

\item{ii)}~߾�����~$x^r$ ������ ���� ������� �~$(-1)^{k+1}a_k$ ��
���û�~$f(x)$ �~$p$.

%% 44
\item{iii)}~�µ����~$x^{r/q} \bmod f(x)$, ��� ������ü�������
����������̽�� ���ļ�¸�� �� ���û�~$p$, ������ ���� ������µ�̽�� ���
��Ϻ��� ����¾�� ����µ��~$q$ Ǹ���~$r$.
\medskip
\noindent ��ĵ�¸��˵ ��¾�� ��Ǹ������~$x^n \bmod f(x)$, �����̷��ɸ�
����������̽�� ���ļ�¸�� �� ���û� ����¾��~$p$, ���ö������ �~�.~4.6.2.

�¾�� ������� °��� ��������, ��� �ö�� �����
İ�¾����Ƹ�~$r=(p^k-1)/(p-1)$ � ������� ������� Ǹ���. �¾
������Ǹ���� ���������¸ ��Ǹ������. װ ���������� ����� �����
İ�¾��������~$r$ ���~$k=2$, $3$ �, ����� ����, $4$, �� � ����ȸ��
���ǵ��ϼ�~$k$, ���� $p$~������, ��ô�� ����� ����. ԰�� ���~$k=2$ Ǹ���
"���Ǹ��� ���ǰ���� Ƹ��" ô��������� �� ��������� �~$k=1$. ߾�¾��
����ȸ� ���ǵ���~$k$ ����� ����ž����.

Ի� �Ƶ��� ���������µ�̽��¸ Ǹ���, ����ǰ���� � �������~(8), �����
������̷������� ������¾� ��������̽��� µ�°, �������˼ � �.~3.3.4
(��.~ÿ�.~3.3.4-26). ط ����������� � �¾� �ý�µ ����õ�, �¾
\emph{��Ƶ�����������} ������Ǹ������ �ǵ����˼� ���ǵ��ϼ�~$a_1=+1$
���~$a_1=-1$, ���� ���� �¾ ��������. ���ȵ ����� ����ȸ�, ��ɵ�²����
"���ǰ��˵" Ǹ���~$a_1$,~\dots, $a_k$, ô����²����ɸ� ������ϼ, � ��µ�
��������� �˱�� � ������� ��������̽��� µ�°. Ի� �����������~$a_1$,~\dots,
$a_k$, ����õ��� ������¸ ����� ��Ǹ������, �� ���� ���
��������� �Ǹ°��, �¾ � ���û�°µ �� ����Ǹ� ���̼� ô����²���µ�̽˹
��¾ǽ�� ���ǰ���� Ǹ���.

����˹ ��µ��� �����°��ϵ� ���ǵ���~$p=2$. ؽ���� �˲��� �ö�� ���Ǹ�,
��������ɸ� ���ǰ���� ���������µ�̽���� \emph{��¾�}---�û�� � ������
(� �»�Ǹ� �� ������, ��������ɸ� ���ǵ��� �� �û� �� �������). ��ɵ�²õ�
����¾� ������ �������˲��� �� ����ǽ�� ��ȸ�� � $k\hbox{-����ϴ�˼�}$
������� ���̼� ���ǰ���� ���������µ�̽���� ��¾�. ݰǸ���� �
��������̽��� ����ǽ��� �����~$|Y|=(Y_1 Y_2 \ldots Y_k)_2$, �»�ǽ��� ��
�û�. �¾�� ����Ǹ�� �ǵ������ ���ǰ��˹ ��� ���������µ�̽��¸, ���������
������ɸ� �����Ƹ�, ��������˵ �� Ϸ˺�~\MIX:
$$
\vcenter{
\mixcode
LDA  & Y   & (������������, �¾ ������ ������������ �˺��ǵ�.)
ADD  & Y   & ᴲ�� ����� �� ���� ����ϴ.
JNOV & *+2 & ߵ��ž�, ���� � �°�ȵ� ����ϴ� ���ǰ�� �˻ �û�.
XOR  & C   & � ���¸���� ���ǰ� ������¸�õ� Ǹ��� �����Ƹ�� "�����ǰ�ɵ� ���".
STA  & Y
\endmixcode
}
\eqno(10)
$$

�²��°� �� ���ϴ�� �����Ƹ�, "�����ǰ�ɵ� ���", ������� ���¸ �� ����
����ǽ�� ��ȸ��� (��.~ÿ�.~2.5-28). ޽� �����ϵ� ���ǵ��� ������� ����ϴ�,
���²���²��ɵ�� ¾��, ��� |C|~�������� �������, �� ����½��. �
�ǵ���~|C| ��ž����� ����ǽ��
%% 45
����°�°~$(a_1\ldots{}a_k)_2$, ���������ɰ� �����¸��˹ �����ǻ��
�� ���û�~$2$: $x^k-a_1x^{k-1}-\cdots-a_k$. ߾��� �˿�������
���������~(10) � ����ȵ� ����ϴ�~|Y| ���������� ������ɸ� ���
���������µ�̽��¸ (���� �¾ ����� ô����, �����, ��������,
�����̷����� �°�ȸ� ����ϴ~|Y|). ��������� � ��ǵ�²� ������� ���.~1,
�����������ɸ�
$$\matrix{
 1011\cr
 0101\cr
 1010\cr
 0111\cr
 1110\cr
 1111\cr
 1101\cr
 1001\cr
 0001\cr
 0010\cr
 0100\cr
 1000\cr
 0011\cr
 0110\cr
 1100\cr
 1011\cr
}
$$
%% �° �����ư � ���� ���¸���.
\picture{
  ��.~1. ߾�������µ�̽˵ ���¾Ͻ�� ��ȸ����� �����~|Y| ��� �����̷������
  ����ǽ��� ��¾�� ���~$k=4$ � $c=|CONTENTS|(|C|)= (0011)_2$.
}
����ǵ��� ���������µ�̽��¸ ���~$k=4$, $c=(0011)_2$ (�¾, ����ǽ�,
���°����½� ����� ���ǵ���~$k$). ����˹ �¾���� °����� �����°��ϵ�
���������µ�̽���� ��¾�, ��¾��� ���¾�ϵ��� � ��������~$2^k-1=15$:
$1101011110001001\ldots\,$. ߾�������µ�̽���� ���°¾ǽ� ���ǰ����,
���� �ǵ���, �¾ ��� ����ǵ�� � ������� ǵ����� ����ϴ�� ����¸. �¾��
ñ������� � �¾�, ���������� �������� ǵ²���� ��¾�, ��ϲ���ɸ��� ��
����϶���� �������, � ������: $1101$, $1010$, $0101$, $1011$, $0111$,
$1111$, $1110$, $1100$, $1000$, $0001$, $0010$, $0100$, $1001$, $0011$,
$0110$. Ҿ��ɵ ������, °� ��� ����� ������� �����~$2^k-1$, ������
��������� �������Ƹ� $k$~��¾� �����ǰ���� �� ������ ¾ǽ� ���� ���, ��
�����ǵ���� ������ �� ���� �û��. ⰺ�� �������, �������� ������ ��
$k$~��¾� ��ɵ�²���� ����������. � \S~3.5 �� ò����, �¾ ��ɵ�²õ�
�ǵ�� ��ɽ˹ ���µ��� ���ǰ����¸ ���~$k$, �������, ������, $30$ ���
����ȵ. ⵾��¸ǵ���� ���û�°��, �����������ɸ� ���ǰ������ �¾�
���������µ�̽��¸, ���������� � �°�̵ �.~������° (R.~�.~Tausworthe,
{\sl Math. Comp.,\/} {\bf 19} (1965), 201--209).

�����¸��˵ �����ǻ��� �µ����~$\le 100$ �� ���û�~$2$
�˻� ���°�û������� �.~������� (�.~J.~Watson, {\sl Math. Comp.,\/} {\bf 16}
(1962), 368--369). ���~$k=35$ ����� �������
$$
c = (00000000000000000000000000000000101)_2,
$$
%% 46
� ���~$k=30$ ����� �����
$$
c=(000000000000000000000001010011)_2.
$$
��� ��, ��� ����õ� �� ÿ�.~18 �~3.3.4-26, ��� ����������� �����¸����
�����ǻ���� �� ���û�~$2$ ���ȵ ��ž���� ��ɵ�²���� "���ǰ��˵" ����°���~$c$.

\emph{����ÿ��������:} ݵ��¾�˵ ���������� � ����Ⱥ�,
��°��� �����̷����� ��¾� ������º� ���ǰ���� ���������µ�̽��µ� ��¾�
��� ����ǵ��� ���ǰ���� ������, �������ɸ� Ƶ���
�����~$(.Y_0Y_1\ldots{}Y_{k-1})_2$,
$(.Y_kY_{k+1}\ldots{}Y_{2k-1})_2$,~$\ldots\,$. ݰ ����� ���� �¾ �����̽�
���ž� ������, ž�� �´��̽˵ ���� ������ ����� ������ ���ǰ��� (��.~ÿ�.~18)!

�� ö� ������, �¾, �����~$X_n$ �������ϵ��� ���ž��ɵ� �ý�Ƹ��
��~$X_{n-1}$,~\dots, $X_{n-k}$, ����� ���¸ °���
���������µ�̽��¸ �~$0\le X_n < m$ � ��������~$m^k-1$, ���~$m$---����¾�
Ǹ���. ݰ�����ȸ� ������, ��¾�˹ ����� ����Ǹ�� ��� \emph{��������̽��}
���������µ�̽��¸, ������������ ���½�ȵ����
$$
X_n=f(X_{n-1}, \ldots, X_{n-k}), \rem{$0\le X_n < m$,}
\eqno(11)
$$
��� ����� ������, �����~$m^k$. �.~ܰ�¸� (�.~H.~Martin
{\sl Bull. Amer. Math. Soc.,\/} {\bf 40} (1934), 859--864) ����˹ �������,
�¾ ��ɵ�²��� �ý�Ƹ�, ��������ɸ� ���¸�� �¾�� ������ü� ��� �α��~$m$
�~$k$. ճ� ��¾� ����� ����������, ��, � ���������, �� ��ô���� ���
���������������� (��.~ÿ�.~17). ط �����½�� �ý�Ƹ�~$f$, ���ɸ�
��������̽˹ ������~$m^k$, ����� ����¾� ϲ�ϵ��� ��������� � ÿ�.~21.
ι²���²��ɸ� ���������, ����ɵ ������, �� °� ��ĵ�¸��� ��� ������º�
���ǰ���� Ǹ���, ��� ��� �������Ƹ� ��ó�� ����� ��������� ��¾���. ��� ��
��� ��������� ������������������ ϲ��� ���ǰ������ ���������µ�̽��¸
(����� ���� ���� � ������� � Ƶ���).

��ó�� ����˹ ����� ��¾��� �������� � \emph{�������Ƹ�} ���Ǹ���
���ǰ���� Ǹ��� ��� ����ǵ��� "�ɵ ����� ���ǰ����" ���������µ�̽��µ�.
������ �������� ����¸��, �������ɸ�, �¾ ������˵ ������ͽ½˵ ��¾��,
����¸��˵ ��¾�� � �.~�.\ ���Ⱥ�� ������ ��� ������º� ���°¾ǽ�
���ǰ���� ���������µ�̽��µ�. � °� ��� ���������� \emph{��������,} �¾
�� ����¸Ƹ�� ���������� (ž�� �� � �����, �¾ �¾ °�), �����̽�
���������� ���������� �������� ������. ��ɵ�²��� ������
��ĵ�¸��˵ ��¾�� ��� ¾��, �¾�� ����ǰ�� �� ����
���������µ�̽��µ� ���¾�̺� ���ǰ���� ������, �¾ ¾�̺� ���˼
�®ϲ����˼ ����¸��� ��� ����� �� �����������.

�����������, �¾ �� ����� ��� ���������µ�̽��¸~$X_0$, $X_1$,~\dots,
�~$Y_0$, $Y_1$,~\dots, ���ǰ���� Ǹ���, ������������� ����� �û�� �~$m-1$,
����ǵ��˵ ��ü� ���������˼� ���������. ޴�� �� ����������� �������� �
¾��, �¾�� �����˲��� Ǹ��� ������� ��
%% 47
���û�~$m$, ����ǰ� ���������µ�̽����~$Z_n=(X_n+Y_n)\bmod m$. � �¾�
���ǰ� ����µ�̽�, �¾�� ����� ��������~$\<X_n>$ �~$\<Y_n>$ �˻� �������
�����˼� Ǹ����� (��.~ÿ�.~13).

ܵ¾�, ����������˹ ܰ�������� � ܰ����̵� ���Ǹµ�̽� ���ȵ � ô���µ�̽�
ô���� ��� ����������������.

\alg M.(ҿ���� ���ǰ���� ���������µ�̽����.) ��� �������� ��¾���
������º� ���� ���������µ�̽��µ�~$\<X_n>$ �~$\<Y_n>$ �¾� ��¾�
������ϵ� ������������ ǻ��� "���Ǹµ�̽� ����� ���ǰ����"
���������µ�̽��¸. �� �����̷õ� ��������µ�̽�� °�����~$V[0]$, $V[1]$,~\dots,
$V[k-1]$, ���~$k$---����¾��� Ǹ���, �˱������� ���ǽ� ���
ô���²� ����˼ ��������~$100$. ὰǰ�� $V\hbox{-°���ư}$ ������ϵ���
����˼� $k$~���ǵ��ϼ� $X\hbox{-���������µ�̽��¸}$.

\st[������°��~$X$, $Y$.] ��°������ �~$X$  �~$Y$ ���ǵ��� �ǵ������
ǻ���� ���������µ�̽��µ�~$\<X_n>$ �~$\<Y_n>$ ���²���²����.

\st[��Ǹ�����~$j$.] ��°������~$j\asg \floor{kY/m}$, ���~$m$---���û�,
�����̷��ɸ��� � ���������µ�̽��¸~$\<Y_n>$. ⰺ�� �������,
$j$~��������� ���ǰ���� ���ǵ���, �������ϵ��� � �������~$Y$; $0 \le j <k$.

\st[װ������.] �˴���~$V[j]$ � ��°������~$V[j]\asg X$.
\algend

�¾� ��¾� ����� �������� �������������. ޽ ������ϵ� ����ǰ��
�������½� ����ȸ� �������, ���� ������� ���������µ�̽��µ�~$\<X_n>$
�~$\<Y_n>$ ������� �����˵. � ���� ���� ����� ������� �� �ǵ�� ��ɵ�²����,
�������� ǻ��� ���������µ�̽��¸ ���¸ �� ����������� ��ó � ��ó��.
���Ǹ��� ¾��, �¾ �¾� ��¾� ������� ������ž��� ��¾� �������� ������°
��� ��¾�, ��������˹ �� ���½�ȵ���~(2), ϲ�ϵ��� ���°¾ǽ��
���ǰ������ ���������µ�̽��µ�~$X_n$ �~$Y_n$, ��¾�˵ �� �����
�����������. �°µ�� ��������õ��� ��������� ÿ�.~3, �¾�� ò�����,
��� ��¾� ����°�� � ǰ�½�� ���ǰ�.

ݰ ��ȸ��~\MIX{} ����� ����������� ������¼~M, ��������~$k$ �� �������
����ȸ� ��������̽��� ���ǵ���, �����ɰ�ɵ���� � ����� ���µ (����˼
������� ���°). 谳�~M2 �~M3 ����� ��������������� ������ɸ� �������:
$$
\vcenter{
\mixcode
LD6 & Y(l:l) & $j\asg \hbox{�°�ȸ� ���� } Y$.
LDA & V, 6   & $|rA|\asg \hbox{������ɸ� ͻ����� ����� ���������µ�̽��¸.}$
LDX & �
STX & V,6    & $V[j]\asg X$.
\endmixcode
}
\eqno(12)
$$

Ի� ������� �����������, �¾ ������¼~M ������ϵ��� � °��� ��ü
���������µ�̽���ϼ �~$k=64$:
$$
\matrix{
 X_0=5772156649, & X_{n+1}=(3141592653 X_n + 2718281829) \bmod 2^{35};\cr
 Y_0=1781072418, & Y_{n+1}=(2718281829 Y_n + 3141592653) \bmod 2^{35}.\cr
}
$$
%% 48
�� �²�������, �¾ ���������µ�̽����, ����ǵ���� � ������� ������¼�~M,
�ô�� ô����²����� İ�¸ǵ��� \emph{�α���} ���µ��� ���ǰ����¸ ���
�������õ��� ��Ǹ���µ�̽�� ��ȸ��� ���������µ�̽��µ�. Ѿ��� ¾��,
����� ������º� ���� ����ȵ ǵ� ����� �����Ȱ�� ����� ����ǵ��� �����
���������µ�̽��¸~$<X_n>$.

�.~ӵ�Ű��� ������� [F.~Gebhardt, {\sl Math. Comp.,\/} {\bf 21} (1967),708--709],
�¾ ������¼~M ������ϵ� ����ǰ�� ô����²���µ�̽˵
���û�°��, ���� ���� ��� ��������� � °���
�����ǰ��˼ ���������µ�̽���ϼ, ��� ���������µ�̽���� 丱����Ǹ
�~$X_n=F_2 \bmod m$ �~$Y_n=F_{2n+1} \bmod m$. ��ó�� ������
������������� ��� ���������µ�̽��¸ ������� �� Ƹ���ǵ���� ������ �
"�����ǰ�ɵ� ���" � ����ǽ�� ��ȸ��. ճ� ���������
�.~���»͹� (W.~J.~Westlake, {\sl JACM,\/} {\bf 14} (1967), 337--340).

\excercises
\rex[12] ����¸ǵ��� �� ����ǰ�� ���ǰ��˵ Ǹ���, ���̷����
���½�ȵ����~$X_{n+1}=(aX_n+c) \bmod m$, ���~$X_n$---\emph{Ƶ�˵.} ߾���
ǵ�� �� ����ɰ���� � ����, ��� � \emph{����ϼ�:} $U_n=X_n/m$. ൺ�����½��
ľ��û� ���~$U_n$ � ����²�µ�̽��¸ °����:
$$
U_{n+1}=(aU_n+c/m) \bmod 1.
$$
ޱ�ü��µ \emph{��ϼ��} �����̷������ �¾� ľ��û� ��� ������º� ���ǰ����
���������µ�̽��µ� � ������� �����Ƹ� � ������ɵ� ¾Ǻ��, ����ɸ��� � ��ȸ��.

\rex[�20] Ի� ž��ȵ�� ��¾ǽ��� ���ǰ���� Ǹ���
���½�ȵ���~$X_{n-1}<X_{n+1}<X_n$ ������ �˿�������� �������� � µǵ���
����� ȵ�¾� ����� �������, °� ��� ��� �������˵ ���ϴ���˵
�������Ƹ�~$X_{n-1}$, $X_n$ �~$X_{n+1}$ ����������½�. ߾����µ, �¾
ú�����˹ ��ȵ  ���ϴ�� µ� �� ����� \emph{�������} �� �����ǰ���� �
���������µ�̽��¸ 丱����Ǹ~(5).

\ex[21] ڰ��� ���������µ�̽���� ����Ǹ��� ��� �����̷������ ������¼�~M,
����~$X_0=0$, $X_{n+1}=(5X_n+3)\bmod 8$, $Y_0=0$, $Y_{n+1}=(5Y_n+1)\bmod8$
�~$k=4$? (װ����µ, �¾ ��ɽ���� ����� ��ü, °� �¾ ��ž��˵~$<X_n>$
�~$\<Y_n>$ �� ���Ⱥ�� ���ǰ���.)

\ex[00] ߾ǵ�� � ������ ������� ���������~(12) �����̷õ��� ������ �°�ȸ�
����, � �� �����-���ô� ��ó��?

\rex[20] ��������µ ����������� �����̷������ �������~$X_n=Y_n$ ���
��������� ������ ������¼�~M.

\ex[10] � µ��µ ��� ������������ ����ǽ��� ��¾��~(10) �²���������, �¾
����ȸ� ��� �����~$X$ ���ǰ��, ���� ��������½� ��������� �¾�
��¾�. ߾ǵ�� �� ���ǰ��� ��� \emph{�����}~$X$?

\ex[20] ߾����µ, �¾ ����� ����Ǹ�� ������ ���������µ�̽����
�����~$2^e$ (�.~�.\ ����˹ �� $2^e$~��������� ������¾� �������� $e$~��¾�,
��¾�˹ ������õ��� ¾�̺� ���� ��� �� ����϶���� �������), ����
�������� ���������~(10) ������ɸ� �������:
%% !!! ݵ����½�� ��ú�: °� ��� ���� \mixcode �ž��� � ���ü��� ������� \ex,
%% ��� ¾���� ����ǰ�� ��µ�����, �� ¾��, ��� � \mixcode ����������
%% �˿������� \obeylines. � �¾�� ����� ����� �� �Ǹ°���� \cr ? ڰ� �¾ �������?
$$
\vcenter{
\mixcode
LDA  & �   \cr
JANZ & *+2 \cr
LDA  & C   \cr
ADD  & X   \cr
JNOV & *+3 \cr
JAZ  & *+2 \cr
XOR  & C   \cr
STA  & X   \cr
\endmixcode
}
$$
%% 49

\ex[M39] Ծ����µ, �¾ ������¸ǽ�� ������ͽ½��
���������µ�̽����~$(3)$ ����� ������ �����~$m$ ¾��� � ¾�̺� ¾���,
����� �˿�������� ������ɸ� �������:
\medskip
\item{i)}~$c$ �~$m$---������� �����˵ Ǹ���;
\item{ii)}~$d$ �~$a-1$ ���½�~$p$---���� ��ǵ½˼ �����˼ ����µ�ϼ~$m$;
\item{iii)}~$d$---ǵ½�� �~$d\equiv a-1\pmod{4}$, ����~$m$ ���½�~$4$,
 $d\equiv a-1 \pmod{2}$, ����~$m$ ���½�~$2$;
\item{iv)}~���~$d=0$, ���~$a\equiv 1$ �~$cd\equiv 6\pmod{9}$, ����~$m$
���½�~$9$. [\emph{㺰�����.} ߾�������µ�̽����, ������������
���½�ȵ��ϼ�~$X_0=0$, $X_{n+1}=dX_n^2+aX_n+c$, ����� �� ���û�~$m$ ������
�����~$m$, ���� ¾�̺� �° ����� ������� �����~$d$ �� ���û�~$d$,
���~$d$---��������̽˹ ����µ��~$m$.]

\rex[�24] (�.~ھ���.) �����̷ùµ ���û�°� ÿ�.~8, �¾�� ��������, �¾ �
����ĸƸ�������� ��¾�� �������� ������°~(4) ����� ������� �����~$2^{e-2}$.

\ex[�29] ߾����µ, �¾ ����~$X_0$ �~$X_1$ �� ϲ������ ��� ǵ½˼�
�~$m=2^e$, ¾ ������ ���������µ�̽��¸ 丱����Ǹ~(5) �����~$3\cdot 2^{e-1}$.

\ex[�36] װ��ǰ �¾�� ÿ�������� ���¾�� � ¾�, �¾�� ����������������
����������˵ �����²� Ƶ��Ǹ������� ���������µ�̽��µ�, ô����²����ɸ�
��������½��� ���½�ȵ���
$$
X_n=a_1X_{n-1}+\cdots+a_kX_{n-k}, \rem{$n\ge k$.}
$$
���� �� ����� ��Ǹ����� ����� ������� �¾� ���������µ�̽��¸ ��
���û�~$m=p^e$, ���~$p$---����¾� Ǹ���, ¾ ����� ������� �½���µ�̽�
��������̽��� ���û�~$m$ ����� �������ȵ�� ��ɵ�� ���½��� ���� ��������,
��Ǹ������� �½���µ�̽� �µ����� ������� �������µ���~$m$.
\medskip
%
\item{a)}~�����~$f(z)$, $a(z)$, $b(z)$)---�������� � Ƶ��Ǹ�����˼� ����ĸƸ��°��;
�ô�� ������~$a(z)\equiv b(z) \pmod{f(z)\hbox{ � } m}$,
����~$a(z)=b(z)+f(z)u(z)+mv(z)$ ��� ����¾��� ���������~$u(z)$, $v(z)$ �
Ƶ��Ǹ�����˼� ����ĸƸ��°��. Ծ����µ, �¾ ���~$f(0)=1$ �~$p^e>2$
����������� ������ɵ�: "����~$z^\lambda\equiv 1 \pmod{f(z)\hbox{ � }p^e}$,
$z^\lambda\not\equiv 1\pmod{f(z)\hbox{ � }p^{e+1}}$,
¾���~$z^{p\lambda}\equiv 1 \pmod{f(z)\hbox{ � }p^{e+1}}$,
$z^{p\lambda}\not\equiv 1 \pmod{f(z)\hbox{ � } p^{e+2}}$".
%
\item{b)}~�����
$$
\eqalign{
f(z)&=1-a_1z-\cdots-a_kz^k,\cr
G(z)&=1/f(z)=A_0+A_1z+A_2z^2+\ldots\,.\cr
}
$$
ޱ����Ǹ� ��������~$\lambda(m)$ ����� �������
���������µ�̽��¸~$\<A_n\bmod m>$.  Ծ����µ, �¾~$\lambda(m)$---�������ȵ�
������µ�̽�� Ƶ���~$\lambda$, °���, �¾~$z^\lambda\equiv 1
\pmod{f(z)\hbox{ � } m}$.
%
\item{c)}~�����~$p$---����¾�, $p^e>2$ �~$\lambda(p^e)\ne \lambda(p^{e+1})$.
Ծ����µ, �¾~$\lambda(p^{e+r})=p^r\lambda(p^e)$ ��� ����~$r\ge0$. (ⰺ��
�������, �¾�� ���¸ ����� ������� ���������µ�̽��¸~$\<A_n \bmod 2^e>$,
����� ��Ǹ�����~$\lambda(4)$, $\lambda(8)$, $\lambda(16)$,~\dots{}
���ǽ�� �� µ� ���, ���� �� �� ������ �������ȵ�~$r\ge2$, °���,
�¾~$\lambda(2^{r+1})\ne\lambda(4)$. ⾳�� ����� ������� ����������
��~$\bmod 2^e$ ��� ����~$e$.)
%
\item{d)}~߾����µ, �¾ �α�� ���������µ�̽���� Ƶ��� Ǹ���,
ô����²����ɰ� ��������½��� ���½�ȵ���, ������������ � ��ǰ��
ÿ��������, ����� ������������ �ý�Ƹ�~$g(z)/f(z)$, ���~$g(z)$---����¾�˹
������� � Ƶ��Ǹ�����˼� ����ĸƸ��°��.
%
\item{e)}~����� ��������~$f(z)$ �~$g(z)$ ��~(d) ������� �����˵ ��
���û�~$p$ (��.~�.~4.6.1). Ծ����µ, �¾ ���������µ�̽����~$\<X_n \bmod
p^e>$ ����� ����� ������� � ¾ǽ��¸ °��� ��, ��� � ���Ƹ��̽��
���������µ�̽����~$\<A_n \bmod p^e>$ �~(b). (ݸ����� �˱����~$X_0$,~\dots,
 $X_{k-1}$ ���̷� ����Ǹ�� ����� �����˹ ������, °� ��� ��ɰ�
���������µ�̽���� �����°��ϵ��� �������� �������Ƹ��
"�������" ���Ƹ��̽�� ���������µ�̽��¸.) [\emph{㺰�����.} ��ɵ�²���
��������, °���, �¾~$a(z)f(z)+b(z)g(z)\equiv 1 \pmod{p^e}$. �¾ ����õ�
�� ÿ�.~4.6.2-22 (����� ӵ�����).]

\rex[�28] ݰ���µ Ƶ�˵ Ǹ���~$X_0$, $X_1$, $a$, $b$ �~$c$, °���, �¾ ���������µ�̽����
$$
X_{n+1}=(aX_n+bX_{n-1}+c)\bmod 2^e, \rem{$n\ge 1$,}
$$
%% 50
����� ���˹ ����Ⱦ� ������ �� ���� ���������µ�̽��µ� �¾�� ¸��.
[\emph{㺰�����.} $X_{n+2}=((a+1)X_{n+1}+(b-a)X_n-bX_{n-1})\bmod 2^e$ �.~ÿ�.~11~(c).]

\ex[�20] �����~$\<X_n>$ �~$\<Y_n>$--- ���������µ�̽��¸ Ƶ��� Ǹ��� ��
���û�~$m$ � ��������� �����~$\lambda_1$ �~$\lambda_2$; �����õ� �����
���������µ�̽����~$Z_n=(X_n+Y_n)\bmod m$. ߾����µ, �¾, ����~$\lambda_1$
�~$\lambda_2$---������� �����˵ Ǹ���, ���������µ�̽����~$\<Z_n>$ �����
����� �������~$\lambda_1\lambda_2$.

\ex[�24] �����~$X_n$, $Y_n$, $Z_n$, $\lambda_1$, $\lambda_2$, °��� ��,
��� � � ����˴�ɵ� ÿ��������. �����������,
�¾~$\lambda_1=2^{e_2}3^{e_3}5^{e_5}\ldots$---����������~$\lambda_1$ ��
�����˵ �����µ��, � �������ǽ�~$\lambda_2=2^{f_2}3^{f_3}5^{f_5}\ldots\,$.
�����~$\lambda_0=2^{g_2}3^{g_3}5^{g_5}\ldots$, ���~$g_p=(\max(e_p, f_p)$,
����~$e_p\ne f_p$, �~$0$, ����~$e_p=f_p$). ߾����µ, �¾
������~$\lambda'$ ���������µ�̽��¸~$Z_n$  ���µ�~$\lambda_0$, ��
ϲ�ϵ��� ����µ���~$\lambda$---�������ȵ�� ��ɵ�� ���½���~$\lambda_1$,
$\lambda_2$. � ǰ�½��¸, $\lambda'=\lambda$, ����
$(e_p\ne f_p \ror e_p=f_p=0)$ ��� ��Ϻ��� ����¾��~$p$.

\ex[�46] �¾ ����� ������� �� ������ ����� ������� ���������µ�̽��¸,
 �������˲����� ������¼��~M?

\rex[�28] ����� ����ǽ�� �����°������ ����°���~$c$, ĸ�������ɵ� �
��¾��~(10), ����� ���~$(a_1 a_2 \ldots a_k)_2$. ߾����µ, �¾
���������µ�̽���� ��¾�~$Y_0$, $Y_1$,~\dots{} ô����²��ϵ� ���½�ȵ���
$$
Y_n=(a_1Y_{n-1}+a_2Y_{n-2}+\cdots+a_kY_{n-k}) \bmod 2.
$$
[��o ����� ������������� ��� ��ó�� ������ �����������
���������µ�̽��¸. ž�� �� ����˹ ����ϴ ��Ϸ� ����� �¸� ���½�ȵ���� �
��ĵ�¸���� ����������~(10) �� �ǵ�����!]

\ex[�33] (�.~ܰ�¸�, 1934.) �����~$m, k\ge 1$---Ƶ�˵ Ǹ���
�~$X_1=X_2=\ldots=X_k=0$. Ի�~$n>0$ �������~$X_{n+k}$ ����˼ �������ȵ��
������ưµ�̽��� ���ǵ���~$y<m$, °����, �¾ $k\hbox{-�����}$ $(X_{n+1},~\ldots,
X_{n+k-1}, y)$ ����ȵ �� �����ǰ���� � ���������µ�̽��¸. ��ó���
�������, $(X_{n+1},~\ldots, X_{n+k-1}, y)$ �� ������ ��������� �~$(X_{r+1},~\ldots,
X_{r+k})$ ���~$0\le r < n$. � °��� ���ǰ� ����˹ �������˹ �����
�� $k$~Ǹ��� �ô�� �����ǰ���� � ���������µ�̽��¸ ����� ����ȵ� ���� ���.
� ���Ƶ ���ƾ� ���Ƶ�� ��°�������, ����� �� ���¸���� °����
���ǵ���~$n$, �¾~$(X_{n+1},~\ldots, X_{n+k-1}, y)$ ö� �����ǰ��� �
���������µ�̽��¸ ��� ����~$y$, $0\le y < m$. ݰ������, ����~$m=k=3$,
���������µ�̽���� °����:
$$
00022212202112102012001110100
$$
� �� �¾� ���Ƶ�� ��°�����������. a)~Ծ����µ, �¾, �����
���������µ�̽���� �����Ǹ������, �� �����~$X_{n+1}=\ldots=X_{n+k-1}=0$.
b)~Ծ����µ, �¾ \emph{����˹} $k\hbox{-�����}$ $(a_1, a_2,~\ldots, a_k)$
ͻ����¾�~$a_j$, $0\le a_j<m$, �����ǰ���� � ���������µ�̽��¸.
ỵ����µ�̽�, ��� �����Ǹ������, �����~$n=m^k$. [\emph{㺰�����.}
Ծ����µ ���úƸ�� ��~$s$, �¾ ��ϲ�ϵ���~$(a_1,~\ldots, a_s, 0,~\ldots, 0)$
�~$a_s\ne0$.] װ��¸�, �¾ ���� µ����
����������~$f(X_n,~\ldots, X_{n+k-1})=X_{n+k}$ ���~$1 \le n \le m^k$,
�������~$X_{m^k+k}=0$, ¾ ����Ǹ� �ý�Ƹ� � ��������̽� �������˼ ��������.

\ex[�22] �����~$Y_n$---���������µ�̽���� ��¾�, ����ǵ����
��¾���~(10) ���~$k=35$ �~$c=(00000000000000000000000000000000101)_2$.
�����~$U_n$---����ǽ�� �����~$(.Y_{nk}Y_{nk+1}\ldots{}Y_{nk+k-1})$. ߾����µ,
�¾ �° ���������µ�̽����~$\<U_n>$ �� ô����²��ϵ� µ���~3.3.2D ���~$d=8$.

\ex[M41] ݰ���µ ��� ������� ����¾��~$p$ �� ������� �¾��ư °��.~1 �
�.~4.5.4 ���ž��ɸ� (� ������, ú������� � µ��µ) ����°���~$a_1$, $a_2$,
°���,  �¾ ����� �������~(8) ���~$k=2$ �����~$p^2-1$.

\ex[�40] ��Ǹ���µ ����°���~$c$, ô���˵ ��� �����̷������ �� �
��¾��~(10), ����ɸ� �������� ���������� Ǹ��� �û�� � ������,
���~$1\le k \le 64$.

\ex[�35] (�. ��.) � µ��µ ������ϵ���, ��� ��ž���� �ý�Ƹ�~$f$, °���,
�¾ � ���������µ�̽��¸~(11) ����� ������� �����~$m^k-1$ ��� �������,
�¾~$m$---����¾� Ǹ���, �~$X_0$,~\dots, $X_{k-1}$ �»�ǽ� �� �û�. ߾����µ,
�¾ �¸ �ý�Ƹ� ����� ����ĸƸ������, �¾�� ����Ǹ�� ���������µ�̽��¸ ����~(11)
%% 51
� ������ �������~$m^k$ ��� \emph{����}~$m$. [\emph{㺰�����.}
Ҿ����̷ùµ�� ������~3.2.1.2Q, ������²���˼ ������� ÿ�.~7 �
���������µ�̽���ϼ� ����~$\<pX_{2n}+X_{2n+1}>$.]

\rex[�24] � µ��µ ���ö����� ����ɵ���� ��������
���������µ�̽��µ�~(8) ������Ǹ������ ���ǰ��, �����~$m$---����¾� Ǹ���.
Ծ����µ, �¾ ���°¾ǽ� ����ȸ� ������� ����� ����Ǹ��, �����~$m$
"�������� �� ������¾�", �.~�.\ �����°��ϵ��� � ���� ������������
�����ǽ�� ������� Ǹ���. (�������� °��.~3.2.1.1-1 �����˲���,
�¾~$m=w\pm1$ ǰ�¾ ô����²��ϵ� �¾� ����µ��. ܽ���� ���û�°��,
����ǵ��˵ � µ��µ, ����� ���¾�� ��������� � � �¾� ���ǰ�, ������̺�
����� ô����� ��� ��Ǹ������.)

%% 52
\subchap{�������������� �����} % 3.3
ݰȰ �������� ����ǰ ���¾�� � ����ǵ��� ���������µ�̽��µ�, ��¾�˵
��ž�� �� ���ǰ��˵. �� ö� ������, ��� �������� °���� ����Ⱦ�� �������
���������µ�̽��¸, �¾�� � ����¸ǵ���� ����ǰ� �����Ǹ�� ����������� ��
���¾�����. ��� �¾ � �����, �� ����Ⱦ� ������ �ɵ ����� �� ����ǰ��, �¾
���������µ�̽���� ž��Ȱ ��� ������. ڰ� �� ��Ȱ��, ���°¾ǽ� ��
���ǰ��� ���������µ�̽����?

���� ���� �α��� ǵ������ �������� � �ü��� � ��������� ��� ��������
100~���ǰ���� ����¸ǽ�� Ƹ��, �ǵ�� ���� Ȱ���� �� ¾, �¾ ��
���°¾ǽ� ž��Ⱦ ������ � �¸� ����������. �δ� ��������� ��������
�������Ƹ�, ����ɸ��� �� �����ǰ��˼�, °���, ��� ���� ����������
�������� Ƹ�� (ž�� �������� ������ �� 10~Ƹ�� ������ ��������� �
����˴�ɵ�). ߾�¾��, ò���� °����� ����²�µ�̽� ���ǰ���� Ǹ���,
�α�� ǵ����� ������ ����� ������, �¾ ��� ������ �� ���ǰ��˵, ��� ����
����� �� �¼�¸� ����¾�˵ �����˵ ������������¸.

ڰ� ����¸� �-�~ܰ���ư (Ƹ¸�õ��� �� ����µ �.~Gardner, {\sl Scientific
American,\/} Ͻ����, 1965), "��µ��¸�� ������������� ����¸ǽ��
�����°������ Ǹ���~$\pi$ ��� ���ǰ��˹ �ϴ, ¾��� ��� ��� ������������
¾�����µ�� Ǹ���---�¾ ������� ����ǰµ�̽�� ������������µ�". �-�~ܰ���ư
ú����, ��������, �¾ ������ ���¾���ɵ��� ��÷��ǽ�� Ǹ��� �
����������~$\pi$---�¾ 26, � �¾��� ��� ��ϲ����� ���ž����� ¾ǽ�
���������� ����� �α���½�� ���ĸ����Ƹ�:
\picture{(1) p. 52}
�˿���� ����� �ζ��� ��ó�� �����² �¸� Ƹ��, �� �����ö��, �¾, �ô�Ǹ
������̽� ��µ����¸������, Ǹ���~$\pi$ �������� ��� ��¾��� ǵ����ǵ�²�!

��� �� �˴��ϵ� ���������¸ µ��ľ���� �������, �������� ������ ��ȸ� �
�.~�., �¾�� ���ǵ �� ���������. ӻ����� ����� ����� ����������
�����ǰ���� � ¾�, �¾ �� �� ����� �������� ���� � �Ƶ���, ���ǰ��� ���
��� ������ ���������µ�̽���� Ǹ���. ݵ��ž���� �����̷����� �����-¾
����������˵ ��Ű��ǵ���� µ���.

%% 53

�°¸�¸ǵ���� µ���� ���� ��� ����¾�˵ ����ǵ�²���˵ ���µ���
���ǰ����¸. Ҿ�����˼ �� µ�°� �ú���̽� ��� ���ư. �� ���ô�� ¾�̺�
µ �� ���, ��¾�˵, �ô�Ǹ �������� ������˼� � ���Ǹµ�̽˼�,
������������ ����� ����������� �� ��Ǹ���µ�̽�� ��ȸ���.

���� ���������µ�̽���� ����� ���� ô����²���µ�̽� �½���µ�̽�
µ�¾�~$T_1$, $T_2$,~\dots{}, $T_n$, �� �� ����� ���� \emph{ò�����} � ¾�,
 �¾ ��� �˴�����, � ������ɵ� ����°���~$T_{n+1}$. ޴���� ����˹ µ��
���� ��� ��� ����ȵ � ����ȵ ò�������¸ � ���ǰ����¸ ���������µ�̽��¸.
ޱ�ǽ� ���������µ�̽���� ������ϵ��� � ������� ���ôζ��� ������ µ�¾�.
���� �� ���û�°�� ����˲����� ô����²���µ�̽˼�, �� �Ǹ°�� ��
���ǰ���� (��� �Ǹ°���� ���������� �� µ� ���, ���� �� �������� �� ����������).

ڰ���� ���������µ�̽����, ��¾��� �ô�� ��µ������ �����̷�������,
����õ� �ɰµ�̽� ���������. ߾�¾�� � ������ɸ� �������� ������ϵ���,
��� ������̽� ��������� °��� ��������. ష��ǰ���� ��� ���° µ�¾�:
\dfn{ͼ����ǵ���� µ���,} ����� ��ȸ�� �����û��õ� � ��ÿ���� Ǹ���
���������µ�̽��¸ � ���������� �Ƶ��� � ������� ������������
�°¸�¸ǵ���� ���µ����, � \dfn{µ���¸ǵ���� µ���,} ����� �� ��ž���
����¾�˵ Ű���µ���¸�� ���������µ�̽��¸, ���̷���� ��¾����
µ���� Ǹ���, �������ɸ���� �� ��������½�� ���½�ȵ���, �
������� ��¾���� �������˲����� ���������µ�̽����. � �����
�.~��İ [D.~Huff, How to Lie With Statistics, (Norton, 1954)]
Ǹ°µ�� ����� ���¸ �ϴ ��ó�� ���������Ƹ�.

\subsubchap{㽸������̽˵ µ��� ��� ������� ���ǰ���� ���������µ�̽��µ�} % 3.3.1
\section{A. ���µ���~$\chi^2$}. ���µ���~$\chi^2$ ("Ÿ-�������"), �����½�,
���˹ ��������������˹ �� ���� �°¸�¸ǵ���� ���µ����. ޽ �����̷õ���
�� ¾�̺� ��� �� ����, �� � ��� ���°���� ǰ��� ������ ��ó�� µ�¾�.
������ ǵ� �����ÿ��� � ��ɵ�� �������� ���µ���~$\chi^2$, ����������
���ǰ�� � ��ǵ�²� �������, ��� ����� �˻� �� ��������� �¾� ���µ��� ���
������� ���� � ���¸. ����� ����˹ ��� ��������� ���������� ���
"������̽˵" ���¸, ���ǵ� �������� ������ �� ��� �������� � ������
�����½����� � �˿������ ������ �� Ǹ���~$1$, $2$, $3$, $4$, $5$ �~$6$.
ҵ���½��¸ �˿������ �α�� �ü�� s ��� ����� �������� �����°����� � °���Ƶ:
$$
\vcenter{\halign{
#\hfil\bskip&\hfil$#{}$&\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr
�ü��      &   s=&2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\cr
ҵ���½����& p_s=&{1\over 36} & 1\over 18 & 1\over 12 & 1\over 9 & 5\over 36
                & 1\over 6 & 5 \over 36 & 1\over 9 & 1\over 12 & 1 \over 18
                & 1 \over 36 \cr
}}
\eqno(1)
$$(ݰ������, �ü�� s=4 ����� ���� ����ǵ�� ����� ���������:
%% 54
$1+3$, $2+2$, $3+1$; ��� $36$~��������� ��ž��� �¾ ���°��ϵ�~$3/36=1/12=p_4$.)

���� ������� ���¸ $n$~���, ����� �������, �¾ �ü��~$s$ ��ϲ���� �
������� $np_s$~���. ݰ������, ��� 144~��������� ���ǵ���~$4$ ������
��ϲ����� ����� 12~���. ỵ���ɰ� °���ư �����˲���, ����� ���û�°��
�˻� � \emph{����²�µ�̽��¸,} ����ǵ�� ��� 144~���������.
$$
\vcenter{\halign{
#\hfil\bskip&\hfil$#{}$&\hfil$#$\bskip&&\bskip\hfil$#$\hfil\bskip\cr
�ü��  &
     s=& 2 & 3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 \cr
䰺¸ǵ���� Ǹ��� �˿������&
   Y_s=& 2 & 4 & 10 & 12 & 22 & 29 & 21 & 15 & 14 &  9 &  6\cr
������� Ǹ��� �˿������ &
  np_s=& 4 & 8 & 12 & 16 & 20 & 24 & 20 & 16 & 12 &  8 &  4 \cr
}}
\eqno(2)
$$
�¼�¸�, �¾ İ�¸ǵ���� Ǹ��� �˿������ �»�ǰ���� �� �������� �� ����
���ǰ��. � �¾� ��� ��ǵ�� ô���µ�̽���. Ե�� � ¾�, �¾ ����� �������
$36{144}$~��������� ���������µ�̽��µ� ��ž��� ��� 144~��������, � ���
��� ����������½�. ޴�� �� °��� ���������µ�̽��µ� ���¾��, ��������,
¾�̺� �� ����� ("�����˵ �����"), � ����˹, � ���� "�����˵ �����"
�˿���� ����ϴ 144~����, �ô�� ò����, �¾ ���¸ ������̽˵. ܵ��� µ� �°
���������µ�̽���� °� �� �����½�, ��� � �α�� ��ó��. ڰ��� �� �������
� °��� ���ǰ� �� ����� ���������, ������̽� �� ����¾����� ������ ����
���µ�? �²�� �����ǰ���� � ¾�, �¾ ������� ����������� "��" ��� "���"
�� �� �����, �� ����� ���� \emph{�����½��½˹} �²��, �.~�.~ú�����,
������̺� �����½� ��� �������½� ������ ����¸�.

��µ�²���˹ ���� ��ȵ��� ��ȵ� ����Ǹ ���¾�� � ������ɵ�. ��Ǹ����
(�������ò � ����ɸ ���) �ü�� ������¾� ������µ� İ�¸ǵ����� Ǹ���
�˿������~$Y_s$ � �������� Ǹ��� �˿������~$np_s$ (��.~(2)):
$$
V=(Y_2-np_2)^2+(Y_3-np_3)^2+\cdots+(Y_{12}-np_{12})^2.
\eqno(3)
$$
Ի� ���ž�� �������° ���µ� ������ ����ǰ���� �½���µ�̽� �������
���ǵ���~$V$. Ҿ������� ������, ������̺� �����½� °��� ������� ���ǵ���?
���� �����½���� �� ��ϲ����� �ǵ�� ����, ������ �����~$1/100$,---�.~�.\
�º������� ���û�°° �� �������� ���ǵ��� �� °��� ������� ����Ǹ��
�������� ¾�̺� � ����� ���ǰ� ��~$100$,---¾ � ��� ���� ����������˵
��������� ��� ����������. (ݵ ����õ� ���˲���, ������, �¾ ����
\emph{ž��ȸ�} ���¸ �ô�� ������ °��� ������� ���ǵ���~$V$ ���� ���
��~100, °� �¾ ��� ����ȵ� ò�������¸ ��������� �� ���¾����
ͺ��������� � ����������, ����Ǹ��� �� ���¾��� ������� ���ǵ���~$V$.)

� �°¸�¸��~$V$ ��� �������� ������µ� �ž��� � ����˼ �����,
ž��~$(Y_7-np_7)^2$, ��������, �����½�, �ô�� ������� ����ȵ,
ǵ�~$(Y_2-np_2)^2$, °� ���~$s=7$ �����ǰ���� � ȵ��� ��� ǰɵ,
%% 55
ǵ�~$s=2$. ޺��˲�����, �¾ � "������̽��" �°¸�¸��, ��� �� ������� ����
°���, ��� ��¾��� ��������, �¾ ��� �������� ���Ǹ��, ǻ��~$(Y_7-np_7)^2$
�ž��� � �����µ���, ��¾�˹ � ȵ��� ��� ����ȵ �����µ��
���~$(Y_2-np_2)^2$. ⰺ�� �������, ����õ� ��������~(3) �� ��������� ľ��û�:
$$
V={(Y_2-np_2)^2 \over np_2}+{(Y_3-np_3)^2\over np_3}+\cdots+{(Y_{12}-np_{12})^2\over np_{12}}.
\eqno(4)
$$
޿���������� °��� ������� ����Ǹ��~$V$ ���˲��� �°¸�¸���~$\chi^2$,
���²���²��ɵ� ���ǵ��ϼ~$Y_2$,~\dots, $Y_{12}$, ����ǵ��˼ � ͺ��������µ.
߾��°���� � ��� ľ��û� ���ǵ��� ��~(2), ����ǰ��
$$
V={(2-4)^2\over 4}+{(4-8)^2\over 8}+\cdots+{(9-8)^2\over 8}+{(6-4)^2\over4}=7{7\over 48}.
\eqno(5)
$$
⵿���, ��µ�²����, ��������� ������, ϲ�ϵ��� �� ���ǵ���~$7{7\over48}$
���¾�̺� ����ȸ�, �¾ ��� ���ǰ���� ��ϲ����� ����� �Ǹ°�� ���������½˼.
������ ǵ� �²�ǰ�� �� �¾� ������, �ľ��û��õ� ���µ���~$\chi^2$ �
����� ��ɵ� ����.

�����������, �¾ ��� �������˵ ���û�°�� ����°��� ��������� ��
$k$~��µ�����. ����������  $n$~\dfn{����������� ����°���;}
�¾ ����ǰ��, �¾ ��ž� ������� ����°��� ������½� �� ���ϵ� �� ��ž�
��°�̽��. �����~$p_s$---�����½���� ¾��, �¾ ���û�°� ����°��� ������� �
��µ�����~$s$, � �����~$Y_s$---Ǹ��� ����°���, ��¾�˵ ����²�µ�̽�
\emph{������} � ��µ�����~$s$. �ľ����õ� �°¸�¸��
$$
V=\sum_{1\le s\le k} {(Y_s-np_s)^2\over np_s}.
\eqno(6)
$$

� ����˴�ɵ� ������� ������� $11$~��������� ��ž��� ��� ������ ��������
���µ�, °� �¾~$k=11$. [���û�~(4) �~(6) �����ǰ���� ¾�̺�
�ü���Ƹ��: � ����� ���ǰ� ��� ������������ ��~2 ��~12, � � ��ó��---��~$1$ ��~$k$.]

�����̷�� ¾����²�~$(Y_s-np_s)^2=Y_s^2-2np_sY_s+n^2p_s^2$ � ������²�
$$
\eqalign{
Y_1+Y_2+\cdots+Y_k&=n,\cr
p_1+p_2+\cdots+p_k&=1,\cr
}
\eqno(7)
$$
����� ������������� ľ��û�~(6) � ����
$$
V={1\over n}\sum_{1\le s \le k} \left({Y_s^2\over p_s}\right)-n,
\eqno(8)
$$
���ǵ� � ����ȸ��²� ���ǰ�� °��� ������ �����ǰ�� ��Ǹ������.

ҵ������ � ������� � ¾�, ����� ���ǵ���~$V$ ����� �Ǹ°�� ���ü�˼�.
�²�� �� �¾ ���� °��.~1, � ��¾��� ��������� "�������������~$\chi^2$ �
$\nu$~�µ���ϼ� �������" ��� ������ ���ǵ����~$\nu$. ỵ�õ� ���̷�������
������� °����� �~$\nu=k-1$; \emph{Ǹ��� "�µ����� �������" �����~$k-1$,
�.~�.\ �� ������� ����ȵ Ǹ��� ��µ�����.}
%% 56
{\everycr={\noalign{\hrule}}
\htable{ⰱ��ư~1}%
{ݵ��¾�˵ ����˵ ��� �������������~$\chi^2$}%
{\offinterlineskip
\strut\vrule\bskip$#$\bskip\hfil\vrule&&\bskip\hfil$#$\bskip\hfil\vrule\cr
\noalign{
\embedpar{
\noindent
(Ѿ��� ����˵ °����� ��. � Handbook of Mathematical Functions, ed.\
 by M.~Abramowitz and I.~A.~Stegun, U.~S. Government Printing Office, 1964,
Table~26.8)
}
}
       & p=99\%  & p=95\%  & p=75\% & p=50\% & p=25\%& p=5\% & p=1\% \cr
\nu=1  & 0.00016 & 0.00393 & 0.1015 & 0.4549 & 1.323 & 3.841 & 6.635\cr
\nu=2  & 0.00201 & 0.1026  & 0.5753 & 1.386  & 2.773 & 5.991 & 9.210\cr
\nu=3  & 0.1148  & 0.3518  & 1.213  & 2.366  & 4.108 & 7.815 & 11,34\cr
\nu=4  & 0.2971  & 0.7107  & 1.923  & 3.357  & 5.385 & 9.488 & 13.28\cr
\nu=5  & 0.5543  & 1.1455  & 2.675  & 4.351  & 6.626 & 11.07 & 15.09\cr
\nu=6  & 0.8720  & 1.635   & 3.455  & 5.348  & 7.841 & 12.59 & 16.81\cr
\nu=7  & 1.239   & 2.167   & 4.255  & 6.346  & 9.037 & 14.07 & 18.48\cr
\nu=8  & 1.646   & 2.733   & 5.071  & 7.344  & 10.22 & 15.51 & 20.09\cr
\nu=9  & 2.088   & 3.325   & 5.899  & 8.343  & 11.39 & 16.92 & 21.67\cr
\nu=10 & 2.558   & 3.940   & 6.737  & 9.342  & 12.55 & 18.31 & 23.21\cr
\nu=11 & 3.053   & 4.575   & 7.584  & 10.34  & 13.70 & 19.68 & 24.73\cr
\nu=12 & 3.571   & 5.226   & 8.438  & 11.34  & 14.84 & 21.03 & 26.22\cr
\nu=15 & 5.229   & 7.261   & 11.04  & 14.34  & 18.25 & 25.00 & 30.58\cr
\nu=20 & 8.260   & 10.85   & 15.45  & 19.34  & 23.83 & 31.41 & 37.57\cr
\nu=30 & 14.95   & 18.49   & 24.48  & 29.34  & 34.80 & 43.77 & 50.89\cr
\nu=50 & 29.71   & 34.76   & 42.94  & 49.33  & 56.33 & 67.50 & 76.15\cr
\nu>30 & \multispan{7} \hfil\emph{��������µ�̽�~$\nu+2\sqrt{\nu}x_p+{4\over3}x^2_p-{2\over3}$\hfil}\vrule\cr
x_p=   & -2.33   & -1.64   & -.675  & 0.00   & 0.675 & 1.64  & 2.33\cr
}}
(ݰ ���ø¸���� ������ �¾ ����� �������� ������ɸ� �������:
���ǵ���~$Y_1$, $Y_2$,~\dots, $Y_k$ �� ������ ����������, °� ���~$Y_1$,
��������~(7), ����� ��Ǹ�����, ����~$Y_2$,~\dots, $Y_k$. ỵ����µ�̽�,
������� $k-1$~�µ����� �������. Ѿ��� ������� ���ü��°Ƹ� �ô��
��������� ����.)

���� � °���Ƶ � ������~$\nu$ � �������~$p$ ��ž����� Ǹ���~$x$, ¾ �¾
����ǰ��, �¾ ���ǵ���~$V$, �������ϵ��� �� ľ��û�~(8), �ô�� ����ȵ~$x$
� �����½�����~$p$. ݰ������, ���~$p=5$\% �~$\nu=10$ °���ư ����
���ǵ���~$x=18.31$; �¾ ����ǰ��, �¾~$V>18.31$ ¾�̺� �~$5$\% ���� ���ǰ��.

�����������, �¾ �������˹ ���Ƶ�� �������� ���µ� �������õ��� �� ��� �
������� ���������µ�̽��¸ Ǹ���, ��¾�˵
%% 57
�������������� ���ǰ��˼�, � �¾ ����ǵ�� ������ɸ� ���û�°��:
$$
\vcenter{
\halign{#\bskip\hfil&\bskip\hfil$#{}$&$#$\bskip\hfil&&\bskip\hfil$#$\bskip\cr
              &   s=& 2 &  3&  4&  5&  6&  7&  8&  9& 10& 11& 12\cr
�����������~1 & Y_s=& 4 & 10& 10& 13& 20& 18& 18& 11& 13& 14& 13\cr
�����������~2 & Y_s=& 3 &  7& 11& 15& 19& 24& 21& 17& 13&  9&  5\cr
}
}
\eqno(9)
$$
��Ǹ���� �°¸�¸�� ���µ���~$\chi^2$, ����ǰ�� � ������
���ǰ� $V_1=29{59\over 120}$, � �� �¾��� ���ǰ�~$V_2=1{17\over 120}$.
ⰱ��ǽ˵ ���ǵ���, ���²���²��ɸ� $10$~�µ���ϼ �������, �����˲���,
�¾~$V_1$ \emph{ϲ�� ���Ⱥ��, ������;} $V$~�˲��� ����ȵ, ǵ�~$23.2$,
¾�̺� � ����� ���Ƶ�µ ���ǰ��! (Ѿ��� ����˵ °����� �����˲���, �¾
�����½���� ��ϲ����� �¾�� ����Ⱦ�� ���ǵ���~$V$ �����~$0.1$\%.)
ⰺ�� �������, � ͺ��������µ~1 ���������������� ���Ǹµ�̽�� �º�������
�� �����.

� ��ó�� �¾����, $V_2$ �ǵ�� ����, ��¾�� �¾~$Y_s$ � ͺ��������µ~2
��������� �ǵ�� ������ � ������� ���ǵ��ϼ~$np_s$ [��.~�~(2)]. ط °�����
�������������~$\chi^2$ ����õ�, �¾ �~$99$\% ���ǰ�� $V$~������ ����
����ȵ, ǵ�~$2.56$. ׽�ǵ���~$V_2$ \emph{ϲ�� ���Ⱥ�� ����;} ����ǵ��˵ �
ͺ��������µ ���ǵ���~$V_3$
%% ?? V_s
���¾�̺� ������ � ������� ���ǵ��ϼ, �¾ ���������� �Ǹ°�� �¾�
ͺ��������� ���ǰ��˼ ����°����. (� ����� ����, �� ����� ������
°���� ����õ�, �¾ ��� $10$~�µ����� ������� °��� ������
���ǵ���~$V$ �����ǰ���� ¾�̺� � $0.03$\%~���ǰ��). ݰ�����, � �������
°����� �������������~$\chi^2$ ����� ��������� ����ǵ���� ���� �~(5)
���ǵ���~$V=7{7\over 48}$. ޽� �������� � ��µ���� �����~$75$ �~$50$\%,
°� �¾ �� �� ����� �Ǹ°�� ��� ���Ⱥ�� ������� ��� ���Ⱥ�� ������; ����˵,
�����°�����˵ �~(2), ô����²����� ���µ���~$\chi^2$.

Ѿ��ȸ� ������ɵ�²�� ���������������� ��¾�� ϲ�ϵ��� ¾, �¾ ���� � µ
�� °���ǽ˵ ���ǵ��� �����̷����� ��� �α��~$n$ � �α��
�����½�����~$p_s$. մ���²����� ���������� ϲ�ϵ���~$\nu=k-1$. ݰ �����
���� ���������˵ � °���Ƶ ���ǵ��� �� ϲ������ ������½� ¾ǽ˼� �� ����
���ǰ��: \emph{�¾ ����������˵ ���ǵ���, ����������˵ ���� ��� ���°¾ǽ�
����ȸ� ���ǵ����~$n$.} ڰ� ������ ������ ����~$n$? Ծ�°¾ǽ�
����ȸ�� ����� �Ǹ°�� °��� ���ǵ���~$n$, ��� ��¾��� �α�� ��~$np_s$
�� ����ȵ~$5$; ������ ���ȵ �����~$n$ ���Ǹµ�̽� ����ȸ��, �¾�� ��������
���������� ���µ���. װ��¸�, �¾ � ������������� �������� ��
�����~$n=144$, � $np_2$~����ϻ��� �����~$4$, �¾ ���¸����Ǹ� ¾�̺� �¾
�ľ��û���������� �������. մ���²����� ���Ǹ�� �¾�� ����ȵ��� �������
� ¾�, �¾ ��¾�� ������� ������� ���¸; � ���û�°µ Ǹ��� �� °�����
��������� �� �ǵ�� ���ž��ɸ�� ��� ��ȵ�� ���ǰ�. �˻� �� ������� ���ȵ
������¸ �¸ ͺ���������� �� ��ȸ�� ���~$n=1000$ ���~$10\,000$,
��� ����~$100\,000$.

%% 58

ݰ ����� ���� ������ � �˱���~$n$ �� °� �����. ���� �� ���¸ �˻�
����²�µ�̽� ��������̽˵, �¾ ���ϲ�ϻ��� �� ��� ����� ó����
����ȸ�~$n$ (��.~ÿ�.~12). ݾ ��� ����ȸ� ���ǵ����~$n$ ����� ������������
\emph{�����̽˵} �º�������, °���, ��� ������ɸ� ��ó �� ��ó�� �����
Ǹ��� � ���̽˼ ���µ��¸ǵ���� ���ɵ���� � ���¸��������˵ �¾����. ���
����²�µ�̽�� �������� ���µ� �¾�� ����� �� ���������, °� ���
��� ����� �����̷����� ���� � µ �� ���¸, �� ���� ���� ����
� ���������µ�̽��¸ Ǹ���, ����ǵ���� �� ���, ¾ °��� ¸� �º������� ��
���ǰ����� ��������� ������ ��������. � ��Ϸ�
\picture{
 ��.~2. ൷û�°�� 90~�������� � �����̷������� ���µ���~$\chi^2$ (��. �~���.~5).
}
� �¸� ����µ�̽� ��������� �������� � ������� ���µ���~$\chi^2$ ���
������ ���ǵ����~$n$, �� � �α�� ���ǰ� �¸ ���ǵ��� ������ ����
�����̽� ����ȸ��.

�°�, �������� � ������� ���µ���~$\chi^2$ �����ǰ���� � ������ɵ�.
���������� $n$~����������� ����°���, ���~$n$---���°¾ǽ� ����Ⱦ� Ǹ���.
(ỵ�õ� �������� ���������� ���µ���~$\chi^2$ � ���ǰ��, ���� ����°���
�� ����������; ��., ��������, ÿ�.~10, ��� ���������� ���ǰ�, ����� ����
�������� ����¸� ������� �� ��ó��.) ߾��Ǹ�˲����� Ǹ��� ����°���,
���û�°� ��¾��� �½������ � ������ �� $k$~��µ�����, � �� ľ��û��~(6)
���~(8) ��Ǹ��ϵ��� ���ǵ���~$V$. װµ�~$V$ ������������ � Ǹ�����
�� °��.~1 ���~$\nu=k-1$. ���� $V$~����ȵ ���ǵ���,
���²���²��ɵ��~$p=99\%$, ��� ����ȵ ���ǵ���, ���²���²��ɵ��~$p=1\%$,
¾ ���û�°�� ��������� ��� �����°¾ǽ� ���ǰ��˵. ����~$p$
%% 59
����� �����~99 �~95\% ��� �����~5 �~1\%, ¾ ���û�°�� �Ǹ°����
"�������µ�̽˼�"; ��� ���ǵ����~$p$, ����ǵ���� ��µ�����Ƹ�� ��
°���Ƶ, �����ǵ���� �����~$95$ �~$90$\% ���~$10$ �~$5$\%, ���û�°��
"������ �������µ�̽�". ��¾ � ������� ���µ���~$\chi^2$ ��������� ��
������� ���� ��� ���� ����˵ ǰ�¸ ������õ���� �ϴ� Ǹ���, �, ���� ��
����� ���� ��� �� ���� ���û�°�� ����˲����� �������µ�̽˼�, Ǹ���
�±���˲����� ��� �����°¾ǽ� ���ǰ��˵.

��������� � ��ǵ�²� ������� ���.~2, ��� �ŵ��¸ǵ��� �����°�����
���û�°�� �������� � ������� ���µ���~$\chi^2$ ȵ�¸ ���������µ�̽��µ�
���ǰ���� Ǹ���. Ի� ������ ���������µ�̽��¸ �������� ���� ������
�������� (���������� �� ���µ���~$\chi^2$), ������ �� ��¾���
���¾�ϻ��� �� ���� ������ �ǰ�º�� ���������µ�̽��¸. � ���Ǹ��~A
�����̷���� ��¾� ܰ�������-ܰ����̸ (������¼~3.2.2�), � ���Ǹ��~E---��¾�
丱����Ǹ, ��°�̽˵ ���Ǹ�� ���²���²��� ������˼
������ͽ½˼ ���������µ�̽���ϼ �� ������ɸ�� �����������:
\ctable{#\hfil\bskip&\bskip # \hfil\cr
԰�Ǹ�~�:& $X_0=0$, $a=3141592653$, $c=2718281829$, $m=2^{35}$.\cr
԰�Ǹ�~C:& $X_0=0$, $a=2^7+1$, $c=1$, $m=2^{35}$.\cr
԰�Ǹ�~D:& $X_0=47594118$, $a=23$, $c=0$,  $m=10^8+1$.\cr
԰�Ǹ�~F:& $X_0=314159265$, $a=2^{18}+1$, $c=1$, $m=2^{35}$.\cr
}
൷û�°��, ���������˵ �� ���.~2, ��������� ������� ������ɸ� �˲���.
԰�Ǹ��~A, B, D ���Ȼ� ����°��� ô����²���µ�̽�, ���Ǹ�~C ��ž�����
�� ����� � ������ ����, ��-��������, ����������, � ���Ǹ��~E �~F
����������� �� ���Ȼ� ����°���. ԰�Ǹ�~F, ����������, ������ɵ�;
���Ǹ��~C �~D ���ö������ � ��µ������, �� � ��� ���Ⱥ�� ����
���ǵ���~$a$. � ���Ǹ��~D ���������� ��¾� ��ǵ¾� � ¾� ����, � �����
�� �˻ �����˵ ��������� ۵����� �~1948~�., � � ���Ǹ��~C---������˹
������ͽ½˹ ��¾� �~$c\ne 0$ °��� � ��� �������ǰ�̽�� ���� (�µ�����, 1960).

ݵ����̺� ��ó�� ���ž� � �ö����� � ���û�°°� �������� ��
���µ���~$\chi^2$, ��� �����̷������ °��� ����¸�, ��� "�������µ�̽˹",
"������ �������µ�̽˹" �~�.~�., � ����� ��������ɸ� ���������� ��
������ ad hoc, ����˲����� ���� � �¾� �������.

\section{B. ���µ��� ھ���������-Ἰ����� (��-���µ���)}. ڰ� ��
������, ���µ���~$\chi^2$ ������ϵ��� � µ� ���ǰ��, ����� ���û�°��
����°��� ����������� �� ����ǽ�� Ǹ��� $k$~��µ�����. ޴���� �������
���ǰ��˵ ����Ǹ�� ����� ��������� �������ǽ� ����� ���ǵ���. � ǰ�½��¸,
�������ǽ� ����� ���ǵ��� ��������� ��ɵ�²���˵ ���ǰ��˵ Ǹ��� �
��µ����� �����~$0$ �~$1$. ��� ������²� ���ǵ��� ���ǰ���� Ǹ���,
����ǵ���� �
%%60
��Ǹ���µ�̽�� ��ȸ��, ��������� ������ǵ��, žµ���� ��, �¾�� �¾ ����� ��
����˲����� �� ���û�°°� ���ǵ¾�.

� µ���� �����½��µ� � �°¸�¸�� �����¾ �����̷����� ���� � µ ��
������ǵ��� ��� �������� ������½�� � ������˲��� �������������. �����
����õ��� ������� ������������� ���ǵ��� ���ǰ���� ����Ǹ��~$X$. �¾
�������� � ������� \dfn{�ý�Ƹ� �������������~$F(x)$,} ���
$$
F (x) = \hbox{�����½���� ¾��, �¾~$(X\le x)$.}
$$
ݰ ���.~3 �����°����� ��� �������. ߵ��˹ �� ���---�ý�Ƹ� �������������
\emph{���ǰ����� ��°,} �.~�.\ ���ǰ���� ����Ǹ��~$X$,
\picture{��.~3. ������� �ý�Ƹ� �������������.}
��������ɵ� ���ǵ���~$0$ ���~$1$, ������ � �����½�����~$1/2$. ݰ ���.~3,~b
�������� �ý�Ƹ� ������������� \emph{��ɵ�²����� ���ǰ���� ����Ǹ��,
���������� ��������������} ����� �û�� � �����Ƶ�, °� �¾ �����½����
¾��, �¾~$X\le x$, ����¾ �����~$x$, ����~$0\le x \le 1$. ݰ������,
�����½���� ¾��, �¾~$X\le{2\over3}$, �����~$2\over3$.
ݰ ���.~3,~c �������� ������̽�� ������������� ���ǵ���~$V$
� ���µ���~$\chi^2$ (��� 10~�µ����� �������); �¾ �� �������������, �� �
��ó�� ľ���, �˻� ö� �����°����� � °��.~1. װ��¸�, �¾~$F(x)$ ������
������°�� ��~$0$ ��~$1$ ��� ò���ǵ���~$x$ ��~$-\infty$ ��~$+\infty$.

�����̷�� ���ǵ���~$X_1$, $X_2$,~\dots, $X_n$ ���ǰ���� ����Ǹ��~$X$,
����ǵ��˵ � ���û�°µ ����������� ����°���, ����� ������-
%% 61
\bye
