Prove if $k$ is any positive integer, the decimal expansion of $\frac{1}{k}$ eventually gets into a repeating cycle.

I'm stuck here , i've thought about applying the pigeonhole principle and induction here but to no avail...

My answer is asking for a proof through pigeonhole principle or induction.. the one linked does not show those..

Please don't close this.


marked as duplicate by Mees de Vries, Jean Marie, Henry, Marc van Leeuwen, user223391 Mar 10 '17 at 7:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ @MeesdeVries Can u check my edit. $\endgroup$ – bigfocalchord Mar 8 '17 at 8:57
  • 1
    $\begingroup$ @dydxx, actually the second answer in the linked question provides a solution that uses the pidgeonhole principle. $\endgroup$ – Mees de Vries Mar 8 '17 at 9:12

If you divide $1$ by $k$ in the way everyone learnt it in school, you calculate $10$ times a number divided by $k$ with remainder multiple times.

The possible remainders are $0,1,\cdots ,k-1$, so there are $k$ possible remainders.

If we have determined $k+1$ remainders, the pigeonhole-principle guarantees some duplication.

So, there must be two positions with equal remainders.

The earliest point for which this occurs is the point where the decimal expansion gets periodic.


Perform long division:

To find the decimal expansion for $1/k$, let $a_0=1$. Then $10a_0=kb_1+a_1$, and we continue so that $10a_1=kb_2+a_2$, and so on. From this, we see that $b_1,b_2,...$ are indeed the digits in the decimal expansion.

by the pigeonhole principle: we know that $a_1 \in \{0,1,..k-1\}$ because it is a remainder, so eventually $a_i=a_j$ for some $i,j \leq k$. But then $b_{i+1}=b_{j+1}$ and so forth after this, so the decimal expansion is periodic.


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