Wednesday, 11 September 2013

modular arithmetic - Cannot find length of repeating block in decimal expansion for frac1778




I am trying to find the length of of the repeating block of digits in the decimal expansion of 1778.



On similar problems, that has not been an issue. Take for instance 17380. My usual approach would be to calculate Φ(380)=Φ(4)Φ(5)Φ(19)=2418=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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...