Thoughts on 1/7 and other rational numbers (Part 6)

In Part 5 of this series, I showed that fractions of the form $\displaystyle \frac{M}{10^d}$ , $\displaystyle \frac{M}{10^k - 1}$ , and $\displaystyle \frac{M}{10^d (10^k-1)}$ can be converted into their decimal representations without using long division and without using a calculator.

The amazing thing is that every rational number $\displaystyle \frac{a}{b}$ can be written in one of these three forms. Therefore, after this conversion is made, then the decimal expansion can be found without a calculator.

Case 1. If the denominator $b$ has a prime factorization of the form $2^m 5^n$ , then $\displaystyle \frac{a}{b}$ can be rewritten in the form $\displaystyle \frac{M}{10^d}$ , where $d = \max(m,n)$ .

For example,

$\displaystyle \frac{3}{160} = \displaystyle \frac{3}{2^5 \times 5}$

$\displaystyle \frac{3}{160} = \displaystyle \frac{3}{2^5 \times 5} \times \frac{5^4}{5^4}$

$\displaystyle \frac{3}{160} = \displaystyle \frac{3 \times 5^4}{2^5 \times 5^5}$

$\displaystyle \frac{3}{160} = \displaystyle \frac{1875}{10^5}$

$\displaystyle \frac{3}{160} = 0.01875$

The step of multiplying both sides by $\displaystyle \frac{5^4}{5^4}$ is perhaps unusual, since we’re so accustomed to converting fractions into lowest terms and not making the numerators and denominators larger. This particular form of $1$ was chosen in order to get a power of $10$ in the denominator, thus facilitating the construction of the decimal expansion.

Case 2. If the denominator $b$ is neither a multiple of $2$ nor $5$ , then $\displaystyle \frac{a}{b}$ can be rewritten in the form $\displaystyle \frac{M}{10^k - 1}$ .

For example,

$\displaystyle \frac{3}{11} = \displaystyle \frac{3}{11} \times \frac{9}{9}$

$\displaystyle \frac{3}{11} = \displaystyle \frac{27}{99}$

$\displaystyle \frac{3}{11} = 0.\overline{27}$

This example wasn’t too difficult since we knew that $9 \times 11 = 99$ . However, finding the smallest value of $k$ that works can be a difficult task requiring laborious trial and error.

However, we do have a couple of theorems that can assist in finding $k$ . First, since $k$ is the length of the repeating block, we are guaranteed that $k$ must be less than the denominator $b$ since, using ordinary long division, the length of the repeating block is determined by how many steps are required until we get a remainder that was seen before.

However, we can do even better than that. Using ideas from number theory, it can be proven that $k$ must be a factor of $\phi(b)$ , which is the Euler toitent function or the number of integers less than $b$ that are relatively prime with $b$ . In the example above, the denominator was $11$ , and clearly, if $1 \le n < 11$ , then $\gcd(n,11) = 1$ . Since there are $10$ such numbers, we know that $k$ must be a factor of $10$ . In other words, $k$ must be either $1$ , $2$ , $5$ , or $10$ , thus considerably reducing the amount of guessing and checking that has to be done. (Of course, for the example above, $k=2$ was the least value of $k$ that worked.)

In general, if $n = p_1^{a_1} p_2^{a_2} \dots p_r^{a_r}$ is the prime factorization of $n$ , then

$\phi(n) = n \left( \displaystyle 1 - \frac{1}{p_1} \right) \left( \displaystyle 1 - \frac{1}{p_2} \right) \dots \left( \displaystyle 1 - \frac{1}{p_r} \right)$

For the example above, since $11$ was prime, we have $\phi(11) = 11 \left( \displaystyle 1 - \frac{1}{11} \right) = 10$ .

Case 3. Suppose the prime factorization of the denominator $b$ both (1) contains $2$ and/or $5$ and also (2) another prime other than $2$ and $5$ . This is a mixture of Cases 1 and 2, and the fraction $\displaystyle \frac{a}{b}$ can be rewritten in the form $\displaystyle \frac{M}{10^d (10^k-1)}$ .

For example, consider

$\displaystyle \frac{11}{74} = \displaystyle \frac{11}{2 \times 37}$

Following the rule for Case 1, we should multiply by $\displaystyle \frac{5}{5}$ to get a $10$ in the denominator:

$\displaystyle \frac{11}{74} = \displaystyle \frac{11}{2 \times 37} \times \frac{5}{5} = \frac{55}{10 \times 37}$

Next, we need to multiply $37$ by something to get a number of the form $10^k - 1$ . Since $37$ is prime, every number less than $37$ is relatively prime with $37$ , so $\phi(37) = 36$ . Therefore, $k$ must be a factor of $36$ . So, $k$ must be one of $1$ , $2$ , $3$ , $4$ , $6$ , $9$ , $12$ , $18$ , and $36$ .

(Parenthetically, while we’ve still got some work to do, it’s still pretty impressive that — without doing any real work — we can reduce the choices of $k$ to these nine numbers. In that sense, the use of $\phi(n)$ parallels how the Rational Root Test is used to determine possible roots of polynomials with integer coefficients.)

So let’s try to find the least value of $k$ that works.

If $k = 1$ , then $10^1 - 1 = 9$ , but $9 \div 37$ is not an integer.
If $k = 2$ , then $10^2 - 1 = 99$ , but $99 \div 37$ is not an integer.
If $k = 3$ , then $10^3 - 1 = 999$ , and it turns out that $999 \div 37 = 27$ , an integer.