Discrete Mathematics for Computer Science

258 CHAPTER 4 Functions

Study the example for finding the decimal expansion of the rational number 3/7, as

shown in Figure 4.24, to gain an insight regarding how the formal proof that follows will

proceed.

.42857 1 4...

7) 3.0000000...

28

20

14

60

56

40

35

50

49

10

7

30

Figure 4.24 Long division to calculate decimal expansion of 3/7.

The decimal expansion of 3/7 can be seen to repeat. After the sixth decimal place

has been calculated, the remainder is 3, and the rest of the division process corresponds

to dividing 7 into 0.000003. That is the same process as dividing 7 into 3, except that it is

shifted six decimal places to the right. Therefore, exactly the same sequence of quotients

and remainders will be generated as before, causing the sequence to repeat.

The ideas shown in these examples will now be incorporated into the general result

about the existence of repeating decimal expansions for rational numbers.

Theorem 7. A real number is rational if and only if it has a repeating decimal expansion.

Proof.

(::-) Suppose a real number r is rational. Show that it has a repeating decimal expansion.

First, express r as the fraction j/k where 0 < j < k. Now, consider the long division of k

into j. (For an illustration, look again at the computation of the decimal expansion of 3/7

in Figure 4.24.) The first division produces one digit (the tenths digit) of the quotient and

a remainder rl < k. The remainder is contained in {0, 1 ... , k - 1}. To prepare for the

next division, concatenate a 0 on the the end of ri. Now, repeat the procedure to calculate

another digit (the hundredths) of the quotient and another remainder r2 < k, follow this by

concatenating another 0 on the end of r2, repeat again, and so on.

The only k possible remainders at each step are 0, 1, 2 .... and k - 1. Hence, after

at most k + 1 steps of the division, two of the remainders must be equal. Then, however,

the process must start repeating, as in the previous illustrations. It is important that at the

end of each step, the same digit, 0, and not any other digit, is always concatenated onto

the remainder. The digit concatenated is always 0, because j and k are both integers and

0 < j < k. This guarantees that when remainders are equal, the entire process repeats. So,

r has a repeating decimal expansion.

(4=) Suppose a real number r has a repeating decimal expansion. Again, for convenience,

we will limit the proof to decimals in the interval (0, 1). For illustration, use