3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The Carmichael function $\lambda(78)$ is $12$, so the period is a factor of $12$. But $17$ is a quadratic residue of $13$, so the period divides $6$. $\endgroup$ – André Nicolas May 20 '14 at 6:08
3
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

$$17\equiv-1\pmod3\implies17^2\equiv1\pmod3\implies\text{ord}_3{17}=2$$

$$17\equiv4\pmod{13}\implies17^2\equiv16\equiv3,17^3\equiv51\equiv-1\implies\text{ord}_{13}{17}=6$$

So, we can derive ord$_{39}17=6$

We can prove

  1. $\lambda(n)$ always divides $\phi(n)$
  2. ord$_na$ always divides $\lambda(n)$ for $(a,n)=1$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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