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

  • Denominators Relatively Prime to the Base. Finally we consider the general case which combines the two, Denominators in General.
    1. Denominitors Absolutely Not Relatively Prime to the Base
    2. Denominators Relatively Prime to the Base
    3. Denominators in General

    Denominitors Absolutely Not Relatively Prime to the Base

    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 base is 10 = 2 * 5, and if our denominator is 200 = 23 * 52, then 1/200 will terminate. This is because 200 will divide into a large enough power of 10 (or whatever our base is):

    Or looking at it another way, we multiply by 10 / 10 = 1 until the denominator cancels out and we get an integer:

    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.

    Denominators Relatively Prime to the Base

    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 related to 1/(basen-1). If we can show that any number relatively prime to the base can divide (basen-1) for some n, 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 n which are relatively prime to n. This totient is used in Euler's Totient Theorem:

    • aφ(n) === 1 (mod n) for all a relatively prime to n

    (=== is being used here to represent "is congruent to".)

    If we take a to be our base 10, and 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 portion (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/7 = 0.142857)
    •        = 1 +     (857,142 / 999,999)
    •        = 1.857142

    6 < 7, so when we expand the denominator to 999,999 (106-1), 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 k places, 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.

    Denominators in General

    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*s where 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 n.

    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 (1/10k), s has been transformed into the numerator (in combination with n), and 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 x digits (we know that the final result is less than 1) which is simply being shifted x times. This is a static portion in the first x digits 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
    •         = 0.303571428

    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.