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

- Denominitors Absolutely Not Relatively Prime to the Base
- Denominators Relatively Prime to the Base
- Denominators in General

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 = 2`

,
then ^{3} * 5^{2}`1/200`

will terminate. This is because `200`

will divide into a large enough
power of `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`

`= .005`

```
```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/(base`^{n}-1)

. If we can show that any number relatively
prime to the base can divide `(base`^{n}-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 `(base`^{x}-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`

(`10`^{6}-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
`1`^{st} 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/10`^{k}

), `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 / (2`^{3} * 7)

```
= [5
```^{3} / 5^{3}] * [17 / (2^{3} * 7)]

```
= [1 / 10
```^{3}] * [(5^{3} * 17) / 7]

```
= [1 / 10
```^{3}] * [125 * 17 / 7]

```
= [1 / 10
```^{3}] * [2125 / 7]

The remaining fraction on the right should now be broken up into an integer and a proper fraction:

```
= [1 / 10
```^{3}] * [2125 / 7]

```
= [1 / 10
```^{3}] * [303 + (4 / 7)]

And finally we distribute the "shift":

```
= [1 / 10
```^{3}] * [303 + (4 / 7)]

```
= 303 / 10
```^{3} + 4 /(10^{3} * 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 / 10`^{3} + 4 /(10^{3} * 7)

```
= 303 / 10
```^{3} + 0.571428 / 10^{3}

```
= 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.