10
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @ Zander I like this proof and I am with you all the way up to $2^{m} = jp +1$; however, I do not see the conclusion that $m|n$. The fault likely lies with me, but I would be grateful if you might clarify your conclusion for me. Why I am confused is as follows: If I take $k$ to be the smallest $k$ that works, and similarly for $j$, then since $m \geq n$, how come $j$ cannot be $\geq$ to $k$? The only way I can see that one can conclude that $m|n$ is if the smallest $k$ and smallest $j$ are equal. $\endgroup$ – mlchristians Jun 28 '19 at 16:28
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\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.