4.5. ���������� ������������� ����������

������������� ������ ���������� � ���������� ������� ����������� �������������� ��������� Q(a, x, y, n) ��� ���������� ���������� ������������� ����������, �.�. ��������� n

E(u, v, n) <-> u=vn & v>=3.

����� ��������� ������������ ��.��������, ����������� ��� � 1952 �. (��� ���������� �����, ��� �������� u=vn "���������� �������" ����� �������� Q, ��, ����������, �� ����� ���������� ������������� ��� Q, ����������� �.�.������������ 18 ��� ������).

������� ���� ���������������� ���������

(a+sqrt(a2-1))n = xn(a)+yn(a)sqrt(a2 -1)

� ��������� v=a+sqrt(a2-1). ����� ����� ����� ����� ������ vn , � ������ ������ sqrt(a2-1 ����� ���������� v-a. ����� �������, ���������

vn - xn(a) - yn(a) (v - a) = 0

����� ������ v1=a+sqrt(a2-1). ��������� ������������ ��������� �����������, �� ����� v2=a-sqrt(a2-1) ����� ������ ���� ��� ������. � ������ �������, v1, v2 - ����� ����������� ���������

v2 - 2av + 1 = 0.

��� ������, ��� �������� v2-2av+1 �������� ��������� �������� vn-xn(a)-yn(a)(v-a) � ���� ������������ �����. ����� ����, ������� �� ����� ������� ������ ���� ��������� � ������ �������������� (������� ����������� �������� ����� 1). ������ n�������, ��� ���� v - ����� �����, �� vn-xn(a)-yn(a)(v-a) ������� �� v2-2av+1. � ���� � ������� ����������� ��������� ����� ��.��������:

����� 9. ��� a>=1 � n>=0

vn = xn(a)+yn(a)(v - a) mod(v2-2av+1).

���������� 4.13. �) ���������, ��� ����� 9 ������������� ����������� � ��� n=0, 1 (���� ����������� �������� ������ ��� n>=2).

�) ���������, ��� �� ����� ����

vn - xn(a) - yn(a)(v - a) = (v2-2av+1)(y1vn-2 + y2vn-3 + ... + yn-2v + yn-1).

(��� ����� �� �������� ����� ��������������� ����� 9, ��� ��� ������������� ������� ���������.)

�������� ����� 9 ������� � ���, ��� ��� ��������� ������������ ������� v � ������ ���������� ������� xn(a), yn(a), ������ ����� ��� ����������� ����������� ��������� ������������� ������� (v-a, v2-2av+1). ������ ����� ���������� ���������� ������������� ��� u=vn.

� ����� ����, �� ������ �������� �� ������������ u, v, n, �, ���������� �� ��� ���������� �������, �������� ���������� n��������� u=vn. ������� ������� ����� a, x, y � �������� �� �������

F1: Q(a, x, y, n),

�.�. x=xn(a) & y=yn(a). ����� �� ����� 9

vn = x+y(v-a) mod(v2-2av+1).

����� ���-�� "���������" ����� u � ����� v , ���������

F2: u = x+y(v-a) mod(v2-2av+1).

�����

u = vn mod(v2-2av+1).

����� ������ ����� ���� ���������, ��� u=vn, ���� ���������� ����������� �������� ������ - �� ������ ���� ������ ��� u, ��� � vn. ����� ����� ��������, ���������� ��������� �������� a - ����� ������ ����� ����� (�� ����������� ��������). � ���������, �������

F3: u < 2av-v2-1

������������ �������� ����������. �� ��� (� ������� ����������� �������) �������� ����������� vn<2av-v2-1? ����� �� ��� �� ��������� � ������������ ����� ��������� u=vn? �����, ��������� � ������� ����������� ������� �� ����� "���������" �������� ����� �� ��������� ����������, �� �� ����� ���� "���������" �� � �������� ��������� ����������. � ����� ����, �� ����� 2 �� �����, ��� xn(v)>=vn, � ���������� ������� xn(v)<2av-v2-1 ����� �����. ������ ����� X, Y �����, ���

F4: Q(v, X, Y, n),

�.�. X=xn(v) & Y=yn(v), � �������, ����� ����� a ���� ��������� ������, ����� ����� �����

F5: X < 2av -v2 - 1.

������ �������

vn < xn(v) = X < 2av-v2-1,

��� ��������� � F3 � (1) ������ u=vn.

����� �������, �� ������ ������� u=vn �� �������

E axyXY (F1&F2&F3&F4&F5). (2)

������������ �� ���������� ����� ����������� v>=3 (��� ���������� � F4), �.�. �� (2) �������� ���������� ��������� E(u, v, n).

���������� 4.14. �) ��������, ��� ������������� (2) � ���������� ������������� ���� (E)P=0. ������� ����� ��������� E, ������� �������� P � ����� ������� ��� �������������.

�) ����� ��������� ��������������, ��������, ��� (2) �������� �� E(u, v, n), �.�. u=vn & v>=3.

����, ������ ������� �.�.����������� � ��.��������, �� �������� ��� ��������� u=vn & v>=3 ���������� ������������� ����

(Ez1...Ezk) P(u, v, n, z1, ..., zk) = 0.

������� v=3 � ������� ������� En, �� �������� ���������� ������������� ���������:

"u �������� �������� ����� 3".

����������, ����� �������, ���������� ���������

P(u, v1, ..., vs)=0

� ���������� u, ������� ����� ������� � ����������� ������, ���� � ������ ���� u ����� ��� 3n. ���� ��������� �������� ����������� ��� ������ ������������ �� ������ �����.

 

4.6. ���������� ������������� ����� ��������� � ����������

��� � 1952 �. ��.�������� ��������, ��� ��������� x=Cyz, x=z! ���������� �������� ����� ����������. ������, ���� ���������� ������������� ����������, ����� ��������� ���������� ������������� � ���� ����������.

����� ��.��������, ����������� � ����������, ��� ���������������� �.�.������������. ����� �������� �� ������� ������ �������

(1 + p)y = sum {Cyz pz | for z =0 to y} (1)

��� p=1 �� ����� ��

2y = sum {Cyz | for z =0 to y},

����� �������, Cyz <= 2y ��� ���� z<=y. ������� ���� p - ������� ����������� �����, ��������, p=3y , �� Cyz < p ��� ���� z<=y, � �� ����� �������� �� ����� Cyz ��� �� ����� � ������� ��������� � ���������� p. ����� � (1) ������������ ����� p-����� ������ ����� (1+p)y. ���� �� ����� ������ �������� �� ����� x �������, ���������� � ��������� x= Cyz, ���� �����������, ����� x ���� ������ ��� ������� pz � ������ ����� (1+p)y , �.�.

x < p & (1+p)y = u + xpz + vpz+1,

���

u = sum {Cyi pi | for i=0 to z-1}, vpz+1 = sum {Cyi pi | for i=z+1 to y}

����� v ���������� ������������ ���, ��� ��� ����� � ��������� pz+1 (��� ������� �� ������� (1+p)y �� pz+1). ��� ��������� �� u (�� ��������� � �������, ���������� Cyi) �� ������ �����������, ����� ����� ����� ����������� u<pz (����� u ������������ ���������� ��� ������� �� ������� (1+p)y �� pz). � ����� ���� (��������, ��� Cyi < p),

sum {Cyi pi | for i=0 to z-1} <= (p-1) sum {Cyi | for i=0 to z-1} = (p-1)(pz-1)/(p-1) < pz.

����� �������, ���� x=Cyz & z<=y, ��

Epuv (p=3y & (1+p)y = u + xpz + vpz+1 & x<p & u<pz). (2)

������� ������, ��� �� z<=y ������ � (2) �������� x=Cyz. �������� (2) ����� u �������� �������� �� ������� (1+p)y �� pz. �������� �� (1) ���� ������� ���������� ����� ������

sum {Cyi pi | for i=0 to z-1},

�.�. u ����� ���� �����. ���������� ����� �����

q = ((1+p)y - u)/pz = x + vp.

��� ��� x<p, �� x �������� �������� �� ������� q �� p. � ������ �������,

q = Cyz + sum {Cyi pi-z | for i=z+1 to y},

��� Cyz <= 2y < p � ������� ����� ������� �� p. ��� ������, ��� Cyz ����� �������� �������� �� ������� q �� p, �.�. x=Cyz, ��� � y�����������.

���������� 4.15. ��������, ��� ������������� z<=y & (2) � ���������� ������������� ���� (E)P=0. ������� ����� ��������� E, ������� �������� P � ����� ������� ��� �������������.

��������, �������, ���������� x=z!. ����������� ��.�������� ������� �� ��������� ����. ��� ��������,

Cyz = y(y-1)...(y-z+1)/z!.

���� y ����������� ������ z, �� ��������� ������������� ���������� �� yz, �.�. z! ~ yz/Cyz. ����� ������� ����������� �������� y, ������ ������� yz/Cyz ���������:

yz/Cyz = z! (y/y) (y/y-1) ... (y/y-z+1).

������ ��������, ���

z! <= yz/Cyz <= z! (y/y-z)z = z! (1+z/y-z)z.

���� ������� y=z+zt, ��

z! <= yz/Cyz <= z! (1+1/t)z = z! (1+ sum{ Czi t-i | for i=1 to z}.

��������, ��� Czi <=2z, ������� t=2zu, �����

z! <= yz/Cyz <= z! (1+z/u).

�������, ���� u=2zzz, �������� (��������� z!<=z z)

z! <= yz/Cyz <= z! + 1/2.

����� �������, ���� y=z+2z2 2z zz, ��

z! = [yz/Cyz ],

��� [ ] - ������ ����� ����� (���������� �����, �� ������������� ����� � �������).

���������� 4.16. ��������, ��� ������ �������� ��� ��������� x=z! ���������� ������������� ���� (E)P=0. ������� ����� ��������� E, ������� �������� P � ����� ������� ��� �������������.

� 1960 �. �.������ �������, ��� ������ ��������� A ����������� �����, ������� ���������� �������������, �.�. ���������� ���������

x in A <-> (Ez1...Ezn) P(x, z1, ..., zn) = 0

��� ���������� �������� P � ������ ��������������, ����������� ��� ��������� ���� ������������� �������� ���������� (�������) �������� Q (����� � ������ ��������������).

���������� 4.17. ��������, ��� ����� ����� Q = x (1 - P2).

���������� 4.18. ������ �� ������� �������� (��. �.�.������� [1966]):

"x - ������� �����" <-> x>1 & x2 ����� x!+x,

��������� ���������� ������������� ��� ��������� ���� ������� �����. �������, ��� ������, ����� ��������� � ������� �������� P ��� ����. ������� Q = x (1 - P2) ������������ ��������� ���� ������� ����� ��� ��������� ���� ����� ������������� ��������. ����� �������, "������� ��� ������� �����", � ������������� ������� ��� ����� �������� ����������� �� ������ �����, � ������������ ������ ���-���� ����������.

 

4.7. ���������� ������������� �������� �����������

������ �� ������� � ����� �������� ���� - ��������� ��������������� ������� ����

(Ay<=t)(Ez1...Ezn) P(a1, ..., am, y, z1, ..., zn) = 0 (1)

(P - ������� � ������ ��������������, t - ������� ������ ������� � ������������ �������������� �� a1, a2, ..., am) � ���������� ������������� ����

(Ev1...Evk) Q(a1, ..., am, v1, ..., vk) = 0.

������ ����� �� ������� ��� � ������� 4.2 ��� �������������� ������, �������������� ���������� �������, � ���������� �������������. ���� ����������� ����� ��������� � �������� �� ����, ����������� � 1960-1961 ��. �.�������, �.�������� � ��.��������. ��������� ������������������ ���� ������� (��� ����� 1970 �.) ��������� �.�.������������ � ��.��������.

��� ������������� a1, ..., am ������� (1) ������������� ������������ ����� ����������� � ������������� (�������� �� ����������� �������� �����������) - � ������������� (t+1)n ����� (�� n �� ������ �������� y = 0, 1, ..., t). ������ ����������� ����������� ��� ���� �����:

y=0; z1(0), ..., zn(0),

y=1; z1(1), ..., zn(1),

...

y=t; z1(t), ..., z n(t),

���������� �� �������� A<= �����, ����������� ��� ������� ������������ (�� ��������� �� t) ������ ����������� �����. ����� ����������, ��������, ������������ ����� ������ ������ �� n �������� �������. ��� ����������� ����� ������������ ��������� ������� �� ��������. ���� �� ������� ������� ������� ������� ����� u0, u1, ..., uz, �� �� ���� ������� ����� ���� �� ��������� ����� w1, ..., wn �����, ����� ������ zi(y) ��������� �������� �� ������� wi �� uy, �.�.

zi(y) <uy & wi = zi(y) mod uy (2)

��� ���� y<=t � i=1, ..., n (��� ����� �������� uy ������ ����, ����������, ���������� ��������).

�� ���� ��� ��� ����� �������, ����� ������� ���� �������� �� w1, ..., wn, ����� ������� zi(y) ������������� ��������� (1)? ����� � ��� ��������� - ���������� ���������� ����� w1, ..., wn � ��������� P=0 ������ ����� zi(y). ������ y ��������� i�������������� ���� ����� x. ��� ����� ������� � �������� P(a1, ..., am, x, w1, ..., wn)? ���� � ���������� � (2) �� ��������� ���, ����� ��� ���� y = 0, 1, ..., t ����� �����

x = y mod uy, (3)

�� ����� ����� ����������, ���

P(a1, ..., am, x, w1, ..., wn) = P(a1, ...,am, y, z1(y), ..., zn(y)) mod uy.

��� ��� �������� P ������ ����� ����, �� ��������

P(a1, ..., am, x, w1, ..., wn) = 0 mod uy

��� ���� y<=t, �.�. �������� ����� ������� �� ��� ����� uy. �� ��� ����� ������� ������� ������, ������� �������� P ������ �������� � �� �� ������������:

P(a1, ..., am, x, w1, ..., wn) = 0 mod u0u1...uz. (4)

��������� ������ �� (4) � ������ ������� - �� ��� �� ��������� �����-�� �������������, � ��� �� �������, ���������� �� ����� w1, ... ,wn. ����� ���� ����� zi(y) - ������� �� ������� wi �� uy, �� �������� (1) � (2) ������ ����� �����

P(a1, ..., am, y, z1(y), ..., zn(y)) = 0 mod uy.

����� �������� ������ �� ������ = 0 mod uy, �� � = 0, �������� ����� ������ ���� ������ ������ uy. ������ ������ �������� �������� P ����� �������� ��������� �������. ����� z ��������� �����, ������� ������ ���� ����� zi(y), ����� N - ������� �������� P, ����� M - ����� ������� ��� �������������. �����

|P(a1, ..., am, y, z1(y), ..., zn(y))| <= M ((a1+1)...(am+1)(t+1)(z+1))N.

���������� 4.19. ���������, ��� ��� ������������� ���.

��������� ������ ��������� ����� T. ����� ������������ ��� �������� �������� P ��������� ������ ���� uy, �� ������ y�����������:

�) ����� ������� �� ������� ����� wi �� uy ������ ��� i y������ z,

�) ����� ��� uy ���� ������ T (���������� �� z). ����� ����, �� ������ ����� ���������� ������� ��������� (������� � ������� ������� �������) ����� uy. � �������� ���� y���������� ����� ���� �� �������������� � ����-������� ������ (��. ������ 3.3), ���������

uy = 1 + T t! (1+y),

��� ����� ��� ���������� ������������� ���������� �� ��� �����. � ���������, � ����� ������ �������� ��������� ����������� ������, ����� �������� ���������� ������������� ��� ������������ u0u1...uz, �.�. ��� ������ � ��������� (4). � ���� ����� �.�����, �.������ � ��.�������� �������������� ��� � �������.

����� ������� �����������, ������, ������ ��������� ����� uy, ������������ ������� �.�.������������ � ��.��������. ���������� ����� Cvt+1(��� ������� t+1<=v) ��������� �������:

Cvt+1 = v(v-1)...(v-t) / (t+1)! = ((v+1)/1-1) ((v+1)/2-1) ... ((v+1)/(t+1)-1).

���� �����������, ����� v+1 �������� �� (t+1)!, �� ��� ����������� �������� ������ �������. ���� ����������� ��� ������ - ����� v+1 �������� �� ((t+1)!)z , �� ��� ����������� �������� ������� ��������.

���������� 4.20. ���������, ��� ��� ������������� ��� (���� d - ����� �������� i-�� � j-�� ������������, ����������� �� ��������).

����, ���������, ����� v+1 �������� �� ((t+1)!)z, � �������

uy = (v+1) / (y+1) - 1.

����� � ������������� u0u1...uz ������� ������� �� ����� - ��� ����� Cvt+1, � ���������� ������������� ��� ����� ��������� �� ������� �����. ������ �� ����� ���������� ��� ���� ������� (res(a, b) �������� "������� �� ������� a �� b"):

G1: P(a1, ..., am, x, w1, ..., wn) = 0 mod Cvt+1,

G2: (Ay<=t) x = y mod ((v+1)/(y+1)-1)

G3i: (Ay<=t) res (wi, (v+1)/(y+1)-1) < z,

G4: (v+1)/(y+1)-1 > M((a1+1)...(am+1)(t+1)(z+1))N,

G5: v+1 ������� �� ((t+1)!)z.

���������� 4.21. ��������, ��� (1) ����������� �������

Ex Ev Ez Ew1 ... Ewn G1 & G2 & G31 & ... & G3n & G4 & G5.

�� �������� ��������������� ��������� �������� �� �������� ��� ���������� ����� x, w1, ...,wn.

� ���������, ��������� ������� ������ ����� ������������� � ���������� �������������. ������ ����� �������� Ay<=t � �������� G2, G3i. ������ � ������� �� Ay<=t � �������� ������� (1), ����� ���� ������� ����� �� ��� ������������ ����������� ��������������, � ��� ����������� � ���������� �������� �����- ������. ����� ���������, ��� ��� �������� �������� ���������� �� ��������� Ay<=t ���������.

������� �������, ��� ���� ����� v=x, �� ������� G2 ����� ��������� �������������,�.�. � ����� ������ ���������� ��� ����� ��������. � ����� ����,

(x+1)/(y+1)-1 = (x-y)/(y+1)

�������� ����� ������, ������� ����� x-y (������� ����� y+1), �.�.

x = y mod ((x+1)/(y+1)-1).

�������� ������ ��������� G3i. ���� ������� �� ������� wi �� (x+1)/(y+1)-1 ������ z, �� ���� �� ����� wi, wi-1, ..., wi-z+1 ������� �� (x+1)/(y+1)-1, �.�. �� ��� ����� ������� � ������������

wi(wi-1)...(wi-z+1) = wi! / (wi-z)!.

��������� ����� (x+1)/(y+1)-1 ��� ��������� y ������� ������� ������, �� �������

Ay<=t ( (x+1)/(y+1)-1 ����� wi! / (wi-z)! )

����������� �������

G3i': Cxt+1 ����� wi! / (wi-z)!

(�.�. �������� ������� Ay<=t). ��� ��� ����� �������, ��� �� ����� ������� ���������� ������������� ���������� � ��� ��� �� �������� ����� �������� G3i' ������������ ����������. ��, � ���������, G3i' �� ����������� G3i !. �� G3i �������� G3i' (��� �� ������ ��� ���������), ������ �� G3i' �� �������� G3i - ���� ������������ ������� �� ��������� �����, ��� ��������, ��� �� ��� ����� ����� �������� ���� �� ������������. ��� �� ����� ����� �������������?

���� ����� R ����� ����������� P1P2.. Pk, �� R ����� ��������� � ����������� R1R2...Rk , ��� ������ Ri ����� ���� Pi. ���� Ri - ���������� �� ������������ R, �� Rik >= R � Ri >= k-root(R). ����� �������, ���� ������������ P1P2...Pk ������� �� R, ����� ���������� ������, ��� R � ���� �� ������������ Pi ����� ����� �������� >= k-root(R). �������� ������������� ������.

������� ���� ������ ������� G3i ������� (� ����� �������, ����� �������) ������� G3i', �� ����� ������������� ������, ��� ��������� wi - j (��� 0<=j<=z) ����� ����� �������� � ������

uy = (x+1) / (y+1) - 1,

������� �� �������� >= z-root(uy). � �������, ����� ����������� y����������. � ����� ����, "�������" ��������� ������� �� w1 �� wn (��� ������������� y<=t). ��� ��������� z1(y) < z �������� w1 - z1(y) ������� �� ��������� �������� S1 >= z-root(uy) ����� uy. �����, ��� ��������� z2(y) < z �������� w2 - z2(y) ������� �� ��������� �������� S2 >= z-root(S1) ����� S1, �.�. w2 - z2(y) ������� �� �������� S2 >= z2-root(uy) ����� uy. � ��� �����, �� �������� wn - zn(y), ������� ������� �� �������� Sn >= zn-root(uy) ����� uy (����� ����� zn(y) < z).

������� ����, ���������, ��� ��� ���� i=1, ..., n

wi = zi(y) mod Sn,

��� Sn ����� uy (� �������������, � Cit+1) � Sn >= zn-root(uy). �� ������� G1 �����

P(a1, ..., am, x, w1, ..., wn) = 0 mod Sn,

������ ��������, ���

P(a1, ..., am, y, z1(y), ..., zn(y)) = 0 mod Sn.

������ ��� zi(y) < z. �������� ����� ������ ����� ��������� ����, ���� ��� ����� (�� ����������� ��������) ������ ������ Sn, �.�. ���� zn-root(uy) ����� ������

T = M((a1+1)...(am+1)(t+1)(z+1))N.

��� ������, ��� ������� G4 ����� �������� ��������

G4': (x+1) / (t+1) - 1 > T**z**n,

��� ** �������� ���������� � �������.

���������� 4.22. ��������� ��� ���, ��� (1) ������������� ����������� �������

Ex Ev Ez Ew1 ... Ewn G1' & G31'& ... & G3n' & G4' & G5'.

��� G1', G5' ���������� �� G1, G5 ���, ��� ������ v ����������� x. ��������, ��� ������������� ��� ��������� ������� � ���������� �������������.

��� ����� ������ ���������� A<= ������ �� �����.