Why the sum of $n$ seems equals the period of the binary expansion of $1/n$?

The sum of $n$(suppose $n$ is positive odd,using $n=23$ as an example):

Step 1 : Get the odd part of $23 + ~~1 $, which is $~~3$,$~~3\times2^3=23 + ~~ 1$,get $s_1 = 3$
Step 2 : Get the odd part of $23 + ~~3 $, which is $13$,$13\times2^1=23 + ~~ 3$,get $s_2 = 1$
Step 3 : Get the odd part of $23 + 13 $, which is $~~9$,$~~9\times2^2=23 + 13$,get $s_3 = 2$
Step 4 : Get the odd part of $23 + ~~9 $, which is $~~1$,$~~1\times2^5=23 + ~~9$,get $s_4 = 5$

Continuing this operation (with $23 + 1$) repeats the same steps as above. There are $4$ steps in the cycle, so the cycle length of $23$ is $4$，and the sum of $23$ is $s_1 + s_2 + s_3 + s_4 = 11$.

The period of the binary expansion of $1/23$ is $11$,so why the sum of $23$ seems equals the period of the binary expansion of $1/23$?

Solution 1:

Consider the sequence $a_i = 2^{-i} \pmod{23}$ $$ \begin{array}{l} a_0 = 1,~a_1=12,~a_2=6 \\ a_3 = 3 \\ a_4 = 13, ~ a_5=18, \\ a_6=9, ~ a_7 = 16, a_8=8, a_9=4, a_{10}=2 \\ a_{11} = 1 = a_0 \end{array} $$ Your steps of "get the odd part" are precisely finding the next odd number in this sequence, your $s_i$ are counting all of the steps, and the sum $\sum s_i$ is the order of 2 modulo 23.

Let $n=\operatorname{ord}_p 2$ be the order of 2 modulo a prime $p$ and $m$ the period of the binary expansion of $1/p$. Then for some positive integer $k$ $$ 2^n = pk+1 \\ 2^n\frac{1}{p} = k + \frac{1}{p} $$ That is, the binary representation of $1/p$ repeats after $n$ bits, so $n\mid m$. Similarly, for some positive integer $j$ $$ 2^m \frac{1}{p} = j + \frac{1}{p} \\ 2^m = jp + 1 $$ so also $m\mid n$ and hence $n=m$.

Solution 2:

Hmm... I don't see where this comes from off the top of my head, or exactly how to prove it, but here's something which is at least partway to a proof. We have a sequence

$$n + 1 = 2^{s_1} t_1$$

$$n + t_1 = 2^{s_2} t_2$$

$$\vdots$$

$$n + t_{\ell - 1} = 2^{s_\ell} t_\ell$$

where $t_0 = t_\ell = 1$. Multiplying together these equations, we see that

$$\prod_{i = 0}^{\ell-1} (n + t_i) = 2^{s_1 + \cdots + s_\ell} t_1 \cdots t_\ell.$$

Expand the LHS in terms of elementary symmetric polynomials:

$$\sum_{j = 0}^{\ell} n^{\ell - j} S_j(t_1, \ldots, t_\ell) = 2^{s_1 + \cdots + s_\ell} t_1 \cdots t_\ell$$

Noticing that $S_\ell(t_1, \ldots, t_\ell) = t_1 \cdots t_\ell$, subtract that term from each side:

$$\sum_{j = 0}^{\ell-1} n^{\ell - j} S_j(t_1, \ldots, t_\ell) = \left(2^{s_1 + \cdots + s_\ell}-1\right) t_1 \cdots t_\ell$$

Pull out a factor of $n$ on the left:

$$n \sum_{j = 0}^{\ell-1} n^{\ell - j - 1} S_j(t_1, \ldots, t_\ell) = \left(2^{s_1 + \cdots + s_\ell}-1\right) t_1 \cdots t_\ell$$

Note that if $n$ is prime (as in your example) then the $t_i$ are relatively prime to $n$; since $n$ divides the LHS, it must divide the RHS, and since $n$ is relatively prime to the $t_i$, it must divide $2^{s_1 + \cdots + s_\ell} - 1$, which says that the period of the binary expansion divides $s_1 + \cdots + s_\ell$.

This is probably not the best way to approach this, but I thought I'd go ahead and write it down in case it helps.

Solution 3:

Something more general is true.

Let $b\geq 2$ and and $n$ any positive integer coprime with $b$. Define the sequence $s_i$ as follows:

The first term $s_1$ is defined as the smallest non negative integer such that $b^{s_1}t_1=n+1$ and $b\not\mid t_2$.
The second term $s_2$ as the smallest non negative integer such that $b^{s_2}t_2=n+t_1$ and $b\not\mid t_2$.
The third term $s_3$ as the smallest non negative integer such that $b^{s_3}t_3=n+t_2$ and $b\not\mid t_3$.
$\hspace{38 ex} \vdots$
Finally the $d^{th}$ term $s_d$ as the smallest non negative integer such that $b^{s_d}=n+t_{d-1}$.

That this sequence is purely periodic, is explained here. What you observed is that the sum of the $s_i$ is the cycle length of $1\over n$ written in base $b$. But, that cycle length of $1\over n$ is the order of $b\pmod n$ since both these numbers can be described as the smallest positive integer $s$ such that $b^s {1\over n}-{1\over n}\in\mathbb N$.

Therefore, it remains to show that $s=s_1+s_2+\ldots+s_d$ is the order of $b\pmod n$ which it's easy to see that it is equivalent to showing that $\operatorname{ord}_n\left(\dfrac1b\right)=s$ or that $b^s=1$ and $\dfrac{1}{b^i}\neq1$ for all $i=1,2,\ldots,s-1$.

Set $t_0=t_{d+1}=1$. Reducing the equations $b^{s_i}t_i=n+t_{i-1}\pmod n$, we obtain $b^{s_i}t_i=t_{i-1}\pmod n$ and therefore $b^s=1\pmod n$. Now for the second part note that $$ \dfrac1b=b^{s_1-1}t_1\pmod n, \ \dfrac1{b^2}=b^{s_1-2}t_1\pmod n,\ldots,\dfrac1{b^{s_1}}=t_1\pmod n, \\ \dfrac1{b^{s_1+1}}=\dfrac{1}{b}t_1=\dfrac{1}{b}b^{s_2}t_2\pmod n=b^{s_2-1}t_2\pmod n\ldots$$

It's not so hard to show that all these values are different from $1\pmod n$. You have to do some work. It may happen that some of the $s_i$ are zero and therefore you have to consider several cases. The case $b=2$ is of course easier since from the fact that $\gcd(n,t_i)=1, \ \forall i$ (why?) it follows that $s_i\neq0 \ \forall i$.

Therefore $\operatorname{ord}_n\left(\dfrac1b\right)=\operatorname{ord}_n(b)=s$.