2
$\begingroup$

It is an exercise in a book on discrete mathematics.How to prove that in the decimal expansion of the quotient of two integers, eventually some block of digits repeats. For example: $\frac { 1 }{ 6 } =0.166\dot { 6 } \ldots$ and $\frac { 217 }{ 660 } =0.328787\dot { 8 } \dot { 7 } \ldots$

How to think of this?I just can't find the point to use the Pigeonhole Principle. Thanks for your help!

  • 0
    Probably you are intended to prove the result by discussing the school division procedure. In the formal sense, this is not enough, since we have not proved that the algorithm works.2012-04-01

2 Answers 2

6

Let's proceed to the actual division :

$ \begin{array} {r|l} \boxed{217}\hphantom{000\;} & 660\\ \hline 2170\hphantom{000} & 0.3287\\ -1980\hphantom{000} & \\ \boxed{190}\hphantom{00\;} & \\ 1900\hphantom{00} & \\ -1320\hphantom{00} & \\ \boxed{580}\hphantom{0\;} & \\ 5800\hphantom{0} & \\ -5280\hphantom{0} & \\ \boxed{520}\hphantom{\;} & \\ 5200 & \\ -4620 & \\ \boxed{580} & \\ \end{array} $

The important point is that the remainders must be smaller than the quotient $660$ so that, after a finite number of operations, you must get $0$ or a remainder you got before.
What will the next digit of the quotient be? And the next remainder?

Hoping it clarified,

2

Assume the decimal is infinite (otherwise the 0 repeats). Imagine evaluating the quotient by long division. After each step after the numerator has become all 0's, you have to carry over something less than the denominator. Eventually you'll have to carry something you carried before, because you carry something on every step.

  • 0
    By "carry over", I presume you mean it's the remainder. But I wouldn't have known that if I hadn't already known how to do this.2012-04-01