Prove that the binary expansion of 1n\dfrac{1}{n} is periodic

Prove that if n>1n > 1 is odd, then the binary expansion of 1n\dfrac{1}{n} is periodic.

Since nn is odd, we know that 22 is invertible modulo nn. How do we continue from here?




What do you know about 2k2^k modulo nn?
– Daniel Fischer♦
Oct 20 at 19:08



Try long division.
– Neal
Oct 20 at 19:11



As an act of good faith in the community, you should start wondering about accepting at least some of the answers MSE provided you.
– Jack D’Aurizio
Oct 20 at 23:48


4 Answers


Presumably you want n>1n > 1. If 2m≡1modn2^m \equiv 1 \mod n, then
1n=a2m−1=a2m+a22m+a23m+…\dfrac{1}{n} = \dfrac{a}{2^m-1} = \dfrac{a}{2^m} + \dfrac{a}{2^{2m}} + \dfrac{a}{2^{3m}} + \ldots
for some aa, 1≤a<2m−11 \le a < 2^m-1. If it where not periodic you have an equation of the form 1n=m∑k=1ak2k=A2m\frac{1}{n}=\sum_{k=1}^m \frac{a_k}{2^k}=\frac{A}{2^m} Then 2m=An2^m=An so n∣2mn\mid 2^m. Since 22 is invertible (modn)\!\!\pmod{n}, there is some exponent mm such that 2m≡1(modn)2^m\equiv 1\pmod{n}, i.e. nn is a divisor of 2m−12^m-1. Since 12=0.11111111…2=0.¯111…111⏟m times 1_2 = 0.11111111\ldots_2 = 0.\underbrace{\overline{111\ldots 111}}_{m\text{ times}} the period of 1n\frac{1}{n} in base-22 has length mm and is given by the binary representation of 2m−1n\frac{2^m-1}{n}. In fact, it is true that any number xx is rational ⟺\iff it has eventually periodic (periodic from some point) expansion (in any base). To prove your case just use the standard division algorithm ( - but in binary notation instead of decimal. If you divide 1n\frac{1}{n}: you subtract 12\frac{1}{2} (if possible), take the reminder, subtract 14\frac{1}{4} (if possible) etc. Now observe that (i) the reminder determines the next reminder, (ii) there are only n−1n-1 possible reminders. By (ii) reminder will eventually repeat, by (i) from this point the sequence will be periodic. What remains is to show that if nn is odd, the sequence will be periodic (not only eventuallyeventually): Since we know, that the expansion of 1n\frac{1}{n} is eventually periodic, we may subtract/add some number dd s.t. the result xx will be just periodic. dd represents the difference on first bits, so its binary expansion has only finitely many non-zero bits. If it has jj non-zero bits, we can write it as d=i2jd=\frac{i}{2^j} for some odd (or zero) ii. On the other hand we know, that the periodic xx is of the form pq\frac{p}{q} (basically this: is a reason). Now: 1n=i2j±pq1n∓pq=i2j2j×q∓npnq=i\frac{1}{n} = \frac{i}{2^j} \pm \frac{p}{q}\\ \frac{1}{n}\mp\frac{p}{q} = \frac{i}{2^j}\\ 2^j \times\frac{q \mp np}{nq} = i Hence, as we know that ii cannot be even, it's 0. So dd is also 0. So, finally, 1n\frac{1}{n} is periodic.