\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
