# Repeating decimal algorithm

I was working on a problem where I needed to prove things in base 10, like: "11 divides $a$ if and only if 11 divides $a_0-a_1+a_2-\cdots$" where $$a=a_0\cdot10^0+a_1\cdot10^1+a_2\cdot10^2+\cdots+a_n\cdot10^n$$ and $0\leq a_i <10$

The solution in this case would be:

$$a=(a_0-a_1+a_2-\cdots) +11(a_1+9a_2+91a_3+909a_4+9091a_5+90909a_6+\cdots)$$ $$\frac{a}{11}=\frac{a_0-a_1+a_2-\cdots}{11}+(a_1+9a_2+91a_3+909a_4+9091a_5+90909a_6+\cdots)$$

...Then I was asked to find a rule for 7, and that's when I realized 7 is special.

First create a table of equivalences involving $10^1,10^2,\cdots$ of the form $10^n+x_n\equiv 0\pmod 7$. $$10^1+4\equiv0\pmod7$$ $$10^2+5\equiv0\pmod7$$ $$10^3+1\equiv0\pmod7$$ $$10^4+3\equiv0\pmod7$$ $$10^5+2\equiv0\pmod7$$ $$10^6+6\equiv0\pmod7$$ From this point on, there is a repeating pattern for $x_n$: 4,5,1,3,2,6. $$10^7+4\equiv0\pmod7$$ $$10^8+5\equiv0\pmod7$$ $$10^9+1\equiv0\pmod7$$ $$\vdots$$ and so on. Next, let us calculate $b_n=(10^n+x_n)/7$ until we can detect a pattern. $$(10^1+4)/7=2$$ $$(10^2+5)/7=15$$ $$(10^3+1)/7=143$$ $$(10^4+3)/7=1429$$ $$(10^5+2)/7=14286$$ $$(10^6+6)/7=142858$$ $$(10^7+4)/7=142857\color{red}{2}$$ $$(10^8+5)/7=142857\color{red}{15}$$ $$(10^9+1)/7=142857\color{red}{143}$$ $$(10^{10}+3)/7=142857\color{red}{1429}$$ $$(10^{11}+2)/7=142857\color{red}{14286}$$ $$(10^{12}+6)/7=142857\color{red}{142858}$$ $$(10^{13}+4)/7=142857\color{red}{142857}\color{green}{2}$$ $$(10^{14}+5)/7=142857\color{red}{142857}\color{green}{15}$$ $$(10^{15}+1)/7=142857\color{red}{142857}\color{green}{143}$$ $$(10^{16}+3)/7=142857\color{red}{142857}\color{green}{1429}$$ $$\vdots$$ We have a neat repeating pattern, which is a result of the fact that $1/7=0.\overline{142857}$. Now we can develop a representation for $a$: $$a=(a_0-x_1a_1-x_2a_2-x_3a_3-\cdots)+7(b_1a_1+b_2a_2+b_3a_3+\cdots)$$ where $x_1=4,x_2=5,\cdots$ (following the repeating pattern 4,5,1,3,2,6) and $x_n=x_{n+6}$, and $b_n=(10^n+x_n)/7$. This gives us $$a=(a_0-4a_1-5a_2-a_3-3a_4\cdots)+7(2a_1+15a_2+143a_3+1429a_4\cdots)$$ $$\frac{a}{7}=\frac{a_0-4a_1-5a_2-a_3-3a_4\cdots}{7}+(2a_1+15a_2+143a_3+1429a_4\cdots)$$ Which implies that $7\,|\,a$ iff $7\,|\,(a_0-4a_1-5a_2-a_3-3a_4-\cdots)$.

So that was how I solved that. But there's something that stuck with me: what is the significance of that sequence 4,5,1,3,2,6? I can't seem to fit it into anything. Also, is there a way to just look at the decimal $0.\overline{142857}$ and know that 4,5,1,3,2,6 corresponds to it in base 10?

Furthermore, let us consider the other repeating decimals like $1/13 = 0.\overline{076923}, 1/17 = 0.\overline{0588235294117647},$ etc. Most of $1/p$ ($p$ prime) are long repeating decimals (base 10). Can we come up with a simple algorithm to that sequence for any $1/p$?

11 is a prime that has a simple sequence: -1,1 repeating. It seems that 7 is interesting simply because its repeating decimal has a large period (6). If we come up with an algorithm, can we say it is true for all primes? (maybe it's just for 7, because $1/7$ has cool properties) Is it only for certain primes? Can we figure out which primes? (so many questions!) More interesting material: Why is the decimal representation of $\frac17$ "cyclical"?

Thank you.

• If the number $p$ is a prime, the residues have a random-like-structure, which is used in simple random generators. The sequence $10^n\ (\ mod\ p\ )$ also behaves chaotic. I have no idea how the sequences $1,4,2,8,5,7$ and $4,5,1,3,2,6$ are connected and how we can easy transform one to the other. – Peter Jan 14 '15 at 21:45
• There's no pattern on any level? – Patrick Shambayati Jan 14 '15 at 21:47
• The length of the period however can be predicted using the order : The least number $k>0$, for which $10^k\equiv1\ (\ mod\ p\ )$ is equal to the period length. Because of Fermat's little theorem, $k$ must be a divisor of $p-1$. – Peter Jan 14 '15 at 21:50
• It is easy to see that every decimal representation of $\frac{a}{b}$, if it does not terminate, must have a repeating-for-ever-sequence (not necessarily beginning at the start) because there are only finite many possible residues, so at some point there must be a repetition and we enter a cycle. But have a bit care : The repetition only guarantees a cycle if it occured after the last non-zero digit of $a$ was used. This is no problem if we only look at $\frac{1}{p}$-fractions. – Peter Jan 14 '15 at 21:55
• Take 1,4,2,8,5,7 (The repeating decimal of $\frac17$). Multiply by 7 (mod 10): 7,8,4,6,5,9. Now, add 7 (mod 10): 4,5,1,3,2,6. Voila. – Akiva Weinberger Jan 14 '15 at 23:43