4.1. ������� �������� � �� �������
��������, ����������� � ������� ��������� � ����� ������, ���������� �������������� �� ������ �������� (VI �. �� �.�.). ����� ��������, ��� ��������� ��������� ������ �� ����� ������� � ����� ������ (��������, 2x+2y=1, ��������� ��� ����� ����� x,y ����� ����� �������� ������ ������). ������ ����� �������� ����� ������� (��������, x2+y2=2 �������� � x2=1, y2=1, �.�. ���������� ������ �������). �������, ������ ���������, ������� ���������� ����� ������� � ����� ������. � �������� ������� ���������� ��������� 3x-7y=1. ����� ������������ x, ��������
x = (7y+1)/3 = 2y + (y+1)/3.
����� (y+1)/3 ������ ���� �����, ��������� ��� ����� t, ����� y=3t-1, x=2y+t=7t-2. ����� �� t �� �� �����, ���������� ����� ������� ���������.
�� ����� ��������� ����������, ����� �� ������ ��������� ������� � ����� ������, � ���� ����� - �� ������� ��? ������ ��� ������ ����� �� ���� ������, ������� �������� ����� ���������, � ������� ���� ����. ������� � ���� ��������� ���� P=Q, ��� P, Q - ���������, ������������ �� �������� ����������� (�� ����� ���� ����, ���, ��� � ������), �� ����� ����� � �������� ��������, ��������� � ���������. ��������� ������ ���� (��� �������, ��� ��� ���������� ������ ����� �������) ������� �������� ������������ ����������� (� ����� ��������, ������� � III �. �.�. ��������� ��������, ����������� � ����� ����������). ������ ����������� ������, ���� ���� � ������� � ����� ������ ��������� ���� P=0, ��� P - ������� (�� ����� ��� ���������� ����������) � ������ ��������������.
��������� ������ ������� ������ ��������� ������ ������� � ����� ������������ ��� �������� ��� � ������� ����. ����� ���� ��������� ax+by=c. ���� ���������� ����� �������� ����� a, b �� �������� ��������� ����� c, �� ��������� �� ����� ����� �������. ���� �������� - ����� ��� ������� ��������� �� ���� ����� �������� � �������� ��������� ����� �������� ������������� (��� ����, ��� ������� ��������� 3x-7y=1). ����� �������� ����� ����� �������� � �������� ���� x=dt+e, y=gt+h, ������� ��� ����� t ���� ������� ��������� ��������� ax+by=c (������� � ���� ������ ���������� ���������� �����, ��������� ������ d, g<>0).
�����, ����� ����� ������� ����������� ��������� ������ ������� � ����� ������������ ��� ������ �.��������� � XVIII �.
� ���������, ��� ����� ��� �������-������ ����� ���������� �������������� ���������. ��������� ������������ ������ ��������� ������, �� ������� �������, ���������� � ���������� �������, ��������� ������� � �.�. ������ ����������� ����� (� �� � ������ � ���������� ���������). ��� ����������� ���� �������� ����� ��������������� �������� � ����������� ����������� ����������� (�������� �� �������������� �������� ���������� � �����)?
� ������� 1900 �. � ������ ��������� II ������������� �������� �����������. 8 ������� �.�������� �������� �� ��� ������ "�������������� ��������". ����� 23 �������, ������� ������� (�� ������ �.���������) ���������� ���������� ���� �������� � ����������� XX �., ������� �������� �� ��������� ��������� ������� (��. �.�������� [1900]):
"����� ������ ���������� ��������� � ������������ ������ ����������� � ������ ������������� ��������� ��������������. ������� ������, ��� ������ �������� �������� ����� ��������� ����� �������� ����������, ��������� �� ��� ��������� � ����� ������������ ������".
���� ������������ ����������, ��� �����, � 1900 �., � ��������������� ����� ���� �������� ������ � ������������� ������� ������� �������� ��������� - �� "�������� �������". ��� ��� ����� ��������� ������������ ��������� ������ "������ �������" ����� ������������� - ����� � ����� ����������� � 1900 �. ������ �� ��������� � ������. ���� � 30-� ��. ���������� ������������� ������ ������� ��������� ("�������, ������� ����� ��������� ����� �������� ���� �����", ��. ������ 3.3). ���� ����� ���� ��������� "��������" �� ��� ��������� � �������������� ���������, ������ ���� �������� �������� � �������������� ������������� ������ "�������" ��� ������� ������-���� ���� �����.
� ����� 40-� ��. ���� � ������������ ������������� ������� ������� ��������� ����������� ��� ���������, ��� ����� ���� �������� ������� ������ �� ������������� ������� ������� �������� ��������� (� ������ ������������ �������, ���������� ������������� ����������). �.�. ����� ���� �������� � ������� �������������� ������������� ���������, ������� �� ������� ���������� ��������� ��������� ��, ����� �� ��� ������� � ����� ������ ��� ���. ��������, ��� ������� �������� ��������� �������������� �����������, ������ �������� (� ����������� �� �� ����������) ������������ ��������� �.����� � 1949 �. �������������� ���� �������� ����������� �� 20 ��� - ��������� ��� ��� ������ ������ � 1970 �.
�.����� ������� ��������� ���� �������������� ����� ��������. ������� �� ������� �� ������� ��������� � ����� ������ � ������� � ����������� ������ (�������, ����� ��������� ��� ������ ����������).
���������� 4.1. ��������, ��� ��������, ������������ ������������ ����������� ��������� � ����� ������, ����������, ���� � ������ ���� ���������� ��������, ������������ �� ������������ � ����������� ������. (� ����� ������������ ������ ������������ ��� ����, ��� ������� x2+y2+z2+t2 ��� ������������ ����� ��������� x, y, z, t ��������� � �������� �������� ��� ����������� �����. ��� ��������� ������� �������� � ���, ��� ������ ����������� ����� ����������� � ���� ����� ������� ���������, ��. ��������, �.�.������� [1966]. )
����, �.����� ��������� ���������� ������������� ���������, ������������� ������������ ����������� ��������� � ����������� ������. ����� �� �������?
���������� 4.2. ����� P(a, x1, ..., xn)=0 - ���������� ���������, ���������� �������� a. ���������, ��� ��������� S ��� �������� a, ��� ������� ��������� ��������� � ����������� ������, �������� ���������� ������������.
���� �� ������� ��������� ��������� (� ���������� a) �����, ��� ��������� S ��������� �� ������������, �� ���� ���� �� ����������. ���������� ������ ��������, ��� S ����� ���� ������������ (������ ���������� ������������), - ��������, ��� � �������� S, ��� ���������� ������ ���������, ����� ��������� ������������ ���������� ������������ ��������� (��� ��������, ����� ���������� ������������ �������� ���������� ������������).
������ �� ����� �����������, �.����� ���� ������� ����������� �������������. ����� R(a1, ..., am) - �������� ��� ����������� �����. �������
(Ex1)...(Exn) P(a1, ..., am, x1, ..., xn)=0,
��� P - ������� � ������ ��������������, ����� �������� ����������� �������������� ��������� R, ���� ��� ������� ������� ��� ��� � ������ ��� ������� (a1, ... am), ��� ������� �������� �������� �������� R. ��������, �������� "a - ������ �����" ����� ��������� ���������� �������������:
(Ex) a-2x=0.
����� �������, ���������� ������������� ��������� R - ��� ���������� ��������� � ����������� (a1, .., am ), ������� ��������� (� ����������� ������), ���� � ������ ���� R(a1, ..., am) �������.
����, ��� ������ ��������, ���������� ����������� ��������������, ���������� ���������� (���������� 4.2). �.����� �����������, ��� ��� ������� ���������� ������������� ��������� ���������� ���������� �������������. ���� ��� ���, �� ������ �������� ��������������� �������������� ������� �������� ���������. ������� ���������� ������������ ������������ ��������� S, �������� ���������� ������������� a in S:
(Ex1)...(Exn)P(a, x1, ..., xn) = 0.
����� ���������� ��������, ������������ �� ����� a, ��������� �� ��������� P(a, x1, ..., xn)=0 � ����������� ������ (��� � �����������).
� 1949 �. �.������ ������� ������� ������ ������ ��� � ���������� �����������: �� �������, ��� ������ ���������� ������������ �������� R(a1, ..., am) ����� ����������� � ����
(Ey)(Az<=y)(Ex1)...(Exn) P(a1, ..., am, y, z, x1, ..., xn) = 0.
���������� �� �������� Az<=y �.������ ����� �� �������.
��������� ����� ��� ��������� � 1960 �.: �.����� ��������� � �.�������� ��������, ��� ��� ������ ���������� ������������� ��������� R(a1, ..., am) ����� �������� ������������� ����
(Ex1)...(Exn) X(a1, ..., am, x1, ..., xn) = 0,
��� ��������� X �������� �� �������� a1, ..., am, x1, ..., xn � ����������� ����� ����������� �������� ��������, ���������, ��������� � ���������� � ������� (��������, x2y+z - yz + 3 = 0). ������, �������������� ������-������� ��������� ������ (��� ��������������� �� ���������� �� ��� ��� ��������� � ������������� ����������� ������� �������������� ����������, ��������� ������ �� ������� �����). ���������� ���� ������ ������� ��.�������� � 1961 �. ��������� ���� X(a1, ..., am, x1, ..., xn) = 0 ���� ������� ������������-������������ �����������. �� ������� ������-�������-�������� �������� ������������� ���������, �������������, ��������� �� ������ ������������-���������� ��������� � ����������� ������. ��� ��� ������� �����, ������ �� ������ ������ ���������� ��� ����� 10 ���.
����� ����, ���� ����� 1961 �. �� ��� ��� ��������, ��� ���� ������� ���������� ����� ������� �� ����� (�������, ��� ������ ���������� ������������ �������� �������� ����������� ��������������). ���� ����� ��������� "a - ������� �����" � "a - ������� ����� 2" � ����������, ��� ��������� �� ���������� �������������:
"a - ������� �����" <-> (Ex1)...(Exn) P(a, x1, ..., xn) = 0,
"a - ������� ������" <-> (Ey1)...(Eyk) Q(a, y1, ..., yk) = 0,
�� ���������, ��� ��������� P=0 ���������, ���� � ������ ���� a - ������� �����, � ��������� Q=0 - ���� � ������ ���� a ����� ��� 2m. ����� ����������� ������ ������������� ����������� ���������-�������� �������� (�������� ���� ��������, ������� ����� � ���������� ��������� ������ ������� �� ���������, ��� ����� ���� ������� ������ ����� ���������� ������� �����). � ��� �� ����� � 1970 �. ���������� ���������� ���� ������������� ����������� (��. �.�.���������� [1970]) ������� ������� ��������� � �������� ��� - �������� ���������� ������������� ����������:
a=bc <-> (Ex1)...(Exn) P(a, b ,c ,x1, ..., xn) = 0.
� ������� ����� ������������� ����� ��������� �������� ���������� � ������� �� ������������� ������-�������-�������� � ����� ������� �������� ���������� ������������� ��� ������ ���������� ������������� ���������. ��� ����� � 1970 �. ��������������� �������������� ������� �������� ��������� ���� �������� ���������.
��������������� �������������� ��������� ���������� ���� ��������� � �������� ����������� ��������� ������� ��������. ������ ������, �������������, ��������� �� ����� ������ ���������� ���������, �� ����������. ������� ������ ����� ����������� ������������ ��������� ����������� ������� - ���������� ������ � ���������� ������������ ����. ������������ ����� �������������� �������������� ������� ������ ������������ �������������� ������� ��� ���������� � ������ ������� ����������.
� ����������� �������� ���������� �������������� ������������� ����������� ������������� ��� ������ ���������� ������������� ���������.
���������� 4.3. ��������, ��� �������� ������������ ������������� ���������� ��������� ����� ���� ������� � �������� ������������: �) ������� ����������� ��������� 2-� ������� ��� �) ���������� ��������� 4-� �������. ����� �������, �������� ������������ ������ ��������� 2-� ������� � ��������� 4-� ������� ����������� ��� �������������� ������������. �� �������� �������, ��� �� ��� ��� �� ������� �������-������ ����� ������ ������� ����������� ��������� 4-� �������.
4.2. ������ � ���� ��������������
���������� ������������� ��������� �������� �� �������� �������� ������������ ���� � ����� EA (����� ������ � ��������� P=0 ��������� � ������ ������� ����� � �������������� ��������������). ��������, ���, ��������� �������������� � EA ����� ���������� �������, �� ��� �������� ��������� ����������� ������� EA, �������������� ��������� ���� f(a1, ..., am) = b, ��� f - ������������ ���������� �������.
���������� 4.4. ��������� �� ������ ������� 3.3, ��� ��� ������� ���� ���������� � ������� ������ ��������� �������:
�) ������������ ������ ���� s=t, s<t, ��� s, t - ����� EA (�������� � ������ �������������� ��������������),
�) ���������� � ����������,
�) �������� �������������,
�) ������������� �������� �����������, � ������ �������� Ax<=U, ��� U - �������� ������� ���� b1y +b2y2+...+bkyk+c � ������������ �������������� b1, b2, ..., bk, c.
� ����� ������ 1949 �. �.����� ����� ������� �� ��������� ����������. ��������� (� ����� ������ ����� �����) ������������ �������������� ������ �������� ���������� � ��� �������� ��������� � �������������� ��������� �����������. "�����������" ��������� � ��������� ����������� �������� ��, ��� ��� ������� �� ������� ������ ���������� ������������ ���������� (���� R - ���������� ������������ ��������, �� ~R ��� �� ����������� �����, ���������� - � ������ �������� �� R(x,y) � (Ay)R(x,y)). �������, ���������� ����� ��������, � ����� ������ ���������� ��������� � ���������� �������������.
����, �� �������� � ���������� ������������� ��������� R(a1, ..., am). �������� ������ �������� M(R), ������� �������� �� ����� ����� ��� ��������� ������ ����� a1, ..., am, ��������������� ��������� R(a1, ..., am). ����� ��������� ������� ���������:
f(a1, ..., am, t) = 1, ���� ����� t ����� ������ ������ M(R) ����� ����� a1, ..., am �� ����� ��� ���������,
f(a1, ..., am, t) = 0, �����.
�� ������� � �������������� ����� ��������� ������� EA, ������� ������������ ������� f � �������� ������ ��������, ������������� � ��. �)-�) ���������� 4.4. ���� F(a1, ..., am, t ,w) - ��� ������� (w ������������� �������� �������), ��
R(a1, ..., am) <-> (Et) F(a1, ..., am, t, 1).
��� ����� ��������, ��� �������� R ���������� ��������� �������, ����������� ������ � ������� �������, ������������� � �)-�). ������ �� ������ ��������� ��������������� ����� ������� � ���������� �������������. ������ "�������" - � ������������ ������. ������� ���� s=t ��� �������� ����������� �������������� (��� ���������). ������� ���� s<t ����� �������� �������� (Ex)(s+x+1=t), ������� ��� �������� ����������� ��������������. ������ ����� ���������� � ��������� �)-�), � ������� ������� �������� ����� ������� �������.
���������� 4.5. ��������, ��� ���������� � ���������� ���� ����������� ������������� (E)P=0, (E)Q=0 ����� ������������� � ���������� �������������.
����� �������, ���� � ����� �������� ��������������, ������������ � ������������ ������, ����������� ������� &, V, �� �����, ��� �� ��� ������������. ���� ���������� ������ E, �� ����� �������� �� ����� ����� (���� (E)P=0 - ���������� �������������, �� (EE)P=0 - �����). �� ��� ������, ���� ���������� ������� Az<=t ? ����� ��, ��� ���������� �� ���, �� ��� ������� � ���� ���������� �������������
(Az<=t)(Ex1)...(Exn) P(b1, ..., bk, y, x1, ..., xn) = 0 (1)
(��������, ��� t - �������� ������� � ������������ �������������� �� b1, ..., bk). �� ����� �������� (1) ����������� �������������� ����
(Ey1)...(Eys)Q(b1, ..., bk, y, ..., ys) = 0, (2)
�� ��� ��� �������?
�����������, ��� ��� ����� ������� ������: ������������� ������� ���� (1) � ������� ���� (2). ����� �������� �� ������� ���������� ������������� �������� ����������� (������: ���������� A<=). ����� ��� ������, �� ��� ����� ����� �� ����� ������ �������������� ������, ������������ � ������� ������� �)-�), � ���������� �������������, �.�. ������������ ������� ������������� ������������� ��� ����� ���������� ������������ ����������.
����, ������ ������ ���������� A<=. ���� ����� ��������:
1) �������� ����������� �������� ������� ��������� x2-(a2-1)y2=1 (a>1). �����������, ��� ��������� ����� � ����������� ������ ���������� ����� �������. ���� n-� ������� ���������� ����� (xn(a), yn(a)), �� xn(a) � yn(a) ������ ��������������� �� n. ���� � ���������� ��� ������� � ������� ���������.
2) �������� �� ���������� ����������, ��������� ���������� ������������� ���������
R(a, x ,y, n) <-> x=xn(a) & y=yn(a),
�.�. ���������, ������� ��� ������������� a ������� �� x � y ����������������� ����� �� n.
3) ��������� ���������� ������������� ��������� R, �������� ���������� ������������� ����������, �.�. ��������� x=yz & v>=3.
4) �������� ���������� ������������� ��� ����� ��������� � ���������� (�.�. ��� ���������� x=Cyz � x=y!).
5) ��������� ��� ���������� ���������� �������������, ��������� ��������� A<=.
������ 1), 2) ���� ������ �.�.������������, ������ 3), 4) - ��.��������, ������ 5) - ��������� �.�������, �.�������� � ��.��������.
����� ������� ���� ����������� �� ����������� ����������, ������������� ������ ���������. ��������� - ��� ����� ����� ���������, ������ �� ������ ���������, � ��������� � ��������� �� ����������, �������� ������ (�� �������� ��������������� ���������). ��������, ����� 18 �������� � 78 �� ������ 10:
18 = 78 mod 10,
��������� 78=18+6*10. ����� �������� � ����� �� ������ m, ���� � ������ ���� ��� ������� �� m: x = 0 mod m ��������, ��� x=0+k*m ��� ���������� k.
���������� 4.6. �������� ��������� �������� ��������� (����������� ���������� � ���� ��� � �������� �����������):
a = a mod m,
a = b mod m -> b = a mod m,
a = b mod m & b = c mod m -> a = c mod m,
a = b mod m & a1 = b1 mod m -> a+a1 = b+b1 mod m,
a = b mod m & a1 = b1 mod m -> a*a1 = b*b1 mod m,
a*c = b*c mod m -> a = b mod m, ���� c ������� ������ � m,
a*c = b*c m�d (c*m) -> a = b mod m, ���� c ������� ������ � m.
4.3. ������������ ��������� �����
��������� x2-Dy2 =1 (��� D>0) ������ ����������� ���� � ������ ����������� ��������� ������ ������� � ����� ������������. ���� ����������� D �������� ������ ��������� (D=k2), �� ������� ��������� �������� � �������� �������� ���������:
x2 - k2y2 = (x - ky) (x + ky) = 1,
x-ky=1 & x+ky=1 -> x=1 & y=0,
x-ky=-1 & x+ky=-1 -> x=-1 & y=0.
����� �������, ���������� ������ ��� �������.
����������� ����� ��������� ������, ����� D �� �������� ������ ���������. ���������� ���������� � ���� ������ ��������� x2 - Dy2 = 1 ������ ����� ���������� ����� ������� � ����������� ������! ��� ���� ��� �.����� � XVII �., �� ������ ������� �������������� ���� ���� ������ �.��������� (XVIII �.). ���������� ��� ������� ��������� ����� ����������� ��� D=a2-1:
x2 - (a2 - 1)y2 = 1.
��� ��� ������� ����� ������� (���������): x=1 & y=0, x=a & y=1. ��������� ������� (� ����������� ������) ���������� � ������� ���������� ����������� �����������. ������� ��������� (a+sqrt(a2-1))n � �������� ��� �� ������� ������ �������. � ���������� ����� ������ ����� ������ �������, ������ �� ����� ����� ��������� ��������� sqrt(a2-1). ��������, ��� n=2
(a+sqrt(a2-1)) 2 = a2 + 2a sqrt(a2-1) + (a2-1).
����� ������ ����� � ������ �����, ��������
(a+sqrt(a2-1))n = xn(a) + yn(a) sqrt(a2-1),
��� xn(a), yn(a) - ����������� ����� (��������, x2(a)=2a2 -1 & y2(a)=2a). ����������
(a-sqrt(a2-1))n = xn(a) - yn(a) sqrt(a2-1)
(� ���� �� xn, yn - ���������, ��� ��� ������������� ���!). ���������� ��� ��������� ���������, ��������
(a2-a2+1)n = xn2 - (a2-1)yn2 ,
xn2 - (a2-1)yn2 = 1.
����� �������, ��� ����� n>=0 ���� ����� x=xn(a), y=yn(a) �������� �������� ��������� x2 - (a2 -1)y2 = 1. ��� n=0, 1 ���������� ��� ��������� ��� ����������� ������� (1,0), (a,1), ��� n=2 - ����� ������� (2a2-1, 2a).
�� ������ ����������� ����� xn(a), yn(a) ����� �������� ������������ �����������, ����������� ��������� xm+n, ym+n, ���� ��� �������� xm, ym, xn, yn (m, n >= 0):
xm+n(a) = xm(a) xn(a) + ym(a) yn(a)(a2-1),
ym+n(a) = xm(a) yn(a) + ym(a) xn(a).
� ���������, ��� m=1:
xn+1(a) = a xn(a) + (a2-1) yn(a),
yn+1(a) = xn(a) + a yn(a).
���������� 4.7. �������� ��� �����������. �������� �����, ��� xn(a), yn(a) ���������� �� n (�.�. ��� ������������� ���������� ���������� ����� ������� ��������� x2-(a2-1)y2=1).
�����������, ��� ������������������ {(xn, yn) | n>=0} ����������� ��� ������� ������ ���������.
����� 1. ��� a>1
x2-(a2-1)y=1 <-> (En)(x=xn(a) & y=yn(a)).
� � � � � � � � � � � � � �. 1) �����. ��� �� ��� �����.
2) ������. ����� ����� x,y ������������� ���������. ���� x<=1, �� x=1 � y=0, �.�. x=x0(a) � y=y0(a).
����� ������ x>1. ����� y>0. ���� �� ������������ ��������, ��� x=xn(a) & y=yn(a) ��� ���������� n>0, �� x,y ������ ���������� ����� xn-1, yn-1 � ������������ � ���������� ��� ������������� �������������, �.�. ������ ������������ ������� (u,v) ������ ��������� �����, ���
x = au + (a2-1)v,
y = u+av.
����� ��� ������� ������������ u, v, ��������
u = ax - (a2-1)y,
v = -x + ay. (3)
����� �������, u, v - ����� �����.
���������� 4.8. ���������, ��� u2-(a2-1)v2=1 (�.�. ��� (u, v) �������� �������� ���������), � �����, ��� 0<u<x � v>=0.
����, ���� ���� (x, y) �������� �������� ��������� x2-(a2-1)y2=1, �� ����� x, y ���������� �� �������� (3) ����� ������ ������� (u, v) ����� ���������, �����, ��� u<x. ���� �����������, ��� ����� u>1, �� ���� (u, v) ���������� ���������� ����� ������� (u', v') �����, ��� u'<u. "�����" ����� ��������� ������ �������� ����� (������, n) ���, � ����� ����� ����� ���������� ��������, ����� u<=1, �.�. u=x0(a) � v=y0(a) �, ����� �������, x=xn(a) & y=yn(a).
����� 1 ��������.
��� ��� ����� �������, �� ������ ���������� ����� ����������������, ����� ������� �������� ���������? ���������������� �� ��� ������ ���������� ������������� ����������. ����� ����� �������������, ������, ��� ���������
Q(b) <-> (En)b=2n
- ��� ������ ����� ���������� ��������� P(b, z1, ..., zk)=0 � ���������� b, �����, ��� ������� (z1, ..., zk ) ����������, ���� � ������ ���� b �������� �������� ����� 2. ����� �������, ���������� ������� P=0 ������ "���������" �������� b ����� �� ��������� ����������. ��������� ����� ���� ��� ��� ����� ��������.
����� 2. ��� a>1 � n>=0
an <= xn(a) <= (a+sqrt(a2-1))n.
� � � � � � � � � � � � � �.
xn(a) - yn(a)sqrt(a2-1) = (a+sqrt(a2-1))n = an + Cn1 an-1 sqrt(a2-1) + ...,
��� � ����������� ��������.
����� �������, xn(a) ������ �� n �� ��������� ���������� (���� � �� ������� ����� �� ����� �� ��������� ���� (a+a1)n), � ��� ���������� ����� ���������� ������� �� x
(Ey)(x2 - (a2-1) y2 =1).
������ ������� ��������� ����� ��������� ��� ��������� ����� � ������� ���������� ������������� ����������. (��� ����������� ����������� ��.�������� � ��������� ��� � 1952 �.)
�� ���� �.�.�����������, ������ �� ������ �������� ������������ ��������, ������������ ��� �������� ������� ����� xn(a), yn(a).
�������, ����� n �����������, n>0 (��� n=0 �� ����� �� x0(a)=1, � ������ ����������� �� ����������). ����� ������� ������� �� ������� xN(a) �� xn(a), ��� N=0, 1, 2, ... ��� ����� ���������� �� ������ xn(a) ��������� ������������ ����������� ��� xm+n, ym+n (�� ������ xn - ��� ������, ��� �� ����� ������������ ����������, �������� xn ):
xm+n(a) = xm(a) xn(a) + ym(a) yn(a)(a -1) = (a2-1)ymyn,
ym+n(a) = xm(a) yn(a) + ym(a) xn(a) = xmyn.
���������� m+n ������ m, ��������
xm+2n = (a2-1)ym+n yn = (a2-1)xmyn2,
ym+2n = xm+nyn = (a2-1)ymyn2 .
������� ������, ��� xn2-(a2-1)yn2 =1, �.�. �� ������ xn
(a2-1)yn 2 = x n 2 - 1 = -1.
���������� ������ (a2-1)yn ����� -1, ��������
xm+2n = - xm, (4)
ym+2n = - ym.
���������� ����� m+2n ������ m, �����
xm+4n = - xm+2n = xm,
ym+4n = - ym+2n = ym.
����� �������, ������� �� ������� x (a) �� x (a) �������� �� N � �������� 4n. ������� ���������� ������� ��������� �������� ��� N=0, 1, 2, ..., 4n-1.
�������� (4)
x0 = x0, x1 = x1, ..., x2n-1 = x2n-1,
x2n = - x0, x2n+1 = - x1, ..., x4n-1 = - x2n-1.
���������� ��� yN(a). ����, ������, ��� �� �������� �� �����, ��������� ����� xn+1 , ..., x2n-1, ����������� � �������������� ��������, ��� ��� ������ �������� xn. ����� ������� ���� �� �����, ���������� �����������, ���������� x2n, y2n ����� x2n-m, y2n-m, xm, ym :
x2n = x2n-m xm + (a2-1)y2n-m ym,
y2n = x2n-m ym + y2n-m xm.
����� ��� ������� ������������ x2n-m, y2n-m, ��������
x2n-m = x2n xm - (a2-1)y2n ym,
y2n-m = y2n x-m - x2n ym.
��������, ��� x2n = - x0 = -1, y2n = - y0 = 0 (�� ������ xn), �����
x2n--m = - xm,
y2n-m = y2m.
������ ���� �������������� �������� �� ������� xN(a) �� xn(a) (������ ������� 4n) ����� ������� �� �����:
x 0 = x 0, x 1 = x 1, ..., x n-1 = x n-1,
xn = - xn, xn+1 = - xn-1, ..., x2n-1 = - x1,
x2n = - x0, x2n+1 = - x1, ..., x3n-1 = - xn-1,
x3n = xn, x3n+1 = xn-1, ..., x4n-1 = x1.
����, ��� ������ xn � -xn ����� ����� ���� �������� ������ ����, �� ��� �������� �� ���������.)
���� ����� ��������������, ����� �������� ��������� ����� �.�.�����������.
����� 3. ����� a>=3, n>=1, 0<m<n. ����� ��� ���� N
xN(a) = xm(a) mod xn(a) <-> (N = +m mod 4n)V(N = -m mod 4n).
� � � � � � � � � � � � � �. 1) �����. ���� N=4kn+m ��� N=4kn-m, �� xN=xm mod xn �������� ��������������� �� ���������� ���� ��������������.
2) ������. ����� ��������, ��� xN=xm mod xn, ��� 0<m<n. �������� ����� N �� 4n � ������ �������: N=4kn+m', ��� 0<=m'<4n. ���� 0<m'<n, �� �� ����� �������������� �������, ��� m'=m � N=4kn+m, ��� � �����������. ���� 3n<m', �� �� �������������� �������, ��� m'=4n-m � N=4(k+1)n-m.
���������� 4.9. ��������, ��� ������ ������ m'=0 ��� n<=m'<=3n ���������� (������, ��� ��� a>2: i<n -> xi(a) < xn(a)/2).
����� 3 ��������.
������ �� ������ �������� ����������� ������������ �������� �� ������� yN(a) �� yn(a) (n>=1 �����������, N=0, 1, 2, ...).
���������� 4.10. ��������� ��� ������������ ��������������. ������ ��������� ������ � 2n, � ������ ������� ������� ����� ����� ���� ����� �������:
y0 = y0, y1 = y1, ..., yn-1 = yn-1,
yn = - yn, yn+1 = - yn-1, ..., y2n-1 = - y1.
�� ����� ����� ��� ���������� ������ �������, ��� ������� yN(a) ������� �� yn(a) (��� ���� ����� �.�.�����������):
����� 4. ����� a>=2, n>=1. ����� yN(a) ������� �� yn(a), ��� � ������ ���� N ������� �� n.
� � � � � � � � � � � � � � �������� ��������������� �� ���������� ��������������.
��� ���� ������ ����� �.�.����������� ���� �������, ��� ������� yN(a) ������� �� ������ �� yn(a), �� � �� yn2(a).
����� 5. ����� a>=2. ����� yN(a) ������� �� yn(a), ���� � ������ ���� N ������� �� nyn(a).
� � � � � � � � � � � � � �. ����� ��������� (��������� �� k), ��� �� ������ yn2
xkn = xnk,
ykn = kxnk-1yn.
1) ���������� ������. ���� yN ������� �� yn2 , �� �� ����� 4: N = kn. ���� ykn ������� �� yn2 , �� ����� kxnk-1yn ����� ������ �������� �� yn2 , �.�. kxnk-1 ������ �������� �� yN. ��������� xn2-(a2-1)yn2 =1, �� xn �� ����� ����� ����� ��������� � yn, ������� �� yn ������ �������� ���� ����� k. ��� ��� N=kn, �� ������ nyn ����� N, ��� � �����������.
2) �����. ���� nyn ����� N, �� N=kn, ��� yn ����� k. ������� yn2 ����� kxnk-1yn, �.�. yn2 ����� � ykn = yN , ��� � �����������.
����� 5 ��������.
� ���������� ��� ����������� ��� ��� �����. ������ �� ��� ����������� ��.��������, ��������� ��� ����������.
����� 6. ��� a>=2 � n>=0
xn(a) = 1 mod(a-1),
yn(a) = n mod(a-1).
����� 7. ��� a,a'>=2 � b>=1, ���� a = a' mod b, ��� ���� n:
xn(a) <-> xn(a') mod b,
yn(a) <-> yn(a') mod b.
����� 8. ��� a>=2 � k>=0 �� ������ 2
x2k = 1, x2k+1 = a, y2k = 0, y2k = 1.
���������� 4.11. �������� ��� ����� � ������� ��������.
4.4. ���������� ������������� ������������������ ������� ��������� �����
������ �� ������ ��������� ���������� ������������� ��� ���������
Q(a, x, y, n) <-> a>=3 & x=xn(a) & y=yn(a).
����� "���������� �������" ������� �������� �� ����� x, y, ����� "���������" �� ��������� xn(a) � yn(a)? ������ �����, ����������, �������
E1: x2 - (a2-1) y2 = 1.
������ �������, ��� ���������� ni �����, ��� x=xni(a) � y=yni(a). ���� �������� ni �� ���� �� �����. �� ����� ������� ������� �������� �� x, y, ����� ���������, ��� ni=n? �� ����� 6 �� �����, ��� y = n mod(a-1), ������� ����� ���� �� ����������� y =n mod(a-1), ����� ������ ��������� �� ni = n mod(a-1). � ���������, ���� n>=a-1, �� ������ ��� ������ ����� �������, ��� ni=n.
����� ������ ��� ���������, ���������� ���� � ����� � ����� ������ ������. ������ ����� ��������� ����� �� ��������� ���������� a' � ��������� ��������� ��� ������� ����� (x', y'):
E2: x'2 - (a'2-1) y'2 = 1.
� ������ ��������� �� y = n mod(a-1), �
E3: y' = n mod(a'-1)
(� �������, ��� a'-1 ����� ����� ������� ������ n). ��������� ��� ���������� mi ����� ����� x' = xmi(a') & y' = ymi(a'), �� �� ����� 6 y' = mi mod(a'-1) � �������
mi = n mod(a'-1). (1)
�� ��� ��� �� "���� � �������" �� ��������� ���������, �� ������ ������ ������� �� �����, ���� �� �� ������ ����� "�������� ����" - ����� ���������� ������� ������� ������� (x', y') � ������������ ��� �������� (x, y). ������ ��� ����� ����� ������ ���������, ��������� ��� ����� X � ���������, ����� ����������� �������
E4: a' = a mod X & x' = x mod X.
����� ����� ����� a', x' �� ����� "������� ������ ����������" �� ������ a, x, ������, ������� X, �� ����� ��������� �������� ����������� ������ �����. ������ �� ����� 7 a' = a mod X ����
x = xni(a) = xni(a') mod X,
x' = xmi(a') = xmi(a) mod X.
�� ������� x' = x mod X* ������ ����������
xmi(a) = xni(a) mod X. (2)
����� ������� ������� ��� ���������� ����� 3 (��� ����� ���� �������������), ������ X ������� ������� �������� ��������� ����� � ���������� a. ������ ������� ��� ���� ����� Y � �������
E4: X2 - (a2-1) Y2 = 1.
������ X=xN(a) � Y=yN(a) ��� ���������� N � (2) ��������� ���
xmi(a) = xni(a) mod xN(a).
��� a>=3 ����� ����� ���� �� ��������� ����� 3, ������ ���� ���������� ��� 0<ni<N, ������� ������ �������
E6: 0<x<X
(��������� 0<xni(a)=x<X=xN(a) � xi(a) ���������� �� i). �������, �� ����� 3
mi = +-ni mod 4N. (3)
������� ��� � (1):
mi = n mod(a'-1).
���� �������� ���� - ���������� ni=n, �.�. ��� ��������� ��������� ����� "������ ������" � ������ ������. ��� ����� ����� ����� ���������� ������� ����� �������� ����� 4N � a'-1. ������ a'-1 �� ����� ������������� ������������ ��������, �� ��� �������� �������� ����� N, ������� ���� ��� ����������? ����� ������ ��������� ����� 5: yni2(a) ����� yN(a), ���� � ������ ���� ni*yni(a) ����� N. ������: y2 ����� Y, ���� � ������ ���� ni*y ����� N. �������, ���� �� ���������
E7: y ����� Y,
�� 4y ����� ��������� 4N (�� �������� ����������� ����� ni, ������� �� ������ �� ������� ��������� ������ a'-1). ������ ����� ����������� ���
E8: 4y ����� a'-1
(����� ���������, ��� ��� ���������� �� ����� ������������� ��������� ��������, ���������� �� a'). ����� (1) ������ � (3) ����
mi = +-ni mod 4y & mi = n mod 4y
� ������
n = +-ni mod 4y.
������� �������, n+ni ��� n-ni ������� �� 4y. ��������� y=yni(a) ���������� �� ni, �� y>=ni, ������� �� ����� ����� ����������� �����
E9: n<=y
(��������, ��� �� ���������� ��������� ni=n, �.�. ���������� "��������" n ����������, ��������� ni). ���������� ������ �������� ��� ���������� �����������:
1) n+ni ������� �� 4y. ��������� n+ni<=2y, �� ��� �������� ������ ��� n=ni=0, ��� � �����������.
2) n-ni ������� �� 4y. ��������� |n-ni|<=y, �� ��� �������� ������ ��� n=ni, ��� � �����������.
��������, ��� x=xni(a) � y=yni(a), �� ����� ���������� ������, ��� �� �������
a>=3 & E a'x'y'XY (E1&E2&E3&E4&E5&E6&E7&E8&E9) (4)
��������, ��� x=xn(a) � y=yn(a), �.�. Q(a, x, y, n).
���������� 4.12. ��������, ��� (4) ����� ������������� � ���������� ������������� ���� (E)P=0. ������� ����� ��������� E, ������� �������� P � ����� ������� ��� �������������.
������� ����� ������ ����� ��������� ����, ���� ������� ��������, ��� �� Q(a, x, y, n) , �.�. �� a>=3 & x=xn(a) & y=yn(a) ����� ������� ������� (4). (� ���������, ������ ����� � ����� ����������� �������� ������������������ ���������� Ei.)
����, ����, ��� �>=3 & x=xn(a) & y=yn(a), �� ������ ����� ����� a', x' ,y' ,X, Y �����, ��� ����� ����� Ei ��� ���� i=1, 2, ..., 9. ������� �����, ��� ���������� E1 ��� ���������� ������ 1, � ���������� E9 - ��� ���������������, ��� yn(a)>=n ��� ���� n.
����� X, Y (������� ���� �� ���������, ��� x, y) ��������� ��������� �������: ����� N - ����� �����, ��������� �� nyn(a)=ny; ������� X=xN(a) � Y=yN(a). ���� ����� ���������� ������� E5, � �� ����� 5 ����� y ����� Y, ��� ������������ E7.
�������� ������� ����� a', ������������ ��������������� ���������, � ��� ������� x', y'. ��� ���� �� ������ ��������� ��������� �������:
E2: x'2 - (a'2-1) y'2 = 1,
E3: y' = n mod(a'-1),
E4: a' = a mod X & x' = x mod X,
E8: a' = 1 mod 4y.
������ n=0 (����� x=1, y=0) ����� ���������� ��������� ��������. ����� E8 ������� a'=1, ����� E3 ������� y'=0, E2 - x'=1, �������, E4 ������� a = 1 mod X. ������ ��������� ���������� ������ "�������� ��������", ��, � �������, ��-�� y=0 �� ��������� ���� ������� N=0, ������� X=1!
����� ������ n>0. ����� y>0. �������������� E4 � E7 , ������� ������ a'. ���� �� ������ X, 4y ��������� ������� ��������, ������������� ����� a' �������� �� �� ��������� ������� �� �������� (��. ������ 3.3). ��������, ��� X � 4y ������������� ������� ������. ��-������, X ������ ���� �������� ������. ����� ����� ��������, ���� ����� ����� N ������ (����� 8). (��������, ��� �� ��� ��� �� ��������� �� N ���� ��������� �� ny.) ��-������, y � X �� ����� ����� ���������, ��������� y2 ����� Y, � X2-(a2-1)Y2=1. ����� �������, ������������� ����� a', ���������������� �������� E4 � E8, ���������� (������, ��������, ����� ������� a'>1).
�������� ���������� x', y'. ������� x'=xn(a') � y'=yn(a'), ����� ������������� ����������� E2, � �� ����� 6 - � E3. �������, ��� ��� x=xn(a) � a'=a mod X, �� �� ����� x'=x mod X, �.�. ���������� ������ �������� ������� E4.
��� ���, ��� �����������: �� Q(a, x, y, n) �� ������ (4).