\input style
\chapnotrue\chapno=3\subchno=3\subsubchno=3
������� ���~$(a+6)/m$. ⎗��� �������� ����� ���������� ��������� �
������� ���������~(17), ��������� �����~B �~C.
\proofend
�� �����������~(40) �������� ��������� ������������� ���������� ���������.
��-������, ��� ����������, ��� ���� �������� ����� ��������~$a$. � ������
�������, ������� ��������~$a$ ��� �� ����������� ����, ��� ����������
����� ����, ��� ���� �������� � �������~1; ������ ���������~(40)
����� ���������~$a/m$, � ����� ��� ������� ���������~$a/m$ �����������
���������� ������. ����~$a\approx\sqrt{m}$, �������� ������������
���������������� ���������� ���������� ���������~$2/\sqrt{m}$.

ᎎ��������~(40) �������� � ��� ������ ��������~$c$. �� ��� ��� �� �����
������������~$c$ ������ ����: �����~$c$ �~$m$ ������ ����, �������
��������. ����, ����� ����,
$$
\eqalign{
{c\over m} \approx {1\over 2}-{1\over 6}\sqrt{3}&\approx 0.21132\,48654\,051871 \approx \cr
                                                &\approx {\it (0.15414\,54272\,33746\,34354\,55716)}_8, \cr
}
\eqno(41)
$$
����������� ���������������� ���������� ����� ���������, ��� ��� �����
���������~$1-6x+6x^2=0$ �����~${1\over 2}\pm{1\over 6}\sqrt{3}$. 품�
��������� ����� ������������, ���� ����������� ������ �����������
������������ ������~$c$.

�� ��� ��� ���� ��� � ���������� �����~$X_n$ �~$X_{n+1}$. ���������� �����
����� ������ ���������� �����~$X_n$ �~$X_{n+2}$, � ������ ���� �� �������,
���� �� ���������� �����~$X_n$ �~$X_{n+t}$ ���� ������, ������,
���~$1\le t \le 10$. ����� ���� �������� (��.\ �������~(3.2.1-6)), ���
$$
X_{n+t}=(a_t X_n+c_t) \bmod m,
\eqno(42)
$$
���
$$
a_t=a^t \bmod m, \qquad c_t=(a^t-1)c/(a-1)\bmod m.
\eqno(43)
$$
\emph{� ������� ����������� ���� ������ ����� ��������� �����������
���������� �����~$X_n$ �~$X_{n+t}$, ���� ������~$a$  �~$c$
����������~$a_t$ �~$c_t$.} �������, $c_t$ ��� �� ����� �������������
�������~(41), �� � ���� �������� ���������.

������������ ���������~(40) ������� ������� �.~����� ({\sl JACM,\/} {\bf 7}
(1960), 72--74) � ���������� ���������� �� ���� \emph{��������������
������}~$x$ �����~$0$ �~$m$, � �� ������ �� ����� ��������� (��.~���.~21).
������, ����������� �������� ������ ���������, ���� ������� �������
�.~������������
({\sl Math. Comp.,\/} {\bf 15} (1961), 383--389) � �.~�����
({\sl BIT,\/} {\bf 4} (1964), 6--27). � �� �������� ����� ��������� ��
��������������. ��� �������� ������� ��� ������������ ����������������
����������, ��, � ���������, �� ������������ ������� ������� ���������,
%%102
������������ �������� �� �������������. �� ������� ��������, ���
����������� ���������� �����~$X_n$ �~$X_{n+t}$ ������~$0.000003$ ���
������� �~$m=2^{35}$, $a=2^{24}+5$, $c=1$ ��� ����~$t\le 2500$. � �������
������������� ����� (��.~�.~3.3.4) ����� ��������, ��� ������������ ����
�������� �� �������; ��� �� ����� ��������� ����---������� �������������
����, ��� � ���������� ������ �������, ����������� �� ��������
������������ ������ � ����������� ������� ���������, �����
������� ������ ���������������� ����������. [\emph{���������.} ���
����� ������� ������� ��� ������������ ���������������� ���������� �
������������������� �~$c=0$ � ����������, �������������� ������������
������ ���~$m=2^e$. 품 ���������� � �������� ���������� �������������
� ���� �����; ��.~���.~3.2.1 2-9.]

ᓌ�� ���������~$\sigma(h, k, c)$ � ����� ���������� (���
�������� ������~$c=0$) ���� ������� ����������� �.~���������� �~1892~�.\
� ��� ������, ����������� ������������� ��������. 풀 �������
�������������� ������� ��������; ������ ���������� �� ������� �������
����� ����� � ������� �.~������
[{\sl Journal f\"ur die reine und angewandte Mathematik,\/} {\bf 201}
(1959), 37--70], � ����� �.~���������� �~�.~〉�����
[{\sl American Journal of Mathematics,\/} {\bf 63} (1941), 377--407].

��� ��������� \emph{���������} ������ ����� ������� � ����������� �
����� �������. ������� �����, ������� ������� �� ���, ����������� �
���������: \emph{��������� � �������� ������������ ������ ������ ����
���������� �����.} �. ����� ���.~3.3.4-7, ��� ���������� ����������
�������� �������~P.

\excercises (��ࢠ� ����)
\ex[�07] ���������, ������ ���������~(7) ����� ����� ��������~$x$,
��� �������~$s(x)<x$, $0\le x < m$.

\ex[�24] �������� �������������� �����������~(12)

\ex[��22] ��������� � ��� 䓐�� (�������� ����� ������ � ��������)
�������~$f(x)=\dlp x \drp$.

\rex[�18] ������ ���������� ��������� ��������~$d$ (� ������������
�������~P), ����~$m=10^{10}$, � �������� ������� �����~$10$?

\ex[M21] �������� �������~(17).

\ex[�27] �����~$hh'+kk'=1$ (a)~��������, �� ��������� �������~B �~C, ���
$$
\sigma(h, k, c)=\sigma(h, k, 0)+12\sum_{0\le j < c}\dlp{h' j \over k} \drp + 6 \dlp {h' c \over k} \drp
$$
��� ����~$c\ge 0$. (b)~��������, ��� ���~$0 \le c < h$ �~$0 \le c < k$
$$
\dlp {h' c \over k} \drp + \dlp {k' c \over h} \drp = {c \over hk}.
$$
(c)~� �������������� �����~B �������� �������������� ���������~(20).

\rex[�24] ���������� �������������� ������ ����������~(19) ���~$c=0$,
���������� �� ����� ���.~1.2.4-45.

%% 103
\rex[M34] �����
$$
\rho(p, q, r)=12 \sum_{0\le j < r} \dlp{jp\over r}\drp \dlp{jq\over r}\drp.
$$
������� �����, �������������� ��� �������������� �����~B, ��������
��������� �������� ����������� (���������� �����������): "����~$p$, $q$
�~$r$ ������� ������� ������, ��
$$
\rho(p, q, r)+\rho(q, r, p)+\rho(r, p, q)={p\over qr}+{q\over rp}+{r\over pq}=3."
$$
(����� ���������� ��� ����  ��������� ���~$c=0$ �������� �������
������� ����� ��������� ���~$r=1$.)

\ex[M40] ᓙ������� �� ������� �������������� �����������
���������� (��.~���.~8), ������� �������� ������� ������� ��������������,
�������������� � ���.~7?

\ex[�20] �������� �����������~(34) �� ��������� ����� ����������, ��������
�~$\sigma(h, k, c)$.

\ex[M30] 䎐���� � ������ ���� ����������� ���������~$\sigma(h, k, c)$,
�����~$h$ �~$k$ ������� ������. � ����� ������ �������~$hh'\equiv d \pmod{k}$,
���~$d$---���������� ����� ��������~$h$ �~$k$. ��������, ���
$$
\sigma(h, k, c)=\sigma(h/d, k/d, \floor{c/d})+\delta,
$$
���~$\delta=0$ ���~$c \bmod d =0$ �
$$
\delta=6\dlp{\floor{c/d} h'd \over k}\drp
$$
���~$c\bmod d\ne 0$.

\ex[�24] ��������, ��� ����~$h$ �~$k$ ������� ������,
��~$\abs{\sigma(h, k, c)}<(k-1)(k-2)/k$.

\ex[�22] �~(37) ��������� \emph{������������} �������� ��� ������������
���������������� ���������� ���~$m=2^{35}$, $a=2^{34}+1$, $c=1$. 煌�
����� ������ ��������?

\rex[�24] ��� �������� ���������������� ���������� � ���������
������������� ������� �~$m=2^{35}$, $a=2^{18}+1$, $c=1$ ���� �����������
��� ������� ������������������ �� 1000~����� � ������; �� ���� �������
����������� ���������� ��������� �������� �������: ��~$0.2$ ��~$0.3$.
����� ����� ����������� ���������������� ���������� ��� ����� ������� ��
����� ������� � $2^{35}$~�����?

\ex[�22] ���������� ������ �������� ������������
���������������� ���������� � ������� ������~$a=1$.

\ex[�24] ��� �� ��� �����, ��������, ������������ ����� ����
������ ��������� ����� ���~$a=1$. �������� � ������� �������~P, ���,
�������� �� ���, ����� ��������� ����� �, ��� ����������� ����������
�����������~$(X_{n+1}<X_n)$ ����� ����� ������ �~$1/2$ ���� ���~$a=1$.
����� ����� ��������� �����~$c$, ��� ����������� ����������������
���������� ����� ����� ������. ����� �� ������� ��������~$c$ ���, �����
����������� ��� ��� ������� ������������?

\ex[M21] ���������, ��� ������� ����� ��������~$a$, ����� ���~$c$, ���
�~$c_2$ ������������� ������������� �����������~(41), ���~$c_2$---����������
������������������, ��������~(43).

\rex[M35] �������
$$
S(h, k, c, z)=\sum_{0\le j <z}\dlp{hj+c\over k}\drp.
$$
��� ������� �������~$h$ �~$k$ �������� "������� ����������", �������
������� ���������� ��������� �������� ���� �������, ������� ����, ��� �
������� ����~B �~C ����������� ��������~$\sigma(h, k, c)$.
[\emph{㊀�����:} ��.~���.~6.]

%% 104
\rex[M35] \emph{�������� �����,} ��������� � ���������� ������� �����
��������� �� ������ �������. �����~$\alpha$, $\beta$, $\gamma$,
$\delta$---����� �����, ������~$0\le\alpha<\beta\le m$,
$0\le\gamma<\delta\le m$. �������� ����������� ��� ����������� ����,
���~$\alpha\le X_n<\beta$ �~$\gamma\le X_{n+1}<\delta$.

\ex[M24] ��������~(26) ����� o������, ����� ���������� ��������� ���~$\sigma(h, k, c)$.

\excercises (���� ����)
�� ������ ������� ������ ������� � ������ ������� ������� ������, ������
����� ���������� ��� ����������� ������������ ��������� ���������� �� ��
����� ���������, � �� ����� ��������� ���������~$x$. 厒� ����� ����������
����� �������������, ��� ������� ���� �� ����������� �������.

ㄎ���� ����� ����� ���� � �������~$U_n$, ������������ ����� �����
� ��������; ��� �������� ������������ �������������������~$U_n=X_n/m$, ���
���~$U_{n+1}=\{aU_n+\theta\}$, ���~$\theta=c/m$, �~$\{x\}$ ��������~$x\bmod 1$.
��������, ������� ��� ������������ ���������������� ����������
��������� ���
$$
C=\left(\int_0^1 x\{ax+\theta\}\,dx-\left(\int_0^1 x\, dx\right)^2\right)
\bigg/ \left(\int_0^1 x^2\, dx-\left(\int_0^1 x\,dx\right)^2\right).
$$

\rex[BM23] (�. �����.) 煌� �����~$C$ � ������ ��� ����������� �������?

\rex[M22] �����~$a$---����� ����� �~$0\le\theta<1$.
����~$x$---�������������� �����, ����������� �����~$0$ �~$1$,
�~$s(x)=\{ax+\theta\}$, �� ������ �����������, ���~$s(x)<x$? (풎 ������
�������~P ��� �������������� �����.)

\ex[M28] ���������� ���������� ���� ����������� ����, ���~$U_{n+1}<U_n$.
������ ����������� ����, ���~$U_{n+2}<U_{n+1}<U_n$, ����~$U_n$---���������
�������������� �����,  ����������� ����� ����� � ��������?

\ex[M29] ᎕����� ������� ���������� ������ � �������~$\theta=0$, ��������,
 ��� ����������� ���������� ����������~$U_n>U_{n+1}>\cdots>U_{n+t-1}$ �
�������� �����
$$
{1\over t!}\left(1+{1\over a}\right)\ldots\left(1+{t-2\over a}\right).
$$
������ ������� ����� ���������� ���� �����, ������������� ��
�������� ���������� ����� ����� � �������� �����~$U_n$?

\rex[M25] �����~$\alpha$, $\beta$, $\gamma$, $\delta$---��������������
�����, ������~$0\le\alpha<\beta\le1$, $0\le \gamma<\delta\le 1$. ������
����������� ����, ���~$\alpha\le x < \beta$ �~$\gamma\le s(x)<\delta$,
���� ��������� ������������� ���.~22?  (풎 ������ ���.~19 ���
�������������� �����.)

\ex[M21] ���������� ������, ���������� �� ������ 䈁������
�~$U_{n+1}=\{U_n+U_{n-1}\}$. �����������, ���~$U_1$ �~$U_2$ ����������
���������� ��������� ������� ����� ����� � ��������, ������� �����������
����, ���~$U_1<U_2<U_3$, $U_1<U_3<U_2$, $U_2<U_1<U_3$ �~�.~�.
[\emph{㊀�����:} ��������� "��������� �������", �.~�.\ ����� ��
���������~$\{\,(x, y) \mid 0\le x, y<1\,\}$, �� ����� ������, �
����������� �� ����������� �����~$x$, $y$ �~$\{x+y\}$, � ����������
������� ������ �����.]

\ex[M27] ����� �������� ����� ��� �������, ���������� � ����������
����������, ���������� ���������� � ��������� ��������, ����� ���� �������
�� ��� ������� � ��������~$U_0$, � �������---$U_1$. ���������� �����������
����, ���~$U_1$ �������� ��������� ������ ������������� ���� �����~$k$,
�.~�.~$U_0>U_1<\ldots<U_k>U_{k+1}$. ᐀����� ��������� � ����������������
������������� ��� ��������� ������������������.

\rex[M35] ��� ��������� ������������� ������� ��������~$2$ �����������
�������~$X_{n-1}-2X_n+X_{n+1}\equiv (a-1)c \pmod{m}$
(��.~�������~(3.2.1.3-5)). ����������� ������, ������� ��������
����������� ��������, �������~$U_{n+1}=\{\alpha+2U_n-U_{n-1}\}$.   ��
��� � ���.~26, ��������� ��������� �������
%% 105
�� �����, ������������ ��������� ����������� �����~$U_{n-1}$,
$U_n$�~$U_{n+1}$ ��� ������ ����~$(U_{n-1}, U_n)$. ᓙ������� ��
��������~$\alpha$, ��� ������� ������ �� ����� ��������� ����������� �����
����� ������� �������������� � ������������~$1/6$, ����~$U_{n-1}$ �~$U_n$
���������� �������� � ���������
��������?

\subsubchap{Ꮕ��������� ����} % 3.3.4
������ ���� ��� �������� ����������� ���������� �� ��� ��������
������������������� �������������� � 1965~�.\ �.~����� �~�.~���������.
풎� ���� ����������� ���, ��� ��� ��������� ������ �������, ����������
�� �������� ������������ ������, ���� �� \emph{�����������,} � �� �����,
��� ��� ������� ������� ������ �����������������! ����������, ��� ��������
����������� �� ��������� ������, � ����� � ��� �� ����������� ������� ��������.

Ꮕ��������� ���� �������� ���������� ��� "������������", ��� �
"�������������" ������, ������������� � ���������� ��������. ��� � �
������������� ������, � ��� ��������������� ��������, ����������� �� �����
�������. � ������ �������, ��� ��������� ����������� ��������� ���������
�������� �������, ��� ������ ��� ������� �� ������������ �����.

����������� ����� ����� ������� ������������� ���������� � ������������
�����. 爒����� ��� ������ ���������� � ���������� ������������� �������
����� � ���������~D ������� ������, ��� ���������� �������� ������
����������� ������������� �����.

\section{A.~ⅎ���, ������� � ������ �����}. �������������� ������������
������������� ����� ������ "�������� �������������� 䓐��" �������,
������������ �� �������� ���������. ���������� ������ ���������
�������������� 䓐�� ��� ������������� � ���������� ������� ���
�������������� �����~3.3.3~B; ���������� ������ ������� ��������������
䓐�� � ����� ������.

��� ����� ����������� ����������� ��������
�������~$F(t_1, t_2,~\ldots, t_n)$, ������������ ��� ���� ���������� �����
�����~$t_k$, ���~$0\le t_k < m$ ���~$1\le k \le n$, ������
\dfn{�������������� 䓐��}
$$
f(s_1, s_2, \ldots, s_n)=
\sum_{0\le t_1,\ldots, t_n<m} \exp\left({-2\pi i \over m}
(s_1t_1+\cdots+s_nt_n)\right) F(t_1, \ldots, t_n).
\eqno(1)
$$

䓍����~$f$ ���������� ��� ���� ���������� �����~$s_k$; ��� �������������
������� � ��� ������,
���~$f(s_1,~\ldots, s_n)=f(s_1 \bmod m,~\ldots, s_n \bmod m)$. 璎��
������� ��� ����������� �
%% 106
��������� ����������� �������, �������, ���
$$
\exp\left({-2\pi i \over m} (s_1 t_1 + s_2 t_2 + \cdots + s_n t_n)\right)
=\omega^{-(s_1t_1+s_2t_2+\cdots+s_nt_n)},
$$
����~$\omega=e^{2\pi i/m}$---������ $m\hbox{-�}$~������� �� �������.
⅐��� "��������������" � ������ ������ ��������, ��� ��� ��������
�������~$F(t_1,~\ldots, t_n)$ ����� ������������ �� ��
��������������~$f(s_1,~\ldots, s_n)$ � ����������� � ��������� ���� (��.~���.~1):
$$
F(t_1,~\ldots, t_n)={1\over m^n}\sum_{0\le s_1, \ldots, s_n<m}
\exp\left({2\pi i\over m} (s_1t_1+\cdots+s_nt_n)\right) f(s_1,~\ldots, s_n).
\eqno(2)
$$
풓 ������� ����� ��������, ��������� ������ � �������� ��� ��������
�������� � ������������ ������ 䓐��. ��������~$(1/m^n)f(s_1,~\ldots, s_n)$
�������� ���������� $n\hbox{-������}$ ����������� ������� ����� �
���������~$s_1/m$,~\dots, $s_n/m$, ����~$F(t_1,~\ldots, t_n)$ ������������
� ����~(2).

�� �����������~(1) �~(2) �������, ��� ������������ ����� ���������� �����
��������~$F$ �� �� ��������������~$f$, � ��������. 瀑�� ������ �������
�������� � ��������������� 䓐�� �������, � ����� ���������� ��������
��������������, ����� ������� ����������� �������� �������� �������.

��������� ��������� ��� ��������� � �������� ��������� ��������� �����.
����� ������ ����������� ������������������ ����� ����� $X_0$, $X_1$,
$X_2$,~\dots, ������~$0\le X_k < m$, � �����~$n$---������������� (������
���������) ������������� ����� �����. ���������
$$
F(t_1, \ldots, t_n)=\lim_{N\to\infty} {1\over N}
\sum_{0\le k <N} \delta_{X_k t_1} \delta_{X_{k+1}t_2} \ldots\delta_{X_{k+n-1}t_n}.
\eqno(3)
$$
풀 ������� ����� ���������� ��������� ����� ���������
����������~$(t_1,~\ldots, t_n)$ � ���� $n$~��������� ���� �� ������ ���������
������������������~$X_0$, $X_1$, $X_2$,~$\ldots\,$.   ��� ��� ����������
������������� ������������������~$X_0$, $X_1$, $X_2$,~\dots, ����� �������,
��� ������ �~(3) ����������, ������ ��� ���������� ������� �����
�����~$N$ ������ ����� �������. � ������������� ���������
������������������ � ����������� �������������� ����� ���������� ��
$t$~����� ������ ���������� � ���������� ��������, ��� ���
$F(t_1,~\ldots, t_n)$~������ ���� �����~$1/m^n$ ��� �����~$t_1$,~\dots, $t_n$.

��������� �������������� 䓐�� �������~(3), �������
$$
f(s_1,~\ldots, s_n)=\lim_{N\to\infty}{1\over N}\sum_{0\le k < N}
\exp\left({-2\pi i \over m}(s_1 X_k+s_2X_{k+1}+\cdots+s_n X_{k+n-1})\right).
\eqno(4)
$$
%% 107
����� �� ����� ���� � ������������� ��������� �������������������, ������
���������� ����� ���������~$1/m^n$; ��� ��� \emph{��� ���������
������������������ �� ������ ��������}
$$
f(s_1,~\ldots, s_n)=\cases{
 1, & ���� $s_1\equiv \cdots \equiv s_n \equiv 0 \pmod{m}$; \cr
 0 & � ��������� ������.\cr
}
\eqno(5)
$$

� ������������� ������, ������������� �����, ������������ ������� ��������
�� ������� �������. ��� ����������� �������� �� �����-���� �������,
��������� ��~$n$ ��������� ���� �� ������ ���������, ���������� �
�������� �����~$F(t_1,~\ldots, t_n)$. ��������, ����������� ����,
���~$X_k<X_{k+1}$, ����� ��������~$F(t_1, t_2)$, ���������������� ��
����~$0\le t_1 < t_2 < m$; ����� ��� �� ������~$n=2$ ��������� ����������
����������� ���������������� ���������� (��.~���.~5).

  ��� �����~$f(s_1,~\ldots, s_n)$ �������� � ���� ���
���������� ��~$F(t_1,~\ldots, t_n)$, ��� ����� ����� ������������ �
\emph{�����} ������������� �����. ዅ����������, ����� �������, ���
�������� ����������~$f(s_1,~\ldots, s_n)$ �� ��������~(5), ����������
������������� ��������� ������������������, ����� ������������
��� �������� �����������.

��� �������� ������������ �������������������~$f(s_1,~\ldots, s_n)$ �����
����� ������� ���, ���� ������ ������� ��~$F(t_1,~\ldots, t_n)$.
���������� �������� ������������ ������������������ � �����������~$a$,
$m$, $c$ �~$X_0$, ������� \emph{������������ ����� �������} � ������������
� ��������~3.2.1.2�. ��� ����� ������������������
$$
\eqalignno{
f(s_1,~\ldots, s_n)&={1\over m}
 \sum_{0\le k < m} \exp\left({-2\pi i \over m} (s_1 X_k+s_2 X_{k+1}+\cdots+s_n X_{k+n-1})\right)=\cr
&={1\over m}
 \sum_{0\le k < m} \exp\left({-2\pi i \over m}\left(s(a)X_k+{s(a)-s(1)\over a-1} c \right) \right), & (6) \cr
}
$$
���
$$
s(a)=s_1+s_2 a+ s_3 a^2+\cdots+s_n a^{n-1},
\eqno(7)
$$
��� ���
$$
X_{k+r}\equiv a^r X_k+{a^r-1\over a-1} c \pmod{m}
$$
�������� �������~(3.2.1-6). �� ������������, ��� ������������������ �����
������������ ������, ��� ��� � ��� ����������� ��� ��������~$X_k$;
�������������, (6) �������� �
$$
{1\over m} \sum_{0\le k <m}
 \exp\left({-2\pi i \over m}\left(s(a)k+{s(a)-s(1)\over a-1} c\right)\right).
$$
%% 108
풎 ����� �������������� ����������, ������� ����� �������� ���������
�������� �������:
$$
f(s_1, \ldots, s_n)=\exp \left({-2\pi i c \over m} \left({s(a)-s(1) \over a-1}\right )\right) \delta\left({s(a)\over m}\right),
\eqno(8)
$$
���~$\delta(x)=1$, ����~$x$---�����, �~$\delta(x)=0$ � ��������� ������.

��������, ��� �������~(2) ���������
����������������~$f(s_1, s_2,~\dots, s_n)/m^n$ ��������� ��� ���������
$n\hbox{-������}$  ����������� ������� �����
$$
\omega(t_1, \ldots, t_n)=\exp\left(2\pi i \left({s_1\over m}t_1+\cdots+{s_n \over m} t_n\right)\right).
\eqno(9)
$$
"�������� �����"~$\nu$, ��������������� "�������" ���� �����,
������������ �� �������
$$
\nu=\sqrt{s_1^2+\cdots+s_n^2}
\rem {���~$\abs{s_k}\le {m \over 2}$ ���~$1\le k < n$.}
\eqno (10)
$$

ᎃ�����~(5), ������� ����, ����� ���������� ����� (� ������� ��������),
�� ������ ����������, ���� ������������������ $X_0$, $X_1$, $X_2$,~\dots{}
������������� ���������. ������� ������������� ��������� � ���������
�������� ������� �� ���������� �� �����������. ����� �����
��������~$f(s_1,~\ldots, s_n)$ ���� ������ �� �����������. ��������, ���� �����
������������� ��������� ������������������ � �������� ������ ������ ��
$N\hbox{-�}$~���� (��� �������~$N$), ������������������ ���������
���������, � ��������~$f(s_1,~\ldots, s_n)$ ����� �������~$1/N$; ������
���������� ����� ����������. �������, ������, ���, ��������~(8),
��������~$f(s_1,~\ldots,  s_n)$ ����� ����~$0$, ����~$1$, �
���~$\abs{f(s_1,~\ldots, s_n)}=1$ � ����������� �� ����� ���� � ����. �
����� ����� ��������� ��������, ��� \emph{�������������� ����������
������� ������ �� �����������, ��� ���������������.} ���������, ��������,
��� ����������, ���� ��������~$X_k$ ��~$2X_k$ �~$m$ ��~$2m$. ᎃ�����~(4),
$f(s_1,~\ldots, s_n)$ �� ���������, �� ������ ����� ������ ����
���������� �~$\abs{s_k}\le m$, � �� �~$\abs{s_k}\le m/2$. �������� ����
�������� ����������, ��� ���� ����� ��������� ������������������ �����
�����~$X_0$, $X_1$, $X_2$,~\dots{} �~$m=2^e$ � ������ ����������� �������
������� � �������� ������������� ������� ����� ������������������, �� ���
������������ ������, ����, ���� � �.~�.\ �������� �������� �����
���������� ���������� � ��������� �������~$2^{e-1}$, $2^{e-2}$,
$2^{e-3}$ �~�.~�. 풎� ����, � ����� ������, ����������� � ���.~(10),
�������� � ���������� ������������ ����������.
\emph{����~$\nu_n$---���������� ��������� �������� ��������� �����~(10), ���
��������~$f(s_1,~\ldots, s_n)\ne 0$ � �������� ������������
������������������ � ������������ ��������, �� ������������������~$X_0/m$,
$X_1/m$, $X_2/m$,~\dots{} ����� ������� ������������������� ���������
�����, ���������� �������������� �����~$0$ �~$1$
%% 109
� �������������� � "���������" ��� � "������� ����������"~$1/\nu_n$,
������ ���� ���� � ������������� $n$~���������������� �������� �
����������� �� ������� �������.} � ���.~27 ���������� ��� ����
������������� ����� �������� ������ � �������������� ��������������,
������������ ����� ��������� �������� ��������~$\nu_n$.

䎐����~(8) ���� "������" �������� ������������ ������������������,
�.~�.\ ����������, ����� ���� ���� ������� � �������������� 䓐��
�������~$F(t_1, \ldots, t_n)$. �� �����, ���~$f(s_1,~\ldots, s_n)=0$
������, ����� �������, �����
$$
s_1+s_2 a+s_3 a^2 + \cdots + s_n a^{n-1} \equiv 0\pmod{m},
\eqno (11)
$$
� ��� ����~$\abs{f(s_1,~\ldots, s_n)}=1$. ዅ����������, \emph{���
�������� ������������ ������������������� � ������������ ��������
���������� ��������� �������� ����� � ������� �����
$$
\nu_n=\min\sqrt{s_1^2+s_2^2+\cdots+s_n^2},
\eqno(12)
$$
��� ������� ������� �� ���� $n\hbox{-�������}$ ����� �����
$(s_1, s_2,~\ldots, s_n) \ne (0, 0,~\ldots, 0)$, ���������������~(11).}
�������, ��� ��� ������� �� ������� �� ����������~$c$ ��������
������������ ������������������.

����� �� ��������� ����� ���������� �������� �����������
����������� �������� ������� ����������� ����� �������� ������������
������������������. ��������� �������� �������� ���������-�������� ������,
����� ��������, ���
$$
\nu_n \le \gamma_n m^{1/n},
\eqno(13)
$$
���~$\gamma_n$ ��������� ��������
$$
1,  (4/3)^{1/4}, 2^{1/6}, 2^{1/4}, 2^{3/10}, (64/3)^{1/12}, 2^{3/7}, 2^{1/2}
$$
���~$n=1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ [��.~���.~9, � ����� ���.~332
� ����� J.~W.~S.~Cassels, An Introduction to the Geometry of
Numbers, Springer, Berlin (1959)]. ��� ����� ������������� (�
��������~$m$) ������������������~$U_0$, $U_1$, $U_2$,~\dots{} �����,
������� �����~$0$ �~$1$, ��������� �� ������� �������, ������������
���~$m^{1/n}$. ���� � ���, ���, �������� ����������������� ���� �������,
���������� � ���������~$1/\nu$ ������������� � �������������
���������������� �������� ������������ (��� �����~$\nu$) ����, ��� ������
��~$\nu^n$ ��������� �������� ($\floor{\nu U_{k+1}}$,
$\floor{\nu U_{k+2}}$,~\dots, $\floor{\nu U_{k+n}}$) ������ ����������
�������������� � ���������� �������� � �������� �������; �������������, ��
����������� ����������� �� �������� ������������ �����������~$\nu^n \le m$.

\section{B. �������}. ��� ������� ������� ��������������� �������������
�� �������. ������� �������� ������������
%% 110
������������������ �
$$
X_0=0, \qquad a=3141592621, \qquad c=1, \qquad m=10^{10}.
\eqno (14)
$$
����������� ��������� ��������~$s_1^2+s_2^2$, ��� ��������
$$
s_1+3141592621s_2 \equiv 0 \pmod{10^{10}},
$$
�������������~$s_1=67654$, $s_2=226$, ��� ���
$$
\nu_2=\sqrt{67654^2+226^2} \approx 67654.4.
$$
풎 ��������, ��� ������������������
$$
U_0, U_1, U_2, \ldots = X_0/m, X_1/m, X_2/m, \ldots
$$
����� ������� ��������� � ������ ������������� ��� ��������� ���� ��
������ �����~$(U_k, U_{k+1})$ �� ������ �������, ���� ������������
���������~$1/67654$; �.~�.\ ������ 16~�������� � �������� �������������
����� ����� ������� ���������� � ��������� ������. ����������, �����������
��������� ��������~$s_1^2+s_2^2+s_3^2$, ��� ��������
$$
s_1+3141592621s_2+3141592621^2s_3 \equiv 0 \pmod{10^{10}},
$$
�������������~$s_1=227$, $s_2=983$, $s_3=130$; �������������,
$$
\nu_3=\sqrt{1034718}\approx 1017.2.
$$
 �� �������, ���� ��������������� ������������� �����~$(U_k, U_{k+1},
U_{k+2})$, �� ����� �������� ����� � 10~�������� ��������. ��������,
$3141592621$---�� ����� ������� ���������;
������� �� ������, ��� �� �������� ����������, �� �� ������ (��������,
������� ���������~$3141592821$ ����~$\nu_3\approx 1912$, �� �������
��������~$\nu_2$). ᎃ�����~(13), ���~$m=10^{10}$ ���������� ��������~$\nu_3>2425$.

����������� ��������� ��������~$s_1^2+s_2^2+s_3^2+s_4^2$, ��� ��������
$$
s_1+3141592621s_2+3141592621^2s_3+3141592621^3s_4 \equiv 0 \pmod{10^{10}},
$$
����� ����� ���~$s_1=52$, $s_2=-203$, $s_3=-54$, $s_4=125$, ��� ���
$$
\nu_4=\sqrt{62454} \approx 249.9.
$$

␅������� ������������� \emph{��������} �������� �������� �� 8~��������
������ (��� ����������� ���������� ����� ������ ����������).

��������~$\nu_n$ ���~$n=5$, $6$,~\dots{} ����� �����, ��� ��� ���� ��
������������� ������� ������ ������������� ����������. ��������, ���
�������� ����� (��.~�.~3.3.2) ����� ����������� ���� ��������. (���
������������ ������� �� ����� �������, ��� � ����� ������, �������
��������� ������������, ������� ������������ ���������� � ������������
����� �� �����; ������ �������������
%% 111
������� ���� �� ����� ������������, �� ������ ������
���~$m<2^{40}$.) ��� ���������������� �������~$s_1=-8$, $s_2=-14$, $s_3=6$,
$s_4=-18$, $s_5=34$ �
$$
\eqalign{
\nu_5 &= \sqrt{1776} \approx 42.2, \cr
\nu_6&=\sqrt{542}\approx 23.3.\cr
}
$$

  ��� ����� �� �����, ������ ��������� ���������� ��������~$\nu_n$,
������ ����� ����������, ����� ��������~$\nu_n$ ����� �������
�������������������. �������������� �������� ������������ � ��������
���� ����������� ����� ���������� � $n\hbox{-������}$ ������������,
������������� ������������~$(x_1 m-x_2a-x_3a^2-\cdots-x_na^{n-1})^2+x_2^2+\cdots+x_n^2\le \nu_n^2$,
��� ��� ���� ����� �������������� ����������� ��������� � ���������
�����~$(x_1, x_2,~\ldots, x_n)$---\emph{�������������} �������
���������~(11).  �� �������, ��� ����������� ������������� ���������~$a$
� �������� ������������ ������������������ � ������������ �������� ��
���������� ��������� ��������
$$
C_n={\pi^{n/2}\nu_n^n \over (n/2)!m}.
\eqno(15)
$$
$\bigl($~� ���� �������
$$
\left({n\over 2}\right)!=\left({n\over2}\right) \left({n\over2}-1\right)
\ldots \left({1\over2}\right)\sqrt{\pi} \rem{��� ��������~$n$.}\bigr)
\eqno(16)
$$
 �� �������,
$$
C_1=2\nu_1/m, \quad C_2=\pi\nu_2^2/m, \quad C_3={4\over3}\pi_3^3/m,
C_4={1\over2}\pi^2\nu_4^4/m \rem{� �. �.}
$$
������� ��������~$C_n$ ������������� �����������, �����---����������
�����������. � ����.~1 ������������ �������� ��� ��������� ��������
������������������� ($C_1$ ������ �����~$2$). �������, ��������������
� �������~1--4 ���� �������, ���� ��� ����������� � �.~3.3.1 (��.~���.~2 �~5).
� ��������~1 �~2 ������� ��� ���������. ����� ������ ������~3 ����
������� ��������~$C_2$, �� ����� ������~$C_3$ �~$C_4$; ��� ����~$\nu_3=6$
�~$\nu_4=2$. � �������~4 "���������" ���������; ���� ������ ������� ������
��������� � �������������� ������������ ������, �� ��������~$C_2$, $C_3$
�~$C_4$ � ���� �� ����� ������.

������~7 �� ������ ��� �������������; ����� � ��� ������������ ������� �
�������� �����������. �������, ��� ���������~$3141592221$ �������� �
��������� ������� ��������~$C_3$ (��.~������~5), ������ ��� ��� ��
��������~$a$ �~$m=2^{35}$ (��. \ ������~9) ���������� ������� ����������.

%% 112

\htable{ ���� 1}%
{��������� ����������, ���������� ��� ������ ������������� �����}%
{\hfil$#$\bskip&&\bskip$#$\bskip\hfil\cr
ᒐ��� & a & m & C_2 & C_3 & C_4 \cr
\noalign{\hrule}
 1 & 23              & 10^8+1  & 0.000017 & 0.00051     & 0.014       \cr
 2 & 2^7+1           & 2^{35}  & 0.000002 & 0.00026     & 0.040       \cr
 3 & 2^{18}+1        & 2^{35}  & 3.14     & 0.000000002 & 0.000000003 \cr
 4 & 3141592653      & 2^{35}  & 0.27     & 0.13        & 0.11        \cr
 5 & 3141592221      & 10^{10} & 1.35     & 0.06        & 4.67        \cr
 6 & 3141592421      & 10^{10} & 2.69     & 0.35        & 0.54        \cr
 7 & 3141592621      & 10^{10} & 1.44     & 0.43        & 1.91        \cr
 8 & 3141592821      & 10^{10} & 0.16     & 2.90        & 0.34        \cr
 9 & 3141592221      & 2^{35}  & 1.24     & 1.69        & 1.11        \cr
10 & 3141592621      & 2^{35}  & 3.02     & 0.17        & 1.25        \cr
11 & 2718281821      & 2^{35}  & 2.59     & 1.15        & 1.75        \cr
12 & 2^{23}+2^{12}+5 & 2^{35}  & 0.015    & 2.78        & 0.066       \cr
13 & 2^{23}+2^{13}+5 & 2^{35}  & 0.015    & 1.48        & 0.066       \cr
14 & 2^{23}+2^{14}+5 & 2^{35}  & 1.12     & 1.66        & 0.066       \cr
15 & 2^{22}+2^{13}+5 & 2^{35}  & 0.75     & 0.30        & 0.066       \cr
16 & 2^{24}+2^{13}+5 & 2^{35}  & 0.0008   & 2.92        & 0.066       \cr
17 & 5^{13}          & 2^{35}  & 3.03     & 0.61        & 1.84        \cr
18 & 5^{15}          & 2^{35}  & 2.02     & 4.12        & 4.04        \cr
   & \hbox{\emph{������� ������� ��������}~(13):} \span & 3.63 & 5.90 & 9.86 \cr
}

� ��������~12--16 � �������� �������������~$a$ ����� �� 4~�������;
���������� ����� ������� ������ ������~14, �� � � ���� �������������
������ ��������~$C_4$. �� ��������� ���������� ��� ��� 5~�������� ����
���������� ��������~$C_4$; ����� ����, �� ���� �������~$s_1=-125$,
$s_2=75$, $s_3=15$, $s_4=1$! ��������� �������� ����� ������� �
�������~16 �������� ��������~$C_3$ ��� ������~$C_2$; � ����
������~$\nu_2=\nu_3$, ��� ��� ������� ���~$n=3$ �����������
���~$s_1=-2043$, $s_2=2047$, $s_3=0$.

� ��������~17 �~18 ������������ ���������, ������� ����������
����������� � ��� ���, ��� �� ���������� �.~–���� � ������ 50-� �����.
�� ���������� ���������� �������� ���������� ���������~$5^{15}$ ����
��������� ���������� �� ���� �������, ���������� � ����.~1.

����������, ����������� � ����.~1, � ����������� ���� ������ � ������� ��
�������������� ����� �������� ��������� �������, ��� ���������~$a$
\emph{������� ������ ������������ ����}, ���� ������ ��~$C_2$, $C_3$
�~$C_4\ge 0.1$; ���� ��� ��� ������ (��� �����) �������, �� ����� �������,
��� ������������ ���� ������� � �������. ������ ��� ������������� ������
��� ������ �����������, ����� ��������� �����~$C_5$, $C_6$ �~�.~�. ���
���� ����� ���������,  ��� ������~$m$ ���������� ����� ��� �����������
%% 113
��������� �������� ��������� �����, ���� ������������� ��������~$\nu_2$,
$\nu_3$  �~$\nu_4$; ��� �����~$m$ ������������������ ����������, ����������
� ������� ������������� �����, ��� �� ����������� ����������� ������� ���
�������� ������� �����-����� � ������� �����������.

\section{C.~����� ��������������� ������}. ����������� �������
������������ ������� ���������� ������������� �����. ������ � �����
������������ ��������, �������, ������������ ������:
���������� �� ���� �����-������ ����������� ���������� ��������~$\nu_n$,
���������� �� ������� ����� ��������� �������? ���, ��������, �����
��������, ��� ������ ���������~$s_1=227$, $s_2=983$ �~$s_3=130$
������������� ������� �����~$s_1^2+s_2^2+s_3^2$ ��� ����������
�������~$s_1+3141592621s_2+3141592621^2s_3\equiv 0 \pmod{10^{10}}$?
��������, ��� � ������� �������� �� ����� ���� � ����.

���������� �������� ���������� �������������� ����� ��� ������� ����
������. ������ ����� �������� �� ������ ��� ����������� ������������,
����������� �� �������~(11) �~(12), � ��������� ������������� ������:
���������� ������� �����
$$
(x_1m-ax_2-a^2x_3-\cdots-a^{n-1}x_n)^2+x_2^2+x_3^2+\cdots+x_n^2
\eqno(17)
$$
��� ����� ���������~$x_1$, $x_2$,~\dots, $x_n$, �� ������� ���� �� ���� ��
����� ����.

����� ��������� �, ��������, �������� ����������� ��������� �����
������� ����� ����� ������: \emph{���������� ������� �����
$$
(a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n)^2+\cdots+(a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n)^2
\eqno(18)
$$
��� ����� ���������~$x_1$,~\dots, $x_n$, �� ������� ���� �� ���� �� �����
����,} � ��� �������, ��� ������� �������������~$A=(a_{ij})$ �� ���������.
���������~(18) ���������� "������������ ������������ ������������ ������".

� ���������� �������~$x$, $y$,~\dots{} ����� ������������ ������-�������
$$
\pmatrix{
 x_1\cr
 x_2\cr
 \vdots\cr
 x_n\cr
},
\pmatrix{
 y_1\cr
 y_2\cr
 \vdots\cr
 y_n\cr
}, \ldots
$$
"ኀ������ ������������" $x\cdot y = x_1 y_1+\cdots+x_ny_n$ ����� ����
�������� � ��������� ������������ ���~$x^Ty$, ��� $T$~���������� ������
�������� �� ������, � �������� (����������������). ��� �������� ������
��������� �����������:
$$
Q=A^TA, \quad B=A^{-1}, \quad R=Q^{-1}=BB^T.
\eqno(19)
$$
%% 113
����� $A_j$~���������� $j\hbox{-�}$~\emph{�������} �������~$A$,
�~$B_i$---$i\hbox{-�}$~\emph{������} �������~$B$. ⎃�� �����
$$
B_i\cdot A_j=\delta_{ij}, \quad Q_{ij}=A_i\cdot A_j, \quad R_{ij}=B_i\cdot B_j.
\eqno (20)
$$
���� ������ ������� � ���, ����� ��������������~(18), �.~�.\
��������������~$(Ax)\cdot(Ax)=x^TA^TAx=x^TQx$ ��� ����� ��������~$x\ne0$.

������ ����� ������� ������ ��������, �.~�.\ �������, ��� �� ����
���������� ��� ����������� ��������� ��������~$x$, ����� ����� �������.
�����~$e_k$---������, $k\hbox{-�}$~���������� �������� �����~$1$, �
��������� ����. ⎃��
$$
x_k = e_k^T x = e_k^T B Ax = (B^T e_k)\cdot(Ax) = B_k\cdot (Ax)
$$
�, �������� ����������� 肀���,
$$
(B_k\cdot (Ax))^2 \le (B_k\cdot B_k) ((Ax)\cdot(Ax))=R_{kk}(x^TQx).
$$
ዅ����������, ����~$x$---��������� ������, ��������������~$x^T Qx$, ��
$$
x_k^2\le R_{kk}(x^T Qx) \le R_{kk}(e_j^T Qe_j)=R_{kk}Q_{jj},
\rem{$1\le j$, $k\le n$.}
\eqno(21)
$$
풎 ��������, ��� ����� ��������~$x$, ������� ���� ����������� ��� ������
��������, ����������. �� ����� ���� �� �������� ��������� ����� ����� ���������.

\proclaim �����~A. ����
$$
x=\pmatrix{
x_1\cr
\vdots\cr
x_n\cr
}
$$
---��������� ������������� ������ � ����������� ���������~$x^TQx$,
a~$q$---��������~$y^TQ$ ��� ���������� ���������� ��������������
�������~$y$, ��
$$
x_k^2\le R_{kk}q. \endmark
\eqno(22)
$$

��������, ��� ������ �����~(22) ����� ���� ��� ��� ������� �������, �����
������� ������� ��� ����������� ����������, ��� ��� ��������� ����������
���������� ������������������. ��������� � ������ �� �������� ������� �
������ ���������������� � ���������� �������---������ ������ ����������.
���������� ����������� ����
$$
y=Ux,
\eqno(23)
$$
���~$U$---������������� �������, ������������ �������~$\det U=\pm 1$. 풎
��������, ��� ����~$x$---������-�������, ��������� �� ����� �����, �� �����
�� �~$y$, � �������, ���� ������~$y$ �����, ��~$x$ ����� ���������� ��
�����������~$x=U^{-1}y$. (틅����� �������~$U^{-1}$
%% 115
����� ������, ��� ��� ��� �����~$\adj (U)/\det(U)$.) ዅ����������, ���� �
��������~$x$ ��������� ��� ������������� �������, �� ��� �� ���������
�������� �������� �~$y=Ux$, � �������; �����, $y=0$ ������ ���~$x=0$.
������� ����� ������� �� ������ � �����������~$(Ax)\cdot(Ax)$ ���
�����~$x\ne0$ � ������������� ������ � ����������
��������~$(AU^{-1}y)\cdot(AU^{-1}y)$ ��� �����~$y\ne0$.

\proclaim �����~B. �����~$U$---����� ������������� ������� �~$\det U=\pm1$, � �����
$$
A'=AU^{-1}, \quad B'=Ub, \quad Q'=(U^{-1})^T QU^{-1}, \quad R'=URU^T.
\eqno(24)
$$
������ �����������, ������������ ���������~$A'$, $B'$, $Q'$, $R'$,  �����
�� �� ����� �������, ��� � ������, ������������ ���������~$A$, $B$, $Q$, $R$.\endmark

⅏��� ����� ���������� ����������� ������ ���������� ������������
�������� ��������� �������: ������� �� �������� ������ � ������ � �������
���������� �������~$U$ � ��������� ��� �� ��� ���, ���� �� ���������
������, ��� ������� ����������� � �����~A ��������� ���������� ������
������� �� ������� ������� �����.

���������� ������� � ��������� ��� ����� ����� ��������, ������������
������� �����~$1$, ����� ������� �������
$$
\eqalign{
U&=\pmatrix{
1   \cr
    & \ddots \cr
    &        & 1       \cr
c_1 & \ldots & c_{k-1} & 1 & c_{k+1} & \ldots & c_n \cr
    &        &         &   & 1       \cr
    &        &         &   &         & \ddots \cr
    &        &         &   &         &        & 1 \cr
} \cr
U^{-1}&=\pmatrix{
1    \cr
     & \ddots \cr
     &        & 1        \cr
-c_1 & \ldots & -c_{k-1} & 1 & -c_{k+1} & \ldots & -c_n \cr
     &        &          &   & 1        \cr
     &        &          &   &          & \ddots \cr
     &        &          &   &          &        & 1    \cr
} \cr
}
\eqno(25)
$$
���~$c_1$,~\dots, $c_n$---����� ����� ��������, $k$---������������� �����
�����. ��� �������� ������, ����� ���������, ����� ����. � ���� ������
�����������~$y=Ux$ �������� ������, ���~$y_j=x_j$ ���~$j\ne k$
�~$y_k=x_k+\sum_{j\ne k} c_j x_j$; ����������, ��� �������� ������������
������ �����������. ��������� ������������, �������������
%%116
�~(24), � ���� ������ ����� �����:
$$
\eqalignter{
A'_j&=A_j-c_jA_k & \rem{���~$j\ne k$, $A_k'=A_k$;}\cr
B'_j&=B_j & \rem{���~$j\ne k$, $B'_k=B_k+\sum_{j\ne k} c_j B_j$.}\cr
}
\eqno(26)
$$
⅏��� ����� ��������� ���������� ����� ��������~$k$ �~$c_j$. ���
�����~$c_j$ � �����~$k$ �������~$U$ �~(25) � �������� �������� ������
���������� ���������������. � ������������ �~(21) ���������� �������
����� �����~$c_1$,~\dots, $c_{k-1}$, $c_{k+1}$,~\dots, $c_n$ ���, �����
\emph{������������ ��������} ��� �������~$Q'$, ��� �~$R'$ ���� ��� �����
������. � ����� � ���� ����������� ��������� ��� ��������� �������:

\medskip
\item{a)}\emph{��� ����� ����� ������� �������������� �����~$c_j$
���~$j\ne k$, ����� �������������� �������� ������������ ���������
�������~$Q'=(U^{-1})^T Q U^{-1}$?}

\item{b)}\emph{��� ����� ����� ������� �������������� �����~$c_j$
���~$j\ne k$, ����� �������������� �������� ������������ ��������� �������~$R'=URU^T$?}
\medskip

� ������~(a) ������������ �������� �������~$Q'$, ������~$A'_j\cdot A'_j$
��������~(20), ����� �������� ���������������~$U$ ��� ����~$j\ne k$. �����
������, ��� ������� ���������
$$
\eqalign{
(A_j-c_jA_k)\cdot(A_j-c_jA_k)&=Q_{jj}-2c_jQ_{jk}+c_j^2Q_{kk}=\cr
                             &=Q_{kk}(c_j-Q_{jk}/Q_{kk})^2+Q_{jj}-Q_{jk}^2/Q_{kk}\cr
}
$$
����������� ���
$$
c_j=Q_{jk}/Q_{kk}.
\eqno(27)
$$

������������� (���.~8) ������ ����������� � ����� ������ ������������ ���
�������~$A_k$, ����� ��� ���������~$c_jA_k$ �� �������~$A_j$
�������������� ������~$A'_j$ ���� ����������� �����. ��� ����� ����
������� �����~$c_j$, ����� $A'_j$~���� ��������������� �~$A_k$
(�.~�.~$A'_j\cdot A'_k=Q'_{jk}=0$), � ��� ����������� � �������~(27).

� ������~(b) ������������ �������� ������~$R'$ �~$R$ ���������,
�����~$R'_{kk}=B'_k\cdot B'_k$. ����� ��� ���� �������~$c_j$ ���, �����
\picture{���. 8. �������������� ������������� ������ ������� (27).}
%% 117
������~$B_k+\sum_{j\ne k} c_jB_j$ ���� ����������� �����. �������������
��� ��������, ��� �� ��������� � �������~$B_k$ ��������� ������, ������� �
$(n-1)\hbox{-������}$ ��������������, ������������
���������~$\{\,B_j \mid j\ne k\,\}$.   ��, ��� � ������, ���������� ��
���.~8, ������� �����������, ����� $B'_k$~��������������� ��������������,
$B'_k$~��������������� ����~$B'_j$ ���~$j\ne k$.  �� �������,
���������� ������ ������� ���������~$B'_kB'_j=0$, �.~�.
$$
R_{kj}+\sum_{i\ne k} c_i R_{ij}=0, \rem{$1\le j \le n$, $j \ne k$.}
\eqno(28)
$$
ᒐ���� �������������� ����, ��� ������~(b) �������� �
������� ���������~(28), ����������� � ���.~12.

⅏���, ����� ��� ������~(a) �~(b) ������, �� ��������� � ���������
����������: �������� �� ��������~$c$ � ������������ �~(27), �����
�������������� ������������ �������� �������~$Q'$, ��� � ������������
�~(28), ����� �������������� ������������ ��������~$R'$? � ����� �������
������ �����~(21) ����������, ������� ������, ����� �������
����������������. � �������, ����� ����������� �����: �������~(27) �~(28)
���������� ���������! ���������~$R'=(Q')^{-1}$ ��������, ���
�������������� �������� � $k\hbox{-�}$~������ �
$k\hbox{-�}$~�������~$Q'$ ����� ���� ����� � ������ �����, ����� �����
���� �������������� �������� � $k\hbox{-�}$~������ �~$k\hbox{-�}$~�������
�������~$R'$. ������� � �����~(a) �~(b) ���� � �� �� �������. � ����������
�����������, ��� ����� ������� ������������ ������������ ������������
��������~$Q$ �~$R$. (�������, ��� �� ������ ��� ������� ������ ���
���������� "������� ��������������� 茈���".)

�������, �� ����� ���� �������~(a) �~(b) ����������� ��� �������
���������~$c_j$, � �� ����� ������������ � �������~$U$ ������ �����
��������. ��� ���� �������~$A'_j$ � �������� ����������������~$A'_k$
����������. ����, ������, ������� � ��������~$c_j$ \emph{���������
�~$Q_{jk}/Q_{kk}$ ����� �����,} �� ��� ����� ��������� ����� ��������
������~(a) � ������� � (�� \emph{��} ������ ������) ���������� ������� ������~(b).

��������� �������������� ����~(25) ��� ������~$k$ � ���~$c_j$, ������
���������� ������ �~$Q_{jk}/Q_{kk}$, ����� �������, ��� ���������� �������
�������, ������������ ����������~(21), ��������� �� ������, ��� �������
�������� ������ �������. �� ���� ������������� ������� ����������� ����
��������. ��� ��������� ��������� ����� ����� ������ ��������� �����
�������� �������� �� ����� ���������, ������ ����������
����������� ������� ����� �������, ��� ���������. ���������� ����
��������� ��������������~(25) ����� 21~���, ����� � ��������� �~$n=6$ �
� ��������� ���������� ��������� ������~$Q$ �~$R$ ���������� �����
500~������� ��� ������� ��������. � ���������� ������� �� ��� ��������
����� ��������� ������.

%% 118

\section{D.~���������� ������������� �����}. �������� ��������������
���������, ���������� �� ����� ���������� ����.

\alg S.(Ꮕ��������� ����.) Ꮕ��������� ���� ����������� ��� ������ ������
���������~$a$ � �������� ������������ ������������������ � ������������
��������. (������ � ��������������� ����� ����� �� ������ ��������
������������ ������������������ ���������� � ���.~20 �~21.) �����
��������~$a$ �������� ����� ������~$m$. ⅑� ��������� ��������������
������������� ���������������� �������� �� $n$~�����. 瀙� ����� ����
����������� ���~$n=2$, $3$, $4$ � ������ ��� ��������� ������� ���������~$n$.

� ��������� ��������������, ��� �� ����� ������~$a$, $m$ �~$n$;
�����������~$q=\nu_n^2$ (��.~(12)). ������������
$n\times n\hbox{-�������}$~$Q$ �~$R$ � ��������������� $n\hbox{-������}$
�������~$X$ �~$c$. ��� �������� � ������ ������� ������ �������������
�����; ��� ����� ����� ������������� ����������� �������� � ����������
���������. ����� �������� ���� ������ ����� ���������� ����.

\st[��������� ���������.] 㑒�������~$X[1]\asg1$, $X[k+1]\asg (aX[k])\bmod m$
���~$1\le k < n$. ���� �����-����~$X[k]$ ������~$m/2$,
����������~$X[k]\asg X[k]-m$. ����� ������������ �������
$$
\eqalign{
Q&=\pmatrix{
   m^2  &  -m X_2 & -m X_3  & \ldots & -m X_n  \cr
 -m X_2 & 1+X_2^2 & X_2 X_3 & \ldots & X_2 X_n \cr
 -m X_3 & X_2 X_3 & 1+X_3^2 & \ldots & X_3 X_n \cr
 \vdots &         &         &        & \vdots  \cr
 -m X_n & X_2 X_n & X_3 X_n & \ldots & 1+X_n^2 \cr
},\cr
R&=\pmatrix{
 \sum X_j^2 & m X_2 & m X_3 & \ldots & m X_n  \cr
      m X_2 & m^2   & 0     & \ldots & 0      \cr
      m X_3 & 0     & m^2   & \ldots & 0      \cr
     \vdots &       &       &        & \vdots \cr
       mX_n & 0     & 0     & \ldots & m^2    \cr
}.\cr
}
\eqno(29)
$$
��� ����� ����������~$Q[1, 1]\asg m^2$, $R[1, 1]\asg \sum_{1\le j \le n} X[j]^2$;
���~$1<j\le n$ ����������~$Q[1,j]\asg Q[j,1]\asg -mX[j]$, $R[1,j]\asg R[j,1]\asg mX[j]$,
$Q[j, j]\asg 1+X[j]^2$, $R[j,j]\asg m^2$; � ���~$1<j<k\le n$
����������~$Q[j, k]\asg Q[k, j]\asg X[j]X[k]$, $R[j,k]\asg R[k,j]\asg 0$.
(풎 �� ����� �������~$Q$ �~$R$, ������� ���������� �~(19), ��
����������� ����, ���~$R=m^2Q^{-1}$, � ��~$Q^{-1}$, ��� ��� ���
����������� ���������� ������������ � ������ �������.)

����� ��������~$k\asg n$ �~$q\asg m^2$.

\st[����� �������~$Q_{jj}$.] ���~$1\le j \le n$, ����~$Q[j, j]<q$,
 ����������~$q\asg Q[j, j]$.

%% 119

\st[���������� � ��������?] ���~$1\le j \le n$ ����������~$c[j]\asg \floor{\sqrt{qR[j,j]}/m}$.
���� ������~$\prod_{1\le j \le n} (2c[j]+1)\le 1000$,
������� � ����~\stp{6}. (ᎃ����� �����~A, ��� ������������
�������~$X[1]$,~\dots, $X[n]$ ��� �����~$j$  ����������� �������---$c[j]\le X[j]\le c[j]$.
ጛ�� ������� ���� � ���, ����� ������� ��~\stp{6}, ����
��� ������ ������� �������� ��������� ��������� �� �����~$1000$,---� ��
����� ����, ��� ����� �������� ����,--- ����� $500$~�������. �������, ���
������������� ��������� ������ ��������~$\prod (2c_j+1)$; ��� ����, ������,
�������� ������������. ���������� ���������, ��������� �� ��� ��������~$1000$.)

\st[�������������.] ���~$1\le j \le n$, $j\ne k$, ���������~$c[j]$
����� ��������, ��� ����� ����� ������� �~$Q[j,k]/Q[k,k]$,
��������~$\floor{Q[j,k]/Q[k,k]+{1\over2}}$ (��.~(27)). ����� ���~$1\le j \le n$,
$j\ne k$ �~$c[j]\ne 0$ ��������� ��������~$|TRANS|(Q, j, k,-c[j])$ �~$|TRANS|(R, k, j, c[j])$.

��������~$|TRANS|(P, i, j, t)$ ��� ��������~$P$ ������������ ���������
�������. ���~$1\le r \le n$ ����������~$P[i,r]\asg P[i,r]+tP[j,r]$;
\emph{�����} ���~$1\le r \le n$ ����������~$P[r,i]\asg R[r,i]+tP[r, j]$.
[ �� �������, ������~$j$ ���������� ��~$t$ � ������������ � ������~$i$,
����� �������~$j$ ���������� ��~$t$ � ������������ � �������~$i$. �
���������� �� ����~\stp{4} ������������ ��������������~(24) �
�������������� �������~$U$ ����~(25).]

\st[��������~$k$.] ㌅������~$k$ ��~$1$; �����, ����~$k=0$,
����������~$k\asg n$. ������� ��~\stp{2}.

\st[���������� � ��������.] (⅏��� ����� ������������ ����������
������� � ������� ������� ��������.) 㑒�������~$k\asg n$ �~$X[j]\asg 0$
���~$1\le j \le n$.

\st[������� � ���������� ��������~$X[k]$.] 㑒�������~$X[k]\asg X[k]+1$.
����~$X[k]>c[k]$, ������� ��~\stp{9}.

\st[������� � ����������~$k$.] 㑒�������~$k\asg k+1$. ����~$k\le n$,
����������~$X[k]\asg -c[k]$ � ��������� ���~\stp{8}. ����~$k>n$,
����������~$q'\asg \sum_{1\le i \le n} \sum_{1\le j \le n} X[i]X[j]Q[i,j]$,
�, ����~$q'<q$, ����������~$q\asg q'$.

\st[㌅������~$k$.] 㑒�������~$k\asg k-1$. ����~$k\ge 1$,
��������� ��~\stp{7}, � ��������� ������ ���������� ���������
�������������. (���������: ����~\stp{6}--\stp{9} ��������
���������� ������� ������ ��������� ��������, ������� �������� ������ � ��.~7.)
\algend

������������ � ������� ����� ��������� ��������~$q$ ���������
���������~$\nu_n=\sqrt{q}$ � ����������~$C_n$ �� �������~(15). ��������
%%120
�������~$\nu_n$ �~$C_n$ � �������, ��� ���������� ������� �����
�������, ��� ���������~$a$ ������ ��������� �����������������,
����������� ���� � ���������~�.

  ��� ������~$m$---��� ������ ����� ������, �� ������� ������������
���������� ���������~S, ���������� ��� �������� �� ����� ���������
������������ ����������� ��� ������ ������� � ����������� ���������.
���� ����������, ��� ���������� ������� �������� (����� ������ ����� �����
����������� � ���� �������). ��������, ��� ���������� ����.~1 �����
����������� 76-��������� ����������. 풎�� ���� ���������� ���~$m=10^{10}$
�~$n\ge 6$, ������ ���~$m=2^{35}$ �� ������ �������
����������� ������������. ��-��������, ����� ��� ���� ���������
�~$m=2^{35}$ ����� ���������� �������� 90~�������� ��������.
�����-���� ������������� ������ ������������ ��������
������������� ����������� ���� �� ����������.

�� �������� ��������~S ����������� ����������� �����������;
���~$m=2^{35}$ ����� ���������� �����~S2--S5 ����������� ������~$6$, $10$,
$14$, $17$, $21$ ���~$n=2$, $3$, $4$, $5$, $6$. ������ �� ��� ��� ���
������, ��������� ����������� ��������, � �� ����� ���� � ���������
������� \emph{����� ����� ������ �����������.}   ��� ������ "��������" �
������ ������, ������ ������, ����������. ����� �������� ��� ��������� ���,
����� ����� �������� ���� ���������� (��.~���.~16). ���������� ������
��� ���� ����������~$d$ � �������������~$d\asg 0$ �� ����~S1 � �
��������~|TRANS|. ����� ����, � ����� ����~S3 ��������: "$d\asg d+1$;
����~$d>n$, ������� ��~S6". ������, ��������, ��� ��� �������� � �����
�������� �������� �� �����~S6--S9, ��� �������� � ���.~18. � �����
�������� ������������� �������������� �������� ������, ������� �����������
� ���.~22 �~23. �������� ������������� ���~$n=2$, $a=1025$, $m=2^{46}$,
���� �������� ������� ������ �����.

� ����� �� ������������ ������� ������� ���~$n=6$ "��������� �����
��������"~$\prod (2c_j+1)$ �� ����~S3 ��������� ���������������
��������� ��������:
$$
\eqalign{
 &1\times 10^{43}, 6\times 10^{42}, 2\times 10^{42}, 9\times 10^{41},
   2\times 10^{41}, 6\times 10^{33}, 4\times 10^{33},\cr
 &1\times 10^{29}, 1\times 10^{20}, 6\times 10^{19}, 4\times 10^{18},
   9\times 10^{12}, 4\times 10^{10}, 3\times 10^{8},\cr
 &1\times 10^8, 8\times 10^7, 1\times 10^7, 7\times 10^6, 1.7\times 10^7,
   1.8\times 10^7, 7\times 10^5,\cr
 &1\times 10^5, 5\times 10^4, 3825, 3825, 675.\cr
}
$$

 �� �������, ��� �������� ����������� ��~$10^{43}$ �� ��������
����~$1000$, ������ �� ���������: ������ �������� \emph{�������������.}
��������, ���������� �������� ��� ������ ������ ��������~$675$, ��� ���,
��-��������, ���������~$1000$ � ����~S3 ������� ���������, ������,
��~$100$. (\emph{���������.} �������� ����� �������~$X[1]$,~\dots, $X[n]$,
���������� � ������ �������� (����
%%121
\bye
