Back to title page.

We will investigate only a special (the simplest!) case of
Fermat's equation - where D=a^{2}-1 for some natural
number a>1:

x^{2} - (a^{2}-1)y^{2}
= 1.

No problems to prove the existence of non-trivial solutions for this equation: you can simply take x=a, y=1. After this, all the other natural solutions we can calculate by using the following smart idea. Let us note that

x^{2} - (a^{2}-1)y^{2}
= (x+y*sqrt(a^{2}-1)) * (x-y*sqrt(a^{2}-1)) = 1.

Take our first non-trivial solution x=a, y=1:

a^{2} - (a^{2}-1) = (a+sqrt(a^{2}-1))
* (a-sqrt(a^{2}-1)) = 1.

Consider the n-th power:

(a+sqrt(a^{2}-1))^{n} *
(a-sqrt(a^{2}-1))^{ n} = 1.

Now let us apply the Newton's binomial formula to the
expression (a+sqrt(a^{2}-1))^{n}. For example, if
n=2, then

(a+sqrt(a^{2}-1))^{ 2} = a^{2}
+ 2a*sqrt(a^{2}-1) + (a^{2}-1).

I.e. some of the items contain sqrt(a^{2}-1), and some
do not. Let us sum up either kind of the items:

(a+sqrt(a^{2}-1))^{ n} = x_{n}(a)
+ y_{n} (a)sqrt(a^{2}-1), -----------(1)

where x_{n} (a), y_{n} (a) are natural
numbers. For example, x_{2}(a)=2a^{2}-1, y_{2}
(a)=2a. Still, in this way we can obtain also

(a-sqrt(a^{2}-1))^{ n} = x_{n}
(a) - y_{n} (a)sqrt(a^{2}-1) ----------(2)

with the same x_{n} (a) and y_{n} (a)
(verify!). Now multiply (1) by (2):

(a^{2}-a^{2}+1)^{ n} =
x_{n}^{2} - (a^{2}-1)y_{n}^{2},

x_{ n}^{2} - (a^{2}-1)y_{
n}^{2} =1.

Hence, for any number n>=0 the pair

x = x_{n}(a),

y = y_{n} (a)

is a solution of the equation x^{2}-(a^{2}-1)y^{2}=1.
The values n=0, 1 yield the solutions that we already know: x=1,
y=0, and x=1, y=1. Still, n=2 yields a new solution; x=2a^{2}-1,
y=2a.

From our definition of the numbers x_{n} (a), y_{n}
(a) the following recurrent identities can be derived (m,
n>=0):

x_{m+n}(a) = x_{m}(a)*x_{n}(a) + y_{m}(a)*y_{n}(a)*(a^{2}-1),

y_{m+n}(a) = x_{m}(a)*y_{n}(a) + y_{m}(a)*x_{n}(a).

For m=1 this means:

x_{n+1}(a) = a*x_{n}(a) + (a^{2}-1)*y_{n}(a),

y_{n+1} (a) = x_{n}(a) + a*y_{m}(a).

**Exercise 4.8.** Prove these identities. Verify also that
x_{n} (a) and y_{n} (a) are increasing functions
of n (i.e. that they really yield an infinite set of solutions of
the equation x^{2}-(a^{2}-1)y^{2}=1).

It appears that the sequence {(x_{n}(a), y_{n}(a)
| n>=0} covers **all **natural solutions of Fermat's
equation.

**Lemma 1.** If a>1, then

x^{2}-(a^{2}-1)y^{2}=1
<-> En(x=x_{n}(a) & y=y_{n}(a)).

**Proof.** 1) Leftwards. This we already have proved.

2) Rightwards. Let x, y be a solution of our equation. If
x<=1, then x=1 and y=0, i.e. x=x_{0}(a), y=y_{0}(a).
Now let x>1. Then y>0. If x, y would be x_{n} (a),
y_{n} (a), and u, v would be x_{n-1}(a), y_{n-1}(a),
then we would have:

x = au+(a^{2}-1)v, -----------(3)

y = u+av.

Let us express u, v from these equations:

u = ax-(a^{2}-1)y, -----------(3a)

v = -x+ay.

Now forget about x_{n}, y_{n}, x_{n-1},
y_{n-1}: the numbers u, v are simply calculated from x, y
by formulas (3a).

**Exercise 4.9.** Verify that u^{2}-(a^{2}-1)v^{2}=1,
i.e. that (u, v) is a solution. Verify also that 0<u<x and
v>=0.

Thus, if (x, y) is a solution of our equation, x>1, then
these numbers can be expressed by formulas (3) through another
solution (u, v) such that u<x. If u>1, again, we can
express (u, v) through another solution (u', v') such that
u'<u, etc. until we reach the solution (1, 0). If n is the
number of these downward steps, then x=x_{n}(a) and y=y_{n}(a).
Q.E.D.

Thus we have an elegant (more than 300 years old) algorithm
allowing to calculate the sequence of all natural solutions of
the equation x^{2}-(a^{2}-1)y^{2}=1. What
makes this algorithm important in the context of Hilbert's 10th
problem?

**Lemma 2.** If a>1 and n>=0, then

a^{n} <= x_{n} (a) <=
(a+sqrt(a^{2}-1))^{ n}.

**Proof.**

x_{n}(a)+y_{n}(a)*sqrt(a^{2}-1)
= (a+sqrt(a^{2}-1))^{n},

x_{n}(a) =a* x_{n-1}(a)+(a^{2}-1)y_{n}(a)
>= a* x_{n-1}(a).

Q.E.D.

Hence, as function of n, x_{n}(a) is growing
exponentially. And this is achieved by a Diophantine condition F
on x:

F(x) <-> Ey(x^{2}-(a^{2}-1)y^{2}=1).

Not bad as the first step - if we wish to find, among others,
a polynomial P(x, z_{1}, ..., z_{m}) such that

Ey(x=2^{y}) <-> Ez_{1}...Ez_{m}
P(x, z_{1}, ..., z_{m}).

(These considerations were proposed by J.Robinson in her 1952 paper.)

Now let us follow the idea due to Matiyasevich: let us
investigate the remainders from dividing the numbers x_{n}(a),
y_{n}(a) by each other.

First, let n be fixed, n>0, and let us observe the
remainders from dividing x_{N}(a) and y_{N}(a) by
x_{n}(a) as N = 0, 1, 2, .... For this purpose we will
consider mod x_{n}(a) the above recurrent identities for
x_{m+n}, y_{m+n}. I.e. we will ignore items
divisible by x_{n} (a):

x_{m+n}(a) = x_{m}(a)*x_{n}(a) + y_{m}(a)*y_{n}(a)*(a^{2}-1)
= y_{m}y_{n}*(a^{2}-1) mod x_{n},

y_{m+n}(a) = x_{m}(a)*y_{n}(a) + y_{m}(a)*x_{n}(a)
= x_{m}y_{n} mod x_{n}.

Substitute m+n for m:

x_{m+2n} = (a^{2}-1)y_{m+n}y_{n}
= (a^{2}-1)x_{m}y_{n}^{2} mod x_{n},

y_{m+2n} = x_{m+n}y_{n} = (a^{2}-1)y_{m}y_{n}^{2}
mod x_{n}.

Now let us note that x_{n}^{2}-(a^{2}-1)y_{n}^{2}=1,
hence (a^{2}-1)y_{ n}^{2} = x_{ n}^{2}-1
= -1 mod x_{ n}. Thus, we can replace (a^{2}-1)y_{
n}^{2} by -1:

x_{m+2n} = -x_{m} mod x_{n},
-----------(4)

y_{m+2n} = -y_{m} mod x_{n}.

Substitute m+2n for m:

x_{m+4n} = -x_{m=2n} = x_{m} mod x_{n},

y_{m+4n} = -y_{m+2n} = y_{m} mod x_{n}.

Thus, the remainders of x_{N}(a) and y_{N}(a)
mod x_{n}(a) are changing with the period 4n, and we can
concentrate on investigating these remainders for N = 0, 1, 2,
..., 4n-1.

According to (4) we have (mod x_{n}):

x_{0 }= x_{0}, x_{1 }= x_{1},
..., x_{2n-1 }= x_{2n-1},

x_{2n }= - x_{0}, x_{2n+1 }= - x_{1},
..., x_{4n-1 }= - x_{2n-1},

y_{0 }= y_{0}, y_{1 }= y_{1},
..., y_{2n-1 }= y_{2n-1},

y_{2n} = - y_{0}, y_{2n+1 }= - y_{1},
..., y_{4n-1 }= - y_{2n-1}.

Since the numbers x_{n+1}, ..., x_{2n-1}
exceed the divisor x_{n}, our analysis is not yet
complete. To complete it, let us consider the recurrent
identities expressing x_{2n}, y_{2n} through x_{2n-m},
y_{2n-m }and x_{m}, y_{m}:

x_{2n} = x_{2n-m}x_{m} + (a2-1)y_{2n-m}y_{m},

y_{2n} = x_{2n-m} y_{m} + y_{2n-m}
x_{m}.

Let us express x_{2n-m}, y_{2n-m} from these
equations:

x_{2n-m} = x_{2n} x_{m} - (a2-1)y_{2n}
y_{m},

y_{2n-m} = y_{2n} x_{m} - x_{2n}
y_{m}.

By (mod x_{n}): x_{2n} = -x_{0} = -1
and y_{2n} = -y_{0} = 0, thus we obtain:

x_{2n-m} = -x_{m} mod x_{n},

y_{2n-m} = y_{m} mod x_{n}.

Now we can complete our analysis:

x_{0 }= x_{0}, x_{1 }= x_{1},
..., x_{n-1 }= x_{n-1},

x_{n }= - x_{n}, x_{n+1 }= - x_{n-1},
..., x_{2n-1 }= - x_{1},

x_{2n }= - x_{0}, x_{2n+1 }= - x_{1},
..., x_{3n-1 }= - x_{n-1},

x_{3n }= x_{ n}, x_{3n+1 }= x_{ n-1},
..., x_{ 4n-1}= x_{1},

y_{0 }= y_{0}, y_{1 }= y_{1},
..., y_{n-1 }= y_{n-1},

y_{n }= y_{n}, y_{n+1 }= y_{n-1},
..., y_{2n-1 }= y_{1},

y_{2n} = - y_{0}, y_{2n+1 }= - y_{1},
..., y_{3n-1 }= - y_{n-1}.

y_{3n} = - y_{ n}, y_{n3n+1 }= - y_{
n-1}, ..., y_{4n-1 }= - y_{1}.

This result allows proving of the following lemma (due to Matiyasevich):

**Lemma 3.** Let a>=3, n>=1, 0<=m<=n. Then for
all N:

x_{N}(a) = x_{m}(a) mod x_{n}(a)
<-> (N=+m mod 4n) v (N=-m mod 4n).

**Proof.** 1) Leftwards. If N=4kn+m or N=4kn-m, then x_{N}=x_{m}
mod x_{n }follows from the results of the above analysis.

2) Rightwards. Let x_{N}=x_{m} mod x_{n},
where 0<=m<=n. Let us divide N by 4n: N=4kn+m', where
0<=m'<4n. If (accidentally) m'<n, then (according to the
results of the above analysis) m'=m, and N=4kn+m - Q.E.D.

Similarly, if 3n<=m', then m'=4n-m, and N=4(k+1)n-m - Q.E.D.

**Exercise 4.10.** Verify that the third alternative
n<m'<3n is impossible. (**Hint:** if a>2, then i<j
-> x_{i}(a) < x_{j}(a)/2.)

**End of proof.**

Now we must perform a similar investigation of remainders from
dividing y_{N}(a) by y_{n}(a) (n is fixed,
n>=1, N = 0, 1, 2, ...).

**Exercise 4.11.** Perform this investigation yourself. You
will obtain that y_{N}(a) mod y_{n}(a) is
changing with the period 2n, and (mod y_{n}):

y_{0 }= y_{0}, y_{1 }= y_{1},
..., y_{n-1 }= y_{n-1},

y_{n }= - y_{n}, y_{n+1 }= - y_{n-1},
..., y_{2n-1 }= - y_{1.}

From this result we can derive another lemma (due to Matiyasevich):

**Lemma 4.** Let a>=2, n>=1. Then y_{N}(a) is
divisible by y_{n}(a), iff N is divisible by n.

**Proof.** Immediately from the results of the exercise
4.11.

The following very important (see below) lemma also is due to Matiyasevich:

**Lemma 5.** Let a>=2, n>=1. Then y_{N}(a) is
divisible by y_{n}^{2}(a), iff N is divisible by
n*y_{n}(a).

**Proof.** You can easily verify (induction by k) that:

x_{kn} = x_{n}^{k} mod y_{n}^{2},

y_{kn} = kx_{n}^{k-1}y_{n }mod
y_{n}^{2}.

1) Rightwards. If y_{N} (a) is divisible by y_{n}^{2}(a),
then by lemma 4: N=kn. If y_{kn} is divisible by y_{n}^{2},
then kx_{n}^{k-1}y_{n} also is divisible
by y_{n}^{2}, i.e. kx_{n}^{k-1}
is divisible by y_{n}. Since x_{n}^{2}-(a^{2}-1)y_{n}^{2}=1,
the number x_{n} cannot have common divisors with y_{n},
hence, k is divisible by y_{n}. And since N=kn, N is
divisible by ny_{n}.

2) Leftwards. If N is divisible by ny_{n}, then N=kn,
where k is divisible by y_{n}. Hence, kx_{n}^{k-1}y_{n}
is divisible by y_{n}^{2}, i.e. y_{N}=y_{kn}
also is divisible by y_{n}^{2}.

Q.E.D.

We will need also the following three lemmas (Lemma 6 is from the 1952 paper by J.Robinson):

**Lemma 6.** Let a>=2, n>=1. Then:

x_{n} (a) = 1 mod(a-1),

y_{n} (a) = n mod(a-1).

**Lemma 7.** Let a, a' >=2, b>==1. Then, if a=a' mod
b, then for all n:

x_{n}(a) = x_{n}(a') mod b,

y_{n}(a) = y_{n}(a') mod b.

**Lemma 8.** Let a>=2, k>=0. Then:

x_{2k}(a) = 1 mod 2, x_{2k+1}(a) = a mod 2,

y_{2k} (a) = 0 mod 2, x_{2k+1}(a) = 1 mod 2.

**Exercise 4.12.** Prove these lemmas by induction.

Now, following Matiyasevich, we must build a Diophantine representation of the predicate

F(a, x, y, n) <-> a>=3 & x=x_{n}(a)
& y = y_{n}(a).

I.e. we must put on x, y some "Diophantine
conditions" forcing x equal to x_{n}(a), and y -
equal to y_{n}(a). Of course, we will begin with the
condition

**F**_{1}**:** x^{2}-(a^{2}-1)y^{2}=1.

Hence, there is m such that x=x_{m}(a) and y = y_{m}(a),
and we must force m equal to n.

By Lemma 6, y_{m} (a) = m mod(a-1), hence, we could
try putting the second condition y=n mod(a-1), then we would have
m=n mod(a-1). Unfortunately, if n>=a-1, then we will not be
able to conclude that m=n.

To avoid this difficulty, a turning movement (literally!) is necessary. Let us introduce another Fermat's equation with a free parameter A:

**F**_{2}**:** X^{2}-(A^{2}-1)Y^{2}=1.

And now we will require not y=n mod(a-1), but

**F**_{3}**:** Y = n mod(A-1).

(Since A is free, we may hope to ensure n<A-1). Since, for
some M, X=x_{M}(A) and Y=y_{M}(A), then by Lemma
6, Y=M mod(A-1), hence,

M = n mod(A-1). -----------(1)

This conclusion will be useful only, if we will be able to connect the new numbers (X, Y) with our initial numbers (x, y). So, let us introduce an additional module U, and let us require

**F**_{4}**:** A = a mod U & X = x
mod U.

By Lemma 7, A = a mod U implies

x = x_{m}(a) = x_{m}(A) mod U,

X = x_{M}(A) = x_{M}(a) mod U.

From F_{4} we have X = x mod U, hence

x_{M}(a) = x_{m}(a) mod U.
----------(2)

We could apply here Lemma 3, yet then U must be a solution of Fermat's equation with the same parameter a. So, let us introduce another number V, and let us require

**F**_{5}**:** U^{2}-(a^{2}-1)V^{2}=1.

Hence, for some N: U=x_{N}(a) and V=y_{N}(a),
and we can rewrite (2) as

x_{M}(a) = x_{m}(a) mod x_{N}(a).

To apply Lemma 3, we must ensure that m<=N. This can be achieved by putting the condition

**F**_{6}**:** x<=U

(since x_{i}(a) is increasing by i, x_{m}
(a)=x<=U=x_{N}(a) means m<=N). Finally, we can
apply Lemma 3:

(M = m mod 4N) v (M = -m mod 4N). ----------(3)

Now we are at the end of our turning movement. Let us compare (3) with (1):

M = n mod(A-1).

Our intention was to force m=n. We would have achieved this,
if 4N would exceed M and m (then (3) would yield M=m or M=-m),
and if A-1 would exceed M and n (this would yield M=n, i.e. m=n).
The way to ensure both "exceed's" would be to force a
large common divisor of A-1 and 4N. Still, we do not know the
number N, how could we find a large divisor of 4N? On the other
hand, we have Lemma 5: y_{N}(a) is divisible by y_{m}^{2}(a),
iff N is divisible by my_{m}(a). Or simply, V is
divisible by y^{2}, iff N is divisible by my. Hence, if
we will put the condition

**F**_{7}**:** V is divisible by y^{2},

then 4y will be a divisor of 4N (we omit m as an unknown number that we could not force to divide A-1). Now we must put the condition

**F**_{8}**:** A-1 is divisible by 4y

to force 4y to be a common divisor of 4N and A-1. After this, (1) and (3) yield:

(M = n mod 4y) & ((M = m mod 4y) v (M = -m mod 4y)).

Hence,

(n = m mod 4y) v (n = -m mod 4y).

Since y=y_{m}(a) is increasing by m, we have y>=m.
On the other hand, we may put the condition

**F**_{9}**:** n<=y.

Finally, we must consider two possibilities:

1) n = m mod 4y, i.e. n-m is divisible by 4y. Since |n-m|<=y, this is possible, iff n=m. Q.E.D.

2) n = -m mod 4y, i.e. n+m is divisible by 4y. Since n+m<=2y, this is possible, iff n=m=0. Q.E.D.

Thus we have established that the condition

a>=3 & **E**A**E**X**E**Y**E**U**E**V(F_{1}
& F_{2} & F_{3} & F_{4} &
F_{5} & F_{6} & F_{7} & F_{8}
& F_{9}) ----------(4)

implies that x=x_{n}(a) and y=y_{n}(a), i.e.
F(a, x, y, n).

Our task will be completed, if we will show that F(a, x, y, n)
also implies (4). So, having a>=3 & x=x_{n}(a)
& y=y_{n}(a), we must find the numbers A, X, Y, U, V
such that F_{i} are satisfied for all i=1, 2, ..., 9.

F_{1}: x^{2}-(a^{2}-1)y^{2}=1
is satisfied by Lemma 1.

F_{9}: n<=y is satisfied, since y_{n}(a) is
increasing by n.

The numbers U, V (a solution of the same equation as x, y) we
can choose in the following way: let N be the least even (see
below!) multiple of ny, such that x_{N}(a)>=x (see F_{6}!),
and let U=x_{N}(a), V=y_{N}(a). Then:

F_{6}: x<=U is satisfied.

F_{5}: U^{2}-(a^{2}-1)V^{2}=1
is satisfied.

And by Lemma 5, V is divisible by y^{2}, i.e. F_{7}
is satisfied.

It remains to determine the parameter A of our auxiliary equation and its solution X, Y. The following conditions must be satisfied:

F_{2}: X^{2}-(A^{2}-1)Y^{2}=1,

F_{3}: Y = n mod(A-1),

F_{4}: A = a mod U & X = x mod U,

F_{8}: A-1 is divisible by 4y.

1) **Case n=0.** Then x=1, y=0. F_{4} is satisfied,
since U=1. F_{8} will be satisfied, iff we take A=1.
After this, F_{2} will be satisfied, iff we take X=1, and
F_{3} - iff we take Y=0. Q.E.D.

2) **Case n>0.** Then y>0. As the first step, let us
use F_{4} and F_{8} to choose A. If the numbers U
and 4y would have no common divisors, then we could obtain A from
Chinese remainder theorem (see Section
3.3) - as a number A>1 that satisfies simultaneously A = a
mod U and A = 1 mod 4y. Then F_{8} and the first part of
F_{4} would be satisfied.

So, let us prove that U and 4y have no common divisors. On the
one hand, U is an odd number (by Lemma 8, since N is even number,
see above). On the other hand, V is divisible by y^{2},
and U^{2}-(a^{2}-1)V^{2}=1, hence, U and
y have no common divisors.

It remains to choose X, Y. Let us choose X=x_{n}(A)
and Y=y_{n}(A). Then F_{2} is satisfied. By Lemma
6, F_{3} also is satisfied. And finally, since x=x_{n}(a)
and A = a mod U, by Lemma 7 we obtain x_{n}(A) = x_{n}(a)
mod U, and X = x mod U, i.e. the second part of F_{4}
also is satisfied. Q.E.D.

Thus, we have established the equivalence of F(a, x, y, n) and (4).

**Exercise 4.13.** Transform (4) into a Diophantine
representation E(P=0). Determine the number of quantifiers E, the
order and the sum of coefficient modules of the polynomial P.

Now we will use the Diophantine representation of "Fermat's" predicate F(a, x, y, n) from the previous section to obtain a Diophantine representation of the exponentional function, i.e. of the predicate

E(u, v, n) <-> u=v^{n} &
v>=3

(assuming that 0^{0}=1).

Let us start with our fundamental equality

(a+sqrt(a^{2}-1))^{n} = x_{n}(a)
+ y_{n}(a)*sqrt(a^{2}-1).

Let us denote v = a+sqrt(a^{2}-1). Then we will have
simply v^{n} on the left hand side. On the right hand
side we can replace sqrt(a^{2}-1) by v-a:

v^{n}-x_{n}(a)-y_{n}(a)(v-a)=0.

Hence, this equation has the solution v_{1}=a+sqrt(a^{2}-1).
Since all the coefficients of it are rational numbers, the number
v_{2}=a-sqrt(a^{2}-1) also is its solution. On
the other hand, v_{1}, v_{2} are solutions of the
equation

v^{2}-2av+1=0.

Hence, the polynomial v^{n}-x_{n}(a)-y_{n}(a)(v-a)
is divisible by v^{2}-2av+1 in the field of rational
numbers. Moreover, the coefficients of this fraction polynomial
are integer numbers (because the leading coefficient of the
divisor is 1). Thus, if v is integer, then the number v^{n}-x_{n}(a)-y_{n}(a)(v-a)
is divisible by the number v^{2}-2av+1. This is the main
lemma from the 1952 paper by Julia Robinson:

**Lemma 9.** If a>=1 and n>=0, then

v^{n} = x_{n}(a)+y_{n}
(a)(v-a) mod(v^{2}-2av+1).

**Exercise 4.14.** a) Verify Lemma 9 for n=0 and n=1 (the
above argument is working only for n>=2).

b) Verify that

v^{n}-x_{n}(a)-y_{n}(a)(v-a)
= (v^{2}-2av+1) (y_{1}v^{n-2}+y_{2}v^{n-3}+...+y_{n-2}v+y_{n-1}).

(This will be a direct proof of Lemma 9 - without the above "smart" algebraic considerations.)

Lemma 9 allows to connect the power v^{n} with the
numbers x_{n}(a), y_{n}(a) by using polynomials
of **restricted** order (v-a and v^{2}-2av+1). Having
this result, we can easily obtain a Diophantine representation of
u=v^{n}.

Indeed, having the variables u, v, n, we must put some
Diophantine conditions that will force u=v^{n}. As the
first step, let us take some numbers a, x, y, n under the
condition

**E**_{1}**:** F(a, x, y, n).

Then x=x_{n}(a) and y=y_{n}(a), and by Lemma
9:

v^{n} = x+y(v-a) mod(v^{2}-2av+1).

In order to "bind" u and v^{n}, let us put
the condition

**E**_{2}**:** u = x+y(v-a) mod(v^{2}-2av+1).

Then

u = v^{n} mod(v^{2}-2av+1).
--------(1)

We could derive u=v^{n} from this congruence, if the
module v^{2}-2av+1 would be greater than both u and v^{n}.
This can be achieved by increasing the free parameter a - then |v^{2}-2av+1|
will grow as 2av-v^{2}-1. Thus the condition

**E**_{3}**:** u < 2av-v^{2}-1

ensures one half of the necessary. Still, how to ensure v^{n}<2av-v^{2}-1
- by using Diophantine conditions? I.e. we must force the
parameter a to grow exponentially by n. We know already from
Lemma 2, that x_{n}(v) is growing exponentially by n: x_{n}(v)>=v^{n}.
Hence, we can try to force x_{n}(v)<2av-v^{2}-1
instead of v^{n}<2av-v^{2}-1. So, let us
introduce the numbers X, Y such that

**E**_{4}**:** F(v, X, Y, n),

i.e. X=x_{n}(v) and Y=y_{n}(v). If we add also

**E**_{5}**:** X < 2av-v^{2}-1,

then v^{n} <= x_{n}(v) = X < 2av-v^{2}-1.
Having this result plus E_{3} and (1) we obtain u=v^{n}.

Thus, we have succeeded in deriving u=v^{n} from the
condition

**E**a**E**x**E**y**E**X**E**Y(E_{1}
& E_{2} & E_{3} & E_{4} &
E_{5}). --------(2)

Since, v>=3 is included in E_{4}, we have derived
also E(u, v, n) from (2).

**Exercise 4.15.** a) To complete the proof, derive (2)
from E(u, v, n).

b) Transform (2) into a Diophantine representation E(P=0). Determine the number of quantifiers E, the order and the sum of coefficient modules of the polynomial P.

Thus, following the work by Matiyasevich and Julia Robinson,
we have obtained for the predicate u=v^{n} & v>=3
a Diophantine representation

Ez_{1}...Ez_{k} P(u, v, n, z_{1},
..., z_{k})=0.

If we substitute v=3 and add the quantifier En, we obtain a Diophantine representation

Ev_{1}...Ev_{s} P_{1}
(u, v_{1}, ..., v_{s})=0

of the predicate "u is power of 3". Hence, the
equation P_{1} (u, v_{1}, ..., v_{s})=0
has natural solutions, iff the parameter u is 3^{n}. This
result was qualified as unexpected by some (anonymous?)
number-theorists.

C_{y}^{z} denotes the coefficient at p^{z}
in the Newton's binomial formula for (1+p)^{y}.

The factorial function y! is defined as follows: 0!=0, and if y>0, then y!=1*2*...*y.

Julia Robinson showed in 1952 how the predicates z<=y &
x= C_{y}^{z} and x=y! can be "Diophantine
expressed" through the predicate x=y^{z}. Now, using
these methods, we can obtain Diophantine representations of these
predicates.

Matiyasevich improved the first method in the following way.
Let us start with the Newton's binomial formula for (1+p)^{ y}:

(1+p)^{y} = sum { C_{y}^{z}
p^{z} | for z=0 to y}. --------(1)

For p=1 we would have

2^{y} = sum { C_{y}^{z}
| for z=0 to y}.

Thus, C_{y}^{z} <=2^{y} for all
z<=y.

From (1) we can obtain also:

(1+p)^{y} = u + (C_{y}^{z}
+ vp)p^{z},

where

u = sum {C_{y}^{i} p^{i}
| for i=0 to z-1},

v = sum {C_{y}^{i}p^{i-z-1}
| for i=z+1 to y}.

If we had u<p^{z}, then we could compute u as (1+p)^{y}
mod p^{z}. And if we had also C_{y}^{z}
<p, then we could compute C_{y}^{z} as ((1+p)^{y}-u)/p^{z}
mod p, i.e. we had reduced computing of C_{y}^{z}
to computing of the exponential function.

Of course, if p would be large enough (for example, p=3^{y}+1),
then C_{y}^{z} <p would be ensured. Still, how
about u<p^{z}? Fortunately, for such a large p:

u<= sum {2^{y}p^{i} | for
i=0 to z-1} = 2^{y}sum {p^{i} | for i=0 to z-1} =
2^{y}(p^{z}-1)/(p-1) = (2/3)^{y}(p^{z}-1)
< p^{z}.

Hence, if we wish to force x= C_{y}^{z} &
z<=y by putting Diophantine conditions, we may try to put

z<=y & **E**p**E**u**E**v (p=3^{y}+1
& (1+p)^{y} = u + (x + vp)p^{z} & x<p
& u<p^{z}). --------(2)

We have already established, x= C_{y}^{z}
& z<=y implies (2). The converse also is true. Indeed,
according to (2), we can compute the value of u as (1+p)^{y}
mod p^{z}, and the value of x - as ((1+p)^{y}-u)/p^{z}
mod p. This is the way C_{y}^{z} is computed (see
above), hence x= C_{y}^{z}.

**Exercise 4.16.** Transform (2) into a Diophantine
representation E(P=0). Determine the number of quantifiers E, the
order and the sum of coefficient modules of the polynomial P.

Now let follow another idea due to Julia Robinson to obtain a Diophantine representation of the predicate x=y!. As you may know:

C_{w}^{y} =
w(w-1)...(w-y+1)/y!.

If w would be much greater than y, then the product
w(w-1)...(w-y+1) would be "approximately" w^{y},
and hence, y! would be "approximately" w^{y}/C_{w}^{y}.
Let us examine this fraction more closely:

w^{y}/C_{w}^{y} = y!
(w/w) (w/(w-1)) ... (w/(w-y+1)).

Let us replace w, w-1, ..., w-y+1 by w-y, then we will have:

y! <= w^{y}/C_{w}^{y}
<= y!(w/(w-y))^{ y} = y!(1+y/(w-y))^{ y}.

Now, take w=y+yt:

y! <= w^{y}/C_{w}^{y}
<= y!(1+1/t)^{ y} = y!(1+sum{ C_{y}^{i }t
^{-i} | for i=1 to y}).

Since C_{y}^{i} <= 2^{y}, let us
take t=u2^{y}, then

y! <= w^{y}/C_{w}^{y}
<= y!(1+y/u).

And finally, by taking u=2yy^{y} we will have (since
y!<=y^{y}):

y! <= w^{y}/C_{w}^{y}
<= y!+1/2.

Hence, if w=y+2y^{2}2^{y}y^{y}, then
y! can be computed as the integer part of the fraction w^{y}/C_{w}^{y},
and we can represent the predicate x=y! as

**E**w(w=y+2y^{2}2^{y}y^{y}
& x=integer(w^{y}/C_{w}^{y})).
--------(3)

**Exercise 4.17.** Transform (3) into a Diophantine
representation E(P=0). Determine the number of quantifiers E, the
order and the sum of coefficient modules of the polynomial P.

**Exercise 4.18.** Build a Diophantine representation of
the predicate "x is prime number". **Hint**
(J.Robinson, 1952): x is prime, iff x and (x-1)! do not have
common divisors. You can use also Wilson's
theorem: x is prime number <-> x>1 & (x-1)!+1 is
divisible by x. Which way is better?

Putnam's idea (Exercise 4.3) allows to obtain from this
representation a polynomial Q(x_{1}, ..., x_{n})
such that the set of positive values of Q is exactly the set of
all prime numbers. Hence, despite the current number-theoretic
intuition of 1969 some kind of a "formula for prime
numbers" does exist!

Now we have arrived at our target - producing a method that will allow converting any formula

(Az<U)Ex_{1}...Ex_{n} P(b_{1},
..., b_{k}, z, x_{1}, ..., x_{n})=0,
--------(1)

where U is a linear function of b_{1}, ..., b_{k}
with natural coefficients, into an equivalent formula

Ey_{1}...Ey_{q} Q(b_{1},
..., b_{k}, y_{1}, ..., y_{q})=0.

We will follow mainly the 1961 paper by Davis, Putnam and Julia Robinson with some later improvements proposed by Matiyasevich and Julia Robinson.

For any fixed values of b_{1}, ..., b_{k} the
formula (1) is an **existential assertion** (despite the
universal quantifier Az<U) - it asserts the existence of U*n
numbers: the values of x_{1}, ..., x_{n} for each
z = 0, 1, ..., U-1. Let us denote these U*n numbers by x_{i}^{(z)}:

for z=0: x_{1}^{(0)}, x_{2}^{(0)},...,
x_{n}^{(0)},

for z=1: x_{1}^{(1)}, x_{2}^{(1)},...,
x_{n}^{(1)},

...

for z=U-1: x_{1}^{(U-1)}, x_{2}^{(U-1)},...,
x_{n}^{(U-1)}.

We could eliminate the universal quantifier Az<U, if we
could find some coding that allowed to represent this table by a
sequence of m natural numbers y_{1}, ..., y_{m}
(where m does not depend on U). Then we could try to replace
Az<U by Ey_{1}...Ey_{m} (plus solving, of
course, all the other remaining technical problems).

For example, let us try to code each of the n columns of our
table by a single number using the Chinese Remainder theorem. If
we had numbers u_{0}, u_{1}, ..., u_{U-1}
such that two of them never had common divisors, then we could
obtain n numbers w_{1}, ..., w_{n} such that each
x_{i}^{(z)} would be w_{i} mod u_{z},
i.e.

x_{i}^{(z)}<u_{z}
& wi = x_{i}^{(z)} mod u_{z} --------(2)

for all z<U and i = 1, ..., n. Of course, the numbers u_{z}
must be large enough to serve this purpose.

Still, even if we will succeed in finding u_{0}, u_{1},
..., u_{U-1}, then how to force the remainders x_{1}^{(z)},
..., x_{n}^{(z)} to satisfy the equation of (1)
for all z = 0, 1, ..., U-1? Let us simply try to substitute the
numbers w_{1}, ..., w_{n} for x_{1}, ...,
x_{n} into the equation of (1). For z let us substitute
some number Z to be determined later. What could we say about the
value of P(b_{1}, ..., b_{k}, Z, w_{1},
..., w_{n})? If we added to (2) the condition

Z = z mod u_{z} for all z = 0, 1, ...,
U-1, ---------(3)

then we could conclude that

P(b_{1}, ..., b_{k}, Z, w_{1},
..., w_{n}) = P(b_{1}, ..., b_{k}, z, x_{1}^{(z)},
..., x_{n}^{(z)}) mod u_{z}.

Since all the right hand side values of P are 0, we obtain that

P(b_{1}, ..., b_{k}, Z, w_{1},
..., w_{n}) = 0 mod u_{z}

for all z<U, i.e. the left hand side number is divisible by
all the numbers y_{z}. Since two of these numbers never
have common divisors, the left hand side number is divisible also
by the product of them, i.e.

P(b_{1}, ..., b_{k}, Z, w_{1},
..., w_{n}) = 0 mod u_{0}u_{1}...u_{U-1}.
----------(4)

Now let us view (4) not as a consequence of some assumptions,
but as a **condition** that is put on the numbers w_{1},
..., w_{n}. If the numbers x_{i}^{(z)}
are defined as w_{i} mod u_{z}, then from (2),
(3) and (4) we obtain that for all z<U:

P(b_{1}, ..., b_{k}, z, x_{1}^{(z)},
..., x_{n}^{(z)}) = 0 mod u_{z}.

We would like to force an "absolute" 0 on the right
hand side instead of 0 mod u_{z}. This would be achieved,
if the left hand side number would be less than u_{z}.

**Exercise 4.19.** Let N be the order of the polynomial P,
M - the sum of its coefficient modules, z<U, and let X exceed
all x_{i}^{(z)}. Verify that

|P(b_{1}, ..., b_{k}, z, x_{1}^{(z)},
..., x_{n}^{(z)})| <= T,

where T = M((b_{1}+1)...(b_{k}+1)U(X+1))^{N}.

Hence, we must produce a (possibly simple) generator of
divisors u_{z} (z = 0, 1, ..., U-1) such that:

a) u_{z} > T for all z<U.

b) The module of (4), i.e. the product u_{0}u_{1}...u_{U-1}
is a possibly simple (i.e. "Diophantine") function.
Otherwise we will have problems with finding a Diophantine
representation of u_{0}u_{1}...u_{U-1}.

c) Two of the numbers u_{z} never have common
divisors.

The following idea of producing u_{z} is due to
Matiyasevich and Julia Robinson. Let V be a large number (to
start let U<=V), then we can generate u_{z} in such a
way that u_{0}u_{1}...u_{U-1} = C_{V}^{U}
(i.e. b) will be satisfied). Indeed,

C_{V}^{U} = V(V-1)...(V-U+1)/U!
= ((V+1)/1-1)((V+1)/2-1)...((V+1)/U-1).

Let us take

u_{z} = (V+1)/(z+1)-1.

If we put the condition "V+1 is divisible by U!",
then all u_{z} will be integer numbers. If we put a
stronger condition "V+1 is divisible by (U!)^{2}",
then two of these numbers never have common divisors (i.e. c) is
satisfied).

**Exercise 4.20.** Verify that this is the case. (**Hint**:
let d be a common prime divisor of u_{i} and u_{j},
consider u_{i} and u_{i}-u_{j}.)

If we put also the condition u_{U-1}>T (note that u_{U-1}
is the least of all u_{z}), i.e.

u_{U-1} > M((b_{1}+1)...(b_{k}+1)U(X+1))^{N},

then a) also is satisfied.

Now let us sum up all the conditions we have put on the
numbers we have introduced, i.e. w_{1}, ..., w_{n},
Z, X, V:

**G**_{1}**:** P(b_{1}, ..., b_{k},
Z, w_{1}, ..., w_{n}) = 0 mod C_{V}^{U},

**G**_{2}**:** (Az<U) Z = z mod u_{z},

**G**_{3i}**:** (Az<U) w_{i}
mod u_{z} < X for each i = 1, ..., n,

**G**_{4}**:** u_{U-1} > M((b_{1}+1)...(b_{k}+1)U(X+1))^{N},

**G**_{5}**:** V+1 is divisible by (U!)^{2},

where, of course, u_{z} = (V+1)/(z+1)-1.

About G_{3i}: since T depends on X, we must ensure
also: w_{i} mod u_{z} < X for all z<U and i
= 1, ..., n (otherwise the estimate of the exercise 4.19 will not
hold).

**Exercise 4.21.** Verify that (1) is equivalent to the
following formula:

**E**Z**E**X**E**V**E**w_{1}...**E**w_{n}
G_{1} & G_{2} & G_{4} & G_{5}
& G_{31} & ... & G_{3n}. -------(5)

(**Hints.** Rightwards: first choose X to satisfy G_{3i}'s,
then choose V to satisfy G_{5} and G_{4},
generate the divisors u_{z}, obtain the number Z by using
Chinese Remainder theorem to satisfy G_{2}, obtain the
numbers w_{1}, ..., w_{n} by using Chinese
Remainder theorem to satisfy (2), and finally, derive G_{1}.
Leftwards: having the numbers w_{1}, ..., w_{n},
Z, X, V take for each z<U: x_{i}^{(z)} = w_{i}
mod u_{z}, etc.)

Why should we view (5) as a step forward from (1), when G_{2}
and G_{3i }contain the same quantifier Az<U? In (1)
this quantifier stands over an arbitrary Diophantine
representation, but in G_{2} and G_{3i} it stands
over simple specific formulas!

First, we need not to eliminate Az<U from G_{2}, we
can eliminate the entire G_{2}. Indeed, we can take Z
equal to V: since V-z is divisible by

u_{z} = (V+1)/(z+1)-1 = (V-z)/(z+1)

(the fraction is equal to z+1), we have V = z mod u_{z}
for all z<U.

So, we can delete G_{2} from our list of conditions,
replace G_{1} by

**G**_{1}**':** P(b_{1}, ..., b_{k},
V, w_{1}, ..., w_{n}) = 0 mod C_{V}^{U},

and delete the quantifier **E**Z from (5).

Now let us set to eliminating Az<U from G_{3i}. If
w_{i} mod u_{z} < X, then one of the numbers w_{i},
w_{i}-1, ..., w_{i}-X+1 is divisible by u_{z},
i.e. their product

w_{i} (w_{i}-1)...(w_{i}-X+1)
= w_{i}!/(w_{i}-X)! --------(6)

also is divisible by u_{z} for all z<U. Since two
of the numbers u_{z} never have common divisors, the
number w_{i}!/(w_{i}-X)! is divisible by their
product u_{0}u_{1}...u_{U-1} = C_{V}^{U}.
Hence, if G_{3i}, then

**G**_{3i}**':** w_{i}!/(w_{i}-X)!
is divisible by C_{V}^{U}.

Thus we have got rid of the quantifier Az<U by introducing
well-known functions! Still, unfortunately, G_{3i}' does
not imply G_{3i}, i.e. these conditions are not
equivalent! Indeed, if we know only that the product (6) is
divisible by another product C_{V}^{U}, then we
cannot guarantee that for each z<U the factor u_{z}
will divide one of the factors w_{i}, w_{i}-1,
..., w_{i}-X+1.

If the number R divides the product P_{1}P_{2}...P_{k},
then R=R_{1}R_{2}...R_{k}, where each
factor R_{i} divides the corresponding P_{i}. If
R_{j} is maximum among the factors R_{i}, then R_{j}^{k}>=R,
i.e. R_{j}>=root_{k}(R). Hence, if R divides
the product P_{1}P_{2}...P_{k}, then R
and one of the factors P_{j }have a common divisor >=
root_{k}(R). This is maximum we can guarantee!

Thus, if we replace G_{3i} by G_{3i}', then we
can guarantee only that some w_{i}-j (where 0<=j<X)
and u_{z} have a common divisor >= root_{X}(u_{z}).
Fortunately, this is enough to solve our problem completely!

Indeed, for a fixed z<U let us proceed from w_{1}
to w_{n} in the following way. We know that the product w_{1}(w_{1}-1)...(w_{1}-X+1)
always is divisible by u_{z}. Then, first, for some
number x_{1}^{(z)}<X the difference w_{1}-
x_{1}^{(z)} is divisible by some divisor S_{1}>=root_{X}(u_{z})
of the number u_{z}. Of course, the product w_{2}(w_{2}-1)...(w_{2}-X+1)
also is divisible by S_{1}. Hence, next, for some number
x_{2}^{(z)}<X the difference w_{2}- x_{2}^{(z)}
is divisible by some divisor S_{2}>=root_{X}(S_{1})>=root_{X}2(u_{z})
of the number S_{1} (and of u_{z}). Etc.,
finally, for some number x_{n}^{(z)}<X the
difference w_{n}-x_{n}^{(z)} is divisible
by some divisor S_{n}>=root_{X}(S_{n-1})>=root_{X}n(u_{z})
of the number S_{n-1} (and of u_{z}).

Hence, for all i = 1, ..., n:

w_{i} = x_{i}^{(z)} mod
S_{n}, -------(7)

where S_{n} divides u_{z} (and hence, C_{V}^{U}),
and S_{n}>=root_{X}n(u_{z}). From G_{1}'
we have:

P(b_{1}, ..., b_{k}, V, w_{1},
..., w_{n}) = 0 mod S_{n},

hence, by (7) and, since V = z mod u_{z},

P(b_{1}, ..., b_{k}, z, x_{1}^{(z)},
..., x_{n}^{(z)}) = 0 mod S_{n}.

Since z<U and all x_{i}^{(z)}<X, the
left hand side value of P does not exceed

T = M((b_{1}+1)...(b_{k}+1)U(X+1))^{N}.

Hence, this value of P will be forced to be an
"absolute" 0, if root_{X}n(u_{z}) will
be greater than T. Thus, we must replace G_{4} by a
stronger condition

**G**_{4}**':** root_{X}n(u_{U-1})
> M((b_{1}+1)...(b_{k}+1)U(X+1))^{N},

and our problem finally is 100% solved!

**Exercise 4.22.** Verify once more that (1) is equivalent
to the formula

**E**X**E**V**E**w_{1}...**E**w_{n}
G_{1}' & G_{4}' & G_{5} & G_{31}'
& ... & G_{3n}'.

Transform this formula into a Diophantine representation.

Q.E.D.

Further reading:

Hilbert's 10th problem database in St. Petersburg

Hilbert's 10th Problem. By Yuri Matiyasevich. MIT Press, 1993, 288 pp. For details see http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook (Russian original available).

Yuri Matiyasevich. A direct method for simulating partial recursive functions by Diophantine equations. Annals of Pure and Applied Logic, 67(1-3): 325-348, 17 May 1994 (see http://theory.lcs.mit.edu/~dmjones/hbp/apal/apal94.html)

Section 6.5 (about "Diophantine incompleteness theorem")

Back to title page.