3
$\begingroup$

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.

$\endgroup$

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
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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