9.4 EXPONENTIATION

In this section we show that the function m^{n} is diophantine, thus completing the proof of the main theorem. We have to begin by considering the behaviour of the solutions to some difference equations.

Let a be an integer greater than 1. Define x_{n} and y_{n} by

\begin{matrix}x_{n+1} = 2ax_{n} − x_{n−1}, & x_{0} = 1, & x_{1} = a, \\ y_{n+1} = 2ay_{n} − y_{n−1}, & y_{0} = 1, & y_{1} = 1. \end{matrix}

When the parameter a needs consideration we refer to these as x_{n}(a) and y_{n}(a).

Let d = a^{2} − 1; then \sqrt{d} is irrational. It follows that if m + n\sqrt{d} = u + v\sqrt{d} then m = u and n = v, and so we also have m − n\sqrt{d} = u − v\sqrt{d}.

(I) It is easy to see, by induction, that x_{n} ± y_{n}\sqrt{d} = (a ± \sqrt{d})^{n}. Since (a + \sqrt{d})(a − \sqrt{d}) = 1, we also have that x_{n} − y_{n}\sqrt{d} = (a + \sqrt{d})^{−n}. Hence x_{n}^{2} − dy_{n}^{2} = 1.

(II) Conversely, we show that any solution of x^{2} − dy^{2} = 1 with x and y in N must satisfy x = x_{n} and y = y_{n} for some n. Observe first that there must be some n with (a + \sqrt{d})^{n} ≤ x + y\sqrt{d} < (a + \sqrt{d})^{n+1}. Let u + v\sqrt{d} be (x + y\sqrt{d})(a − \sqrt{d})^{n}, so both u and v are integers. We also have u − v\sqrt{d} = (x − y\sqrt{d})(a + \sqrt{d})^{n}, and so u^{2} − dv^{2} = x^{2} − dy^{2} = 1.

Since (a − \sqrt{d})^{n} = (a + \sqrt{d})^{−n}, we have 1 ≤ u + v\sqrt{d} < a + \sqrt{d}. Taking the inverse of these inequalities and changing sign, we find that −1 ≤ −u + v\sqrt{d} < −a + \sqrt{d}. Adding these to the original inequalities then gives 0 ≤ 2v\sqrt{d} < 2\sqrt{d}. Hence v = 0, and so u = 1, since u^{2} − dv^{2} = 1. It follows that x + y\sqrt{d} = (a + \sqrt{d})^{n}, so x = x_{n} and y = y_{n}, as required.

(III) It follows easily from the equalities x_{n} ± y_{n}\sqrt{d} = (a ± \sqrt{d})^{n} = (a + \sqrt{d})^{±n} that x_{m±n} + y_{m±n}\sqrt{d} = (x_{m} + y_{m}\sqrt{d})(x_{n} + y_{n}\sqrt{d}), and hence that we have the addition formulas x_{m±n} = x_{m}x_{n} ± dy_{m}y_{n}, and y_{m±n} = x_{n}y_{m} ± x_{m}y_{n}. In particular x_{n±1} = ax_{m} ± dy_{m}, y_{m±1} = ay_{m} ± x_{m}. It follows that y_{m+1} > y_{m}, and hence that y_{m} ≥ m for all m.

(IV) We denote the greatest common divisor of two integers r and s by (r, s). Since x_{n}^{2} − dy_{n}^{2} = 1, we see that (x_{n}, y_{n}) = 1. By induction on k, using the addition formulas, we see that y_{n}|y_{nk} for all n and k, where r|s means that r divides s.

(V) We can now deduce the y_{n}|y_{t} iff n|t. The previous remark gives the result if n|t. Assume that y_{n}|y_{t} and that n does not divide t. Write t as nq + r, where 0 < r < n. Since y_{t} = x_{r}y_{nq} + x_{nq}y_{r}, and we already know that y_{n} divides y_{n}q, we see that y_{n}|x_{nq}y_{r}. As (y_{nq}, x_{nq}) = 1, and y_{n}|y_{nq}, it follows that y_{n}|y_{r}. But we know that y_{r} < y_{n}, a contradiction.

(VI) We next show that y_{nk} ≡ kx_{n}^{k−1}y_{n} mod y_{n}^{3}. To see this, we write x_{nk} + y_{nk}\sqrt{d} as (x_{n} + y_{n}\sqrt{d})^{k}. Expanding this by the binomial theorem, and equating the terms involving \sqrt{d} gives the result.

(VII) It follows immediately that if k = y_{n} then y_{n}^{2}|y_{nk}. As a partial converse to this we show that y_{n}|t if y_{n}^{2}|y_{t}. We already know that n|t, since y_{n}|y_{t}. Write t as nk. Then we know that y_{n}^{2} must divide kx_{n}^{k−1}y_{n}, so that y_{n} divides kx_{n}^{k−1}. Since (y_{n}, x_{n}) = 1, this tells us that y_{n} divides k.

(VIII) From the difference equation, easy inductions (the initial cases when n is 0 or 1 being obvious) give the following results. y_{n} ≡ n mod 2, and y_{n} ≡ n mod (a − 1). Also if a ≡ b mod c we find that, mod c, x_{n}(a) ≡ x_{n}(b) and y_{n}(a) ≡ y_{n}(b).

(IX) We now show that x_{2n±j} ≡ −x_{j} mod x_{n}, and hence x_{4n±j} ≡ x_{j} mod x_{n}. For the addition formula tells us that x_{2n±j} ≡ x_{n}x_{n±j} + dy_{n}y_{n±j} ≡ dy_{n}(y_{n}x_{j} ± x_{n}y_{j}) ≡ dy_{n}^{2}x_{j} ≡ (x_{n}^{2} − 1)x_{j} ≡ −x_{j}.

(X) The most difficult of our results, is the following. Let x_{i} ≡ x_{j} mod x_{n}, with i ≤ j ≤ 2n and n > 0. Then i = j, unless a = 2, n = 1, i = 0, and j = 2.

We first suppose that x_{n} is odd, and let q = (x_{n} − 1)/2. Then no two of the numbers −q, …, q are congruent mod x_{n}, and every integer is congruent to one of them. Now we know that 1 = x_{0} < x_{1} < … < x_{n−1}, and that x_{n−1} ≤ x_{n}/a ≤ x_{n}/2. In particular x_{n−1} ≤ q. Also we know that the numbers x_{n+1}, …, x_{2n} are congruent mod x_{n} to −x_{n−1}, …, −x_{0}, by the previous result. Hence the numbers x_{0}, …, x_{2n} are mutually incongruent mod x_{n}.

When x_{n} is even, we let q be x_{n}/2. In this case −q ≡ q mod x_{n}. The result will follow as before unless x_{n−1} = q; this possiblity would give x_{n+1} = −q. However this case requires x_{n} = 2x_{n−1}, and, as we know that x_{n} = ax_{n−1} + dy_{n−1}, we must have a = 2 and y_{n−1} = 0, so that n = 1, as needed.

The previous result can be extended to show that if x_{j} ≡ d_{i} mod x_{n}, with 0 < i ≤ n and 0 ≤ j < 4n, then either j = i or j = 4n − i. For if j ≤ 2n, we get i = j unless we are in the exceptional case. Since i is not 0, we would then have i = 2, j = 0, and n = 1, contradicting i ≤ n, so this case cannot happen. If j > 2n define k as 4n − j. Then k > 0, and x_{k} = x_{j} = x_{i} mod x_{n}. As 0 < k < 2n, we cannot be in the exceptional case, and so must have k = i.

It follows at once that if 0 < i ≤ n and x_{i} ≡ x_{j} mod x_{n} then j ≡ ±i mod 4n. For we need only write j as 4nq + k, where 0 ≤ k < 4n and use the previous result and the fact that x_{4n+r} ≡ x_{r} for all r.

We are now in a position to prove the main results.

Proposition 9.9 The function y_{k}(a) is diophantine.

Proof We show that, provided k is non-zero (the general case can be obtained from this, but is not needed) y = y_{k}(a) iff a > 1 (else y_{k}(a) is not defined) and there are positive integers x, u, v, s, t, b, r, p, q, c, and d satisfying the following eight equations.

x^{2} − (a^{2} − 1)y^{2} = 1  (1)
u^{2} − (a^{2} − 1)v^{2} = 1  (2)
s^{2} − (b^{2} − 1)t^{2} = 1  (3)
v = ry^{2}  (4)
b = 1 + 4py = a + qu  (5)
s = x + cu  (6)
t = k + 4(d − 1)y  (7)
y ≥ k.  (8)

First suppose the equations have a solution. As the variables are not zero, there will, by (II), be a positive i, j, and n such that x = x_{i}(a), y = y_{i}(a), u = x_{n}(a), v = y_{n}(a), s = x_{j}(b), and t = y_{i}(b). By (4), y ≤ v, and so i ≤ n. Form (5), b ≡ amodx_{n}(a), from which we know, by (VII), that x_{j}(b) ≡ x_{j}(a)modx_{n}(a). From (t) we have x_{j}(b) ≡ x_{i}(a) mod x_{n}(a). Hence we have x_{j}(a) ≡ x_{i}(a) mod x_{n}(a), so (X) tells us that j ≡ ±i mod 4n.

Equation (4) tells us that y_{i}(a)^{2}|y_{n}(a), from which we know that y_{i}(a)|n. Hence j ≡ ±i mod 4y_{i}(a). We know that y_{j}(b) ≡ j mod (b − 1). By (5), b ≡ 1 mod 4y_{i}(a), so that y_{j}(b) ≡ j mod 4y_{i}(a). By (7), we

have y_{j}(b) ≡ k mod 4y_{i}(a). Consequently k ≡ ±i mod 4y_{i}(a).

However, we know that i ≤ y_{i}(a), and condition (8) tells us that k ≤ y_{i}(a). The congruence then requires that i = k. As i is defined to satisfy y = y_{i}(a), we have, as required, y = y_{k}(a).

Conversely, suppose that y = y_{k}(a). Set x to be x_{k}(a), so that (1) holds. Let m = 2ky_{k}(a), and define u = x_{m}(a), v = y_{m}(a). Then (2) holds. We find that y^{2}|v, since we have that y^{2}|y_{m/2}(a), and the latter divides y_{m}(a). Hence we can find r satisfying (4). Since m is even, we know from (VIII) that v is even, and hence u is odd.

As u is odd and (u, v) = 1, adn y divides v, we find that (u, 4y) = 1. By the Chinese Remainder Theorem (Theorem 9.11 below) there is a non-negative b_{0} satisfying b_{0} ≡ 1mod4y and b_{0} ≡ amodu. Adding a suitable multiple of 4uy to b_{0}, we can find positive b, p and q satisfying (5). Then (3) is satisfied by putting s and t to be x_{k}(b) and y_{k}(b).

Since b > a, we have s > x, as s = x_{k}(b) and x = x_{k}(a). It also follows, since b ≡ a mod u, that s ≡ x mod u. Hence we can choose c to satisfy (6).

Since t is y_{k}(b), we know that t ≥ k and t ≡ k mod (b − 1). By (5) we have that t ≡ k mod 4y, so that (7) can be satisfied. Finally (8) holds, since y = y_{k}(a). •

Theorem 9.10 The function a^{n} is diophantine.

Proof It is most convenient to assume that n > 0 and a > 1. We do not need the general case; it can be obtained by a simple modification.

We define Near(u, v) to be the nearest integer to v/u. The function Near is diophantine, since Near(u, v) = w iff (2rem(u, v) ≤ u ∧ w = quo(u, v)) ∨ (2rem(u, v) > u ∧ w = quo(u, v) + 1).

We shall show that a^{n} = Near(y_{n+1}(k), y_{n+1}(ka)) provided k is large enough. By the previous proposition, a^{n} will be diophantine if the requirement that k is large enough can be expressed as a diophantine condition.

It is ease to check, by induction, that, for any b > 1 and any n, (2b − 1)^{n} ≤ y_{n+1}(b) ≤ (2b)^{n}. Apply this for b = ka and for b = k, and divide the inequalities. We find that y_{n+1}(ka)/y_{n+1}(k) lies between (2ka−1)^{n}/(2k)^{n} = a^{n}(1−1/2ka)^{n} and (2ka)^{n}/(2k−1)^{n} = a^{n}(1−1/2k)^{−n}. Hence Near(y_{n+1}(k), y_{n+1}(ka)) = a^{n} if (1 − 1/2ka)^{n} > 1 − 1/2a^{n} and (1 − 1/2k)^{−}n < 1 + 1/2a^{n}.

Since y_{n+1}(a) ≥ (2a − 1)^{n} > a^{n}, it is enough to require that (1 − 1/2ka)^{n} > 1 − 1/2y_{n+1}(a) and (1 − 1/2k)^{−n} < 1 + 1/2y_{n+1}(a), and the latter condition can be written as (1 − 1/2k)^{n} > (1 + 1/2y_{n+1}(a))^{−1}.

Now (1 − x)^{n} > 1 − nx for any real x between 0 and 1 (because (1 − x)^{n} + nx ahs a positive derivative). Hence the required conditions hold provided that 1 − n/2ka > 1 − 1/2y_{n+1}(a) and 1 − n/2k > (1 + 1/2y_{n+1}(a))^{−1}. These two conditions, when cleared of fractions, are diophantine conditions, since y_{n+1}(a) is diophantine. •