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$
1
  • $\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$ Commented May 20, 2014 at 6:08

2 Answers 2

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$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .