I am trying to find the length of of the repeating block of digits in the decimal expansion of $\frac{17}{78}$.
On similar problems, that has not been an issue. Take for instance $\frac{17}{380}$. My usual approach would be to calculate $\Phi (380) = \Phi(4)*\Phi(5)*\Phi(19)=2*4*18=144$, then test $10^{\Phi(each factor)} \equiv 1 \pmod{380}$. No $\Phi(factor)$ passes, so the highest, $\Phi(19) = 18$, is the length of the repeating block of digits.
But that does not work for $\frac{17}{78}$. I know from checking on my calculator that the length is 6, but there is no factor of 78 such that $\Phi(factor)=6$.
What makes this problem different and what method do I use to find the length of its repeating block?
Answer
Note that the period for a prime $p$ is a factor of $\varphi (p)=p-1$ but need not be equal to it. This is because $10^{p-1} \equiv 1 \mod p$. The period is the least $n$ for which $p|(10^n-1)$.
If you know that $1001=7 \times 11 \times 13$ then it is easy that $10^6-1=27\times 7\times 11\times 13\times 37$
Primes with period $1$ divide $10^1-1=9$ hence $3$ (also $3^2=9$)
Primes with period $2$ divide $10^2-1 =99$ hence $11$ (we've dealt with $9$ as having period $1$)
Primes with period $3$ divide $999=27\times 37$ hence $37$ (and $3^3$)
The primes with period $6$ are then $7$ and $13$
No comments:
Post a Comment