We know that all repeating or terminating decimals are rational, but are all rationals either repeating or terminating? If they are, that would by corrolary mean that all irrational numbers do not terminate or repeat.
We'll first consider rationals that have denominators consisting of factors from the base. That is to say, any number that can divide the denominator can also divide the base. We call these Denominitors Absolutely Not Relatively Prime to the Base. Next we consider rationals with
If you think about it, it's easy to see that a denominator with no factors relatively prime
to the base you're using will result in a terminating decimal. For example, in decimal our
10 = 2 * 5, and if our denominator is
200 = 23 * 52,
1/200 will terminate. This is because
200 will divide into a large enough
10 (or whatever our base is):
1 / 200 = 5 / 1,000 = .005
Or looking at it another way, we multiply by
10 / 10 = 1 until the
denominator cancels out and we get an integer:
1 / 200 = (1/10) * 10 / 200 = (1/10) * 1 / 20
= (1/100) * 10 / 20 = (1/100) * 1 / 2
= (1/1,000) * 10 / 2 = (1/1,000) * 5
Note that the power of 10 in question determines how long the terminating decimal will be.
It doesn't matter if we have a numerator; that will just increase the number to be shifted once we've canceled out the denominator.
After the section above, it should be clear that denominators that are relatively prime to the base don't terminate: No matter how many times you multiply by the base, you can't get an integer. If all rationals do indeed terminate or repeat, these relatively prime denominators must repeat.
If you know how repeating decimals work, you know that they're
1/(basen-1). If we can show that any number relatively
prime to the base can divide
(basen-1) for some
we will have shown that the number repeats.
To prove this, we'll use Euler's Totient. The totient of
n is represented by
φ(n), and is defined as the number of positive integers less than
which are relatively prime to
n. This totient is used in Euler's Totient Theorem:
aφ(n) === 1 (mod n)for all
arelatively prime to
=== is being used here to represent "is congruent to".)
If we take
a to be our base
n to be the denominator, then:
10φ(n) === 1 (mod n)
10φ(n) - 1 === 0 (mod n)
n \ (
10φ(n) - 1)
Which is to say, all relatively prime denominators will go into
(basex-1) for some
x (if nothing else,
φ(n)). They repeat, snug against the decimal point.
If we have a numerator, the only thing we really need to look out for is if it is greater than the
denominator. In that case, it's best to seperate out the integer portion before tackling the fraction.
The remaining numerator will be less than the denominator, and won't be able to "escape" the repeating
x digits long) defined by the denominator. As way of an example:
13 / 7 = 1 + 6 / 7 = 1 + 6 * (1 / 7)
= 1 + 6 * (142,857 / 999,999)(Read:
= 1 + (857,142 / 999,999)
6 < 7, so when we expand the denominator to
the resulting numberator
857,142 is still less than the denominator. There is no carrying between
"repeating groups" or into the integer.
Note that the repeating portion, in this case, starts right after the decimal point. You could call this the
1st decimal position. If it were to be shifted to the right
it would begin at the
(1 + k)th decimal position.
The only trick remaining is a good way to find
x, the length of the repeating section.
This will be covered later, as knowing that it exists is good enough for the proof.
If a demoninator has both relatively prime and not relatively prime factors (to the base), we consider each set
of factors seperately. Let us say that our denominator is
r is relatively
prime to the base, and
s is absolutely not relatively prime to the base (that is, it has no factors
which are relatively prime to the base). It's also easier if we include a numerator from the start. Any
integer should have been removed already, similar to above. The numerator will be
When we had an absolutely not relative prime denominator, we simply canceled out
the denominator and shifted the result appropriately. We start out doing the same thing here -- but instead
of "canceling out" (making the denominator
1), we cancel out until the denominator is relatively
prime to the base. That is, we have some shifting fraction (
has been transformed into the numerator (in combination with
r is left on bottom.
Now's a good time to clarify by starting up an example:
17 / 56 = 17 / (23 * 7)
= [53 / 53] * [17 / (23 * 7)]
= [1 / 103] * [(53 * 17) / 7]
= [1 / 103] * [125 * 17 / 7]
= [1 / 103] * [2125 / 7]
The remaining fraction on the right should now be broken up into an integer and a proper fraction:
= [1 / 103] * [2125 / 7]
= [1 / 103] * [303 + (4 / 7)]
And finally we distribute the "shift":
= [1 / 103] * [303 + (4 / 7)]
= 303 / 103 + 4 /(103 * 7)
Now, let's look at what we have. On the left is a numerator with no more than
(we know that the final result is less than
is simply being shifted
x times. This is a static portion in the first
after the decimal point. On the right is a numerator less than the relatively prime
portion of the denominator. This will result in some repeating section, which will also be shifted over
x times. Therefore the repeating starts at the
(1 + x)th decimal
position, right after the static portion. The repeating portion will not overflow into the static
portion, because the numerator is smaller than the relatively prime portion of the denominator.
We can find out that:
4 / 7 = 4 * 1 / 7 = 4 * 142,857 / 999,999 = 571,428 / 999,999 = 0.571428
And now we know that:
17 / 56 = 303 / 103 + 4 /(103 * 7)
= 303 / 103 + 0.571428 / 103
= 0.303 + 0.000571428
We've shown that any rational with a "mixed" denominator (with factors both relatively prime to and not relatively prime to the base) can be broken into two non-interfering sections: One that terminates, and another that repeats. Since we've already shown that rationals with denominators absolutely not relatively prime to the base and rationals with denominators relatively prime to the base also either terminate or repeat, we have proven that all rationals either terminate or repeat. Moreover, we know that the non-relatively prime factors in the denominator result in static sections, and relatively prime factors result in repeating sections.