Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  André Nicolas Apr 1 '12 at 18:54
add comment

2 Answers 2

up vote 6 down vote accepted

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,

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  Michael Hardy Apr 1 '12 at 17:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.