I was reading about a not so practical way to determine the divisibility of a number by $7$.
At some point the following number is mentioned: $142857$ (which is the result of $\frac{999999}{7}$) and apparently this number as I have verified if multiplied by $2,3,4,5, 6$ it gives the same digits in different order e.g. $142857 \cdot 3 = 428571$
Why does this number have this property? I see that the numbers $2,3,4,5,6$ are all remainders if we divide $100, 10, 10000, 100000, 1000$ by $7$ respectively but I am not sure if there is any correlation with the property.
I'd like to understand the intuition behind this "trick"
Note: I have found a similar post but I don't see any explanation on this
$\endgroup$ 82 Answers
$\begingroup$Well, one can note that $142857$ is a bit of a special number in that $\frac{1}{7}=0.\overline{142857}$, which means that, by long division, one obtains $\overline{142857}=142857142857142857...$ ad infinitum via the following algorithm:
Start with $1$.
$1=\color{green}{0}\times7+\color{red}{1}$ so $\frac{1}{7}=0.\text{something}$
To get this something, do:
$\color{red}{1}\times10 = 10 = \color{green}{1}\times7+\color{red}{3}$ (*)
$\color{red}{3}\times10 = 30 = \color{green}{4}\times7+\color{red}{2}$ (**)
$\color{red}{2}\times10 = 20 = \color{green}{2}\times7+\color{red}{6}$
$\color{red}{6}\times10 = 60 = \color{green}{8}\times7+\color{red}{4}$
$\color{red}{4}\times10 = 40 = \color{green}{5}\times7+\color{red}{5}$
$\color{red}{5}\times10 = 50 = \color{green}{7}\times7+\color{red}{1}$
Now, the remainder is $\color{red}{1}$, which is what we started with at equation (*), so we now have a loop which yields $\frac{1}{7}=0.\color{green}{\overline{142857}}$. In group-theoretic parlance, the fact that the loop closes after $6$ iterations means that $10$ has order $6$ in $(\mathbb{Z}/7\mathbb{Z})^*$, i.e. $10^6\equiv1 \pmod{7}$ and $10^k\neq1\pmod7$ for $1 \leq k \leq 5$.
To understand why the digits are shifted when e.g. multiplying by $3$, just note that multiplying $\frac{1}{7}$ by $3$ means considering $\frac{3}{7}$ instead of $\frac{1}{7}$, and so the algorithm would start at equation (**) instead of (*), thus yielding $\color{green}{\overline{428571}}$ instead of $\color{green}{\overline{142857}}$.
So $\frac{3}{7}=\frac{3\times 142857}{999999} = \frac{428571}{999999} \Rightarrow 3\times142857 = 428571$
This explains the shift.
$\endgroup$ 1 $\begingroup$Good question!
Let's see if we can noodle it out.
$\frac {1,000,000 -1}7 = 142857$.
And $2\times \frac {1,000,000 -1}7 = $ what... now you point out that $100 = 7k + 2$ where $7 =14$ so $2 = 100-7k$
$2\times \frac {100,000 - 1}7= (100-7k)\frac {1,000,000-1}7 =$
$100\frac {1,000,000 - 1}7 - k(1,000,000 -1) =$
$14,285,700 - \overline{k000000} +k$.
Hmm.... that we know $k = 14$ seems to be a really nice coincidence.
$14,285,700 - 14,000,000 + 14 = 285714$ and of course the numbers are reversed.
If we can assume that if $10^{m_j} = (\text{first }m_j\text{ digits of }142857)\times 7 + j$ for $j=2,3,4,5,6$ we'd be done.
After all we'd then have
$j \times 142,857=$
$(10^{m_j} - (\text{first }m_j\text{ digits of }142857)7)\frac {1,000,000-1}7 =$
$10^{m-j}142,857 - (\text{first }m_j\text{ digits of }142857)7)1,000,000 + (\text{first }m_j\text{ digits of }142857)7)= $
$[\overline{(\text{first }m_j\text{ digits of }142857)(\text{last }6-m_j\text{ digits of }142857)\underbrace{0...0}_{m-j}}]- [\overline{(\text{first }m_j\text{ digits of }142857)000000}]+(\text{first }m_j\text{ digits of }142857)=$
$\overline{(\text{last }6-m_j\text{ digits of }142857)(\text{first }m_j\text{ digits of }142857)}$
......
So how can we show that for all $m_j \le 6 $ that $10^{m_j} = (\text{first }m_j\text{ digits of }142857)\times 7 + j$
Well.....
we know that $\frac {1,000,000 -1}7 = 142,857$.
This means $\frac 17= \frac 1{1000000}\frac {1000000}7 = \frac 1{1000000}[142,857 + \frac 17]$. That means $\frac 17 = 0.142857\overline{142,857}$.
Okay....
So if we multiply $\frac 17$ times $10^{m_j}$ we get $10^{m_j}\frac 17 = (\text{first }m_j\text{ digits of }142857) + (\text{some decimal part less than } 1)$.
So $10^{m_j} = 7 \times (\text{first }m_j\text{ digits of }142857) + 7\times(\text{some decimal part less than } 1)=$
$7 \times (\text{first }m_j\text{ digits of }142857) + (\text{some value less than } 7)$
but as $10^{m_j}$ is a natural number (not divisible by $7$) we have
$10^{m_j} = 7 \times (\text{first }m_j\text{ digits of }142857) +j$ for some $1 \le j \le 7$
And that's it.
This will actually be true of any $n$ so that $\gcd(n,10) = 1$
Take, say $\frac 1{17}= 0.\overline{0588235294117647}$
We should get $0588235294117647 \times 2..... 16$ should be the same digits shifted. Try it.
$\endgroup$ 8
