Elementary way to prove that if $n$ and $10$ are coprime, then $1/n$ has no transient digits.

Question

With Euler-Fermat's theorem at hand it's easy to prove that if $\gcd(n,10)=1$ then the decimal expansion of $1/n$ is repeating, and that there is no transient (that is, digits after the point before the repetend). With pigeonhole principle we can show easily that $1/n$ is repeating, but I don't know how to prove that there is no transient.

I'd like to show my pupils (that don't know anything about group theory or congruences) that the repeating decimals that have transient are represented by fractions whose denominator has $2$ or $5$ as a factor.

Answer 1

Responding to comments.

To show that $\frac{1}{2^a 5^b}$ has a finite decimal, let $c = \max \{a,b\}$ and consider $$ \frac{1}{2^a 5^b} = \frac{1}{2^a 5^b} \cdot \frac{2^{c-a} 5^{c-b}}{2^{c-a} 5^{c-b}} = \frac{2^{c-a} 5^{c-b}}{10^c} \text{,} $$ which has a finite decimal expansion whose digits are those of $2^{c-a}5^{c-b}$.

Now suppose we have $\frac{1}{2^a 5^b c}$, where $\gcd(c,10) = 1$. Suppose $$ \frac{1}{2^a 5^b c} = \frac{d}{10^e} \text{,} $$ that is, $\frac{1}{2^a 5^b c}$ has a terminating decimal expansion whose digits are the digits of $d$. But then $$ 10^e = 2^a 5^b c d $$ Since the prime factorization of $10^e$ is $2^e 5^e$, the only primes appearing on the right-hand side are $2$ and $5$. Since $\gcd(c,10) = 1$, this forces $c = 1$. As a consequence, if $c \neq 1$, $\frac{1}{2^a 5^b c}$ does not have a terminating decimal expansion.

---

Warm up: $$ \frac{1}{30} = 0.0\overline{3} \text{,} $$ but also \begin{align*} \frac{1}{30} &= \frac{1}{3} - \frac{3}{10} \\ &= 0.\overline{3} - 0.3 \text{.} \end{align*} So what we need to do is find a way to separate the given fraction into one that contains the part that has a denominator of $2^a 5^b$ and a part that has the maximal denominator relatively prime to $10$.

Suppose we are to understand $a/b$ and $\gcd(b,10) = c$, so $b = c \cdot d$ with $\gcd(d,10) = 1$. We want $$ \frac{a}{b} = \frac{\text{something}}{c} + \frac{\text{another something}}{d} \text{.} $$ The second fraction will tell us about the repetend and the first fraction will tell us about the modification of the leading digits of the repetend to make the transient initial segment. We use the extended Euclidean algorithm to find the unknown numerators.

Let's do another example to see how to find the two numerators. Let's look at $1/175$. We want to find $e$ and $f$ such that $$ \frac{1}{175} = \frac{e}{7} + \frac{f}{25} \text{.} $$ Clearing denominators, $$ 1 = 25e + 7f $$ Using the extended Euclidean algorithm, we find that $\gcd(25,7) = 1$ (which we already know is true, by construction) and also $2 \cdot 25 + (-7) \cdot 7 = 1$. So, $e = 2$ and $f = -7$ work. We find out \begin{align*} \frac{1}{175} &= \frac{2}{7} - \frac{7}{25} \\ &= 0.\overline{285714} - 0.28 \\ &= 0.00\overline{571428} \text{.} \end{align*}

Notice that our construction shows that, in some sense, we should think of the repetend of $1/175$ to be $285714$, with the transient initial segment being altered to suppress the first two digits, rather than thinking of the repetend starting on the third decimal digit.

Answer 2

The digits $n_1\dots n_2-1$ of $\frac1m$ form a repeating block when $10^{n_1-1}\equiv10^{n_2-1}\pmod{m}$. Note that if $(10,m)=1$, and $10^{n_1-1}\equiv10^{n_2-1}\pmod{m}$, then $10^0\equiv10^{n_2-n_1}\pmod{m}$. That means that digits $1\dots(n_2-n_1)$ form a repeating block.

Answer 3

Bear in mind:

$m_1 = 10$ and $10=d_1*n + r_1; 0\le r_1 < n$ and $d_1$ is the first digit.

$m_2 = 10*r_1$ and $m_2 = d_2*n + r_2; 0\le r_2 < n$ and $d_2$ is the second digit.

And so on.

$m_{k+1} = 10r_k$ and $m_{k+1}=d_{k+1}*n +r_{k+1};0\le r_{k+1} < n$ and $d_k$ is the $k$th digit.

And as $n$ and $10$ are relatively prime we never have $r_{k+1}=0$ and as there are only $n$ possible $r_k$ we must get a repetition and once we do we get an infinite loop.

But suppose we get a case where $r_k = r_v$ (and thus $m_{k+1}=10r_k = m_{n+1}=10r_v$ and $m_{k+1} = 10d_{k+1} + r_{k+1}= m_{v+1}=10d_{m+1} + r_{v+1}\implies d_{k+1}=d_{v+1}; r_{k+1}=r_{v+1}$ and so on...)

Does this mean that $m_k = 10*r_{k-1} = d_k*n + r_k$ and $m_v = 10*r_{v-1}= d_v*n + r_v = d_v*n + r_k$ implies $d_k = d_v$ and so $r_{k-1} = r_{v-1}$?

The answer is yes.

If $d_k \ne d_v$ but $r_k = r_v$ then $10r_{k-1} = d_k*n + d_k$ and $10r_{v-1} = d_v*n + d_v$ the $10r_{k-1}-10r_{v-1} = 10(r_{k-1}-r_{v-1}) = n*(d_k-d_v)$.

But $n$ and $10$ are coprime so either $n|r_{k-1}-r_{v-1}$ or $d_k-d_v = 0$ (or both). But $-(n-1) < r_{k-1}-r_{v-1} < n-1$ so if $n|r_{k-1}-r_{v-1}$ then $r_{k-1}-r_{v-1}=0$ and $r_{k-1}=r_{v-1}$ and so $d_k$ and $d_v = 0$.

If id $d_k = d_v$ then ... $10r_{k-1} = 10r_{v-1}= 10d_k + r_k =10d_v + r_v$ and $r_{k-1} = r_{v-1}$.

So, yes $r_{k-1} = r_{v-1}$ and $d_k = d_v$. So by induction no-where can any $d_i$ and $d_{i+(v-k)}$ differ.

And that's that. Just as you must repeat, nothing different can appear before the "repetend".