Length of the period of decimal representation of $\frac{1}{n}$ is factor of $\varphi(n)$?

64 Views Asked by At

if $\frac ab=\alpha .c_1c_2 \cdots c_n \dot{d_1} d_2 \cdots \dot{d_m}$,

then $l(\frac {a}{b}):=m$.

so $l( {1 \over n} )=$ Length of the period of decimal representation of 1/n.

then, $l( {1 \over n }) \neq 0 \Rightarrow l( {1 \over n }) \vert \varphi(n)$ for all $n \in N$?

I tried for $n=1 $~ $80$, and it's true...

1

There are 1 best solutions below

0
On BEST ANSWER

If you perform the (never-ending) long division of $a$ by $b$,

  1. print $\lfloor a/b\rfloor$ and "."
  2. let $a\leftarrow 10\cdot(a \bmod b)$
  3. print $\lfloor a/b\rfloor$
  4. go to step 2

forever, the eventual periodicity of the output comes from the fact that eventually the value of $a$ in step 2 repeats because in can take only finitely many values $0,10,20,\ldots, 10(b-1)$. If it is the value after $n$ loops that repeats for the first time after $n+m$ loops, then we see that $10^na\equiv 10^{n+m}a\pmod b,$ or with $A:=10^na$, $$ A\equiv 10^m A\pmod b$$ and $m$ is minimal positive with this property. If $A$ and $b$ have a common divisor $d=\gcd(A,b)>1$, we can replace this condition with $A'\equiv 10^m\cdot A'\pmod {b'}$, where $A'=\frac Ad$ , $b'=\frac bd$. As $A'$ and $b'$ are co-prime, $A'\equiv 10^mA'\pmod {b'}$ is equivalent to $$\tag1 10^m\equiv 1\pmod {b'}.$$ In particular, $10$ and $b'$ are co-prime. The $\phi(b')$ numbers $\le b'$ that are co-prime to $b'$, form a group $G$ under multiplication modulo $b'$. From $(1)$, we conclude that the $10^k$, $0\le k<m$, also form a group $H$ under multiplication modulo $b'$. Then $H$ is a subgroup of $G$ and by an elementary result from group theory, the order of $H$ divides the order of $G$, i.e., $$l(\tfrac ab)\mid \phi(b').$$ If $a$ and $b$ are co-prime (e.g., when $a=1$), note that $b=2^r5^sb'$ and $b'$ is neither a multiple of $2$ or $5$. Then $$ \phi(b)=(r+1)(s+1)\phi(b')$$ so that $$l(\tfrac1b)\mid\phi(b). $$


Note that I do not see that $l$ ever takes the value $0$. Instead, terminating fractions such as $\frac 34=0.75$ are eventually periodic a la $\frac34=0.75\dot 0$ with a period length of $1$.