4.5 Rational reconstruction and applications 69

0 ¤ r ¤ r— and 0 < t ¤ t— . We claim that

r ≡ ty (mod n). (4.9)

To show that (4.9) holds, it su¬ces to show that

tz ≡ ty (mod ni ) (4.10)

for all i = 1, . . . , k. To show this, for each index i we consider two cases:

Case 1: i ∈ G. In this case, we have ai = ai , and therefore,

˜

tz ≡ tai ≡ t˜i ≡ ty (mod ni ).

a

Case 2: i ∈ B. In this case, we have ni | t, and therefore,

tz ≡ 0 ≡ ty (mod ni ).

Thus, (4.10) holds for all i = 1, . . . , k, and so it follows that (4.9) holds.

Therefore, the values r , t obtained from Theorem 4.6 satisfy

r r tz

== = z.

t t t

One easily checks that both the procedures to encode and decode a value

z run in time O(len(n)2 ). If one wanted a practical implementation, one

might choose n1 , . . . , nk to be, say, 16-bit primes, so that the encoding of a

value z consisted of a sequence of k 16-bit words.

The above scheme is an example of an error correcting code, and is

actually the integer analog of a Reed“Solomon code.

4.5.2 Application: recovering fractions from their decimal

expansions

Suppose Alice knows a rational number z := s/t, where s and t are integers

with 0 ¤ s < t, and tells Bob some of the high-order digits in the decimal

expansion of z. Can Bob determine z? The answer is yes, provided Bob

knows an upper bound T on t, and provided Alice gives Bob enough digits.

Of course, from grade school, Bob probably remembers that the decimal

expansion of z is ultimately periodic, and that given enough digits of z so

as to include the periodic part, he can recover z; however, this technique is

quite useless in practice, as the length of the period can be huge ” ˜(T ) in

the worst case (see Exercises 4.8“4.10 below). The method we discuss here

requires only O(len(T )) digits.

To be a bit more general, suppose that Alice gives Bob the high-order k

70 Euclid™s algorithm

digits in the d-ary expansion of z, for some base d > 1. Now, we can express

z in base d as

z = z1 d’1 + z2 d’2 + z3 d’3 + · · · ,

and the sequence of digits z1 , z2 , z3 , . . . is uniquely determined if we require

that the sequence does not terminate with an in¬nite run of (d ’ 1)-digits.

Suppose Alice gives Bob the ¬rst k digits z1 , . . . , zk . De¬ne

y := z1 dk’1 + · · · + zk’1 d + zk = zdk .

Let us also de¬ne n := dk , so that y = zn .

Now, if n is much smaller than T 2 , the number z is not even uniquely

determined by y, since there are „¦(T 2 ) distinct rational numbers of the

form s/t, with 0 ¤ s < t ¤ T (see Exercise 1.18). However, if n ≥ 4T 2 ,

then not only is z uniquely determined by y, but using Theorem 4.6, we can

compute it as follows:

1. Run the extended Euclidean algorithm on inputs a := n and b := y,

and let s , t be as in Theorem 4.6, using r— := t— := T .

2. Output s , t .

We claim that z = ’s /t . To prove this, observe that since y = zn =

(ns)/t , if we set r := (ns) mod t, then we have

r = sn ’ ty and 0 ¤ r < t ¤ t— .

It follows that the integers s , t from Theorem 4.6 satisfy s = s ± and

’t = t ± for some non-zero integer ±. Thus, s /t = ’s/t, which proves the

claim.

We may further observe that since the extended Euclidean algorithm guar-

antees that gcd(s , t ) = 1, not only do we obtain z, but we obtain z expressed

as a fraction in lowest terms.

It is clear that the running time of this algorithm is O(len(n)2 ).

Example 4.3. Alice chooses numbers 0 ¤ s < t ¤ 1000, and tells Bob the

high-order seven digits y in the decimal expansion of z := s/t, from which

Bob should be able to compute z. Suppose s = 511 and t = 710. Then

s/t ≈ 0.71971830985915492958, and so y = 7197183 and n = 107 . Running

the extended Euclidean algorithm on inputs a := n and b := y, Bob obtains

the following data:

4.5 Rational reconstruction and applications 71

i ri qi si ti

0 10000000 1 0

1 7197183 1 0 1

2 2802817 2 1 -1

3 1591549 1 -2 3

4 1211268 1 3 -4

5 380281 3 -5 7

6 70425 5 18 -25

7 28156 2 -95 132

8 14113 1 208 -289

9 14043 1 -303 421

10 70 200 511 -710

11 43 1 -102503 142421

12 27 1 103014 -143131

13 16 1 -205517 285552

14 11 1 308531 -428683

15 5 2 -514048 714235

16 1 5 1336627 -1857153

17 0 -7197183 10000000

The ¬rst ri that meets or falls below the threshold 2r— = 2000 is at

i = 10, and Bob reads o¬ s = 511 and t = ’710, from which he obtains

z = ’s /t = 511/710. 2

Exercise 4.7. Show that given integers s, t, k, with 0 ¤ s < t, and k >

0, we can compute the kth digit in the decimal expansion of s/t in time

O(len(k) len(t)2 ).

For the following exercises, we need a de¬nition: a sequence S :=

(z1 , z2 , z3 , . . .) of elements drawn from some arbitrary set is called (k, )-

periodic for integers k ≥ 0 and ≥ 1 if zi = zi+ for all i > k. S is called

ultimately periodic if it is (k, )-periodic for some (k, ).

Exercise 4.8. Show that if a sequence S is ultimately periodic, then it

is (k — , — )-periodic for some uniquely determined pair (k — , — ) for which the

following holds: for any pair (k, ) such that S is (k, )-periodic, we have

k — ¤ k and — ¤ .

The value — in the above exercise is called the period of S, and k — is

called the pre-period of S. If its pre-period is zero, then S is called purely

periodic.

72 Euclid™s algorithm

Exercise 4.9. Let z be a real number whose base-d expansion is an ulti-

mately periodic sequence. Show that z is rational.

Exercise 4.10. Let z = s/t ∈ Q, where s and t are relatively prime integers

with 0 ¤ s < t, and let d > 1 be an integer.

(a) Show that there exist integers k, k such that 0 ¤ k < k and sdk ≡

sdk (mod t).

(b) Show that for integers k, k with 0 ¤ k < k , the base-d expansion of

z is (k, k ’ k)-periodic if and only if sdk ≡ sdk (mod t).

(c) Show that if gcd(t, d) = 1, then the base-d expansion of z is purely

periodic with period equal to the multiplicative order of d modulo t.

(d) More generally, show that if k is the smallest non-negative integer

such that d and t := t/ gcd(dk , t) are relatively prime, then the base-

d expansion of z is ultimately periodic with pre-period k and period

equal to the multiplicative order of d modulo t .

A famous conjecture of Artin postulates that for any integer d, not equal

to ’1 or to the square of an integer, there are in¬nitely many primes t such

that d has multiplicative order t ’ 1 modulo t. If Artin™s conjecture is true,

then by part (c) of the previous exercise, for any d > 1 that is not a square,

there are in¬nitely many primes t such that the base-d expansion of s/t, for

any 0 < s < t, is a purely periodic sequence of period t ’ 1. In light of these

observations, the “grade school” method of computing a fraction from its

decimal expansion using the period is hopelessly impractical.

4.5.3 Applications to symbolic algebra

Rational reconstruction also has a number of applications in symbolic alge-

bra. We brie¬‚y sketch one such application here. Suppose that we want to