Given dividend and divisor, get the length of repeating digits in other bases than $10$

Question

Inspired by this question, I was intrigued to ask how the length of the repeating and non-repeating digits can be calculated for bases other than $10$. For instance, if we have the fraction

$$ \frac{47}{16} = 2.9375, $$

while not repeating in base $10$, it is repeating in base $9$:

$$ \frac{47}{16} = 2.83838383\ldots_9. $$

It is obvious that it is repeating because of the presence of $8$ in the denominator, but how to we use this information to find the length of the non-repeating part (which is $1$) and the repeating part (which is $2$)?

Answer 1

To find the length of the non-repeating part, factor the denominator. Find all the primes that are common between the denominator and $b$. The length of the non-repeating part will be the power of $b$ needed to account for all the factors. For example, if the denominator is $60=2^2\cdot 3 \cdot 5$ the non-repeating part in base $10$ will be of length $2$ because of the power of $2$ in the denominator. The non-repeating part in base $9$ will have length $1$ to cover the $3$.

To find the length of the repeating part, if the fraction is $\frac cd$ you can form products $cb^k \pmod d$. When you get back to $c$ you have the length of the repeating part. It will be a factor of $\phi(d)$, where $\phi$ is Euler's totient function.

As an example, consider $\frac 1{52}$ in base $10$. The two factors of $2$ in $52$ says there will be two non-repeating digits. We will clear those factors, so the length of the repeat will be a factor of $\phi(13)=12$. In fact, the repeat is $6$. We get $\frac 1{52}=0.01\overline{923076}$

Answer 2

Let $x,y,B\in \Bbb{N}\space|\space \text{gcd}(x,y)=1$. $x$ is the numerator of the fraction, $y$ is the denominator of the fraction and B is the base of the decimal expansion. (if the gcd of $x$ and $y$ are one this insures that the fraction $\frac{x}{y}$ is in reduced form.)

We first may want to know how many digits are to the left of the decimal point. This can be done by following two rules.

1. If $\frac{x}{y} < 1$ then then there is just a zero to the left of the decimal point

2. If $B^{g+1}>\frac{x}{y}\geq B^g$ Then the fraction has $g+1$ digits to the left where $g\in\Bbb{N}$

If we want to just focus on the right side of the decimal point we can create a new fraction $\frac{z}{y}$ such that $\frac{z}{y}=\frac{x}{y}-\lfloor\frac{x}{y}\rfloor$

In order to answer questions about the right side of the decimal expansion we first need $y$ and $B$ to be factorized into prime numbers. Let

$$y=p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}...\cdot p_m^{e_m}\space\space\space B=q_1^{f_1}\cdot q_2^{f_2}\cdot q_3^{f_3}...\cdot q_m^{f_n}$$

where $p_i$ are prime factors of $y$, $q_i$ are prime factors of $B$, $e_i$ are the exponent of the prime factors of $y$, and $f_i$ are the exponent of the prime factors of $B$.

If $\text{gcd}(y,B)=1$ then there are zero non-repeating digits to the right of the decimal point.

If $\text{gcd}(y,B)\neq 1$, then there is at least one $p$ in $y$ that is equal to one $q$ in $N$. For each pair of $p$ and $q$ that are equal we have $\lceil\frac{e_j}{f_j}\rceil$. Where $e_j$ is the exponent of one of the $p\text{’s}$ of the $pq$ pairs and $f_j$ is the exponent of $q$ in the same $pq$ pair. The number of non-repeating digits to right of the decimal point is the largest of the $\lceil\frac{e_j}{f_j}\rceil$ fractions. For example if $z=1$ $y=216$ and $N=12$ then $y=2^3\cdot3^3$ $N=2^2\cdot3^1$. In this case there are two $pq$ pairs and the two corresponding fractions are $\lceil\frac{3}{2}\rceil=2$ and $\lceil\frac{3}{1}\rceil=3$ so the second one is the larger of the two so $\frac{1}{216}$ has three non-repeating digits after the decimal point. $\frac{1}{216}=0.008$ in base 12.

let $y’$ be the largest number that satisfies the two conditions $y’\space|\space y$ and $\text{gcd}(y’,B)=1$. (In other words $y’$ is constructed by removing all of the prime factors from $y$ that divide $B$.)

If $y’=1$ then there are no repeating digits for $\frac{z}{y}$

If $y'\neq1$ then to show what the number of repeating digits are, it is useful to point out that $1=0.(B-1)(B-1)(B-1)(B-1)(B-1)(B-1)...$ For example if $B=3$ then $1=0.222222...$. This can be shown by first letting $$t=0.(B-1)(B-1)(B-1)(B-1)(B-1)(B-1)...$$ $$Bt=(B-1).(B-1)(B-1)(B-1)(B-1)(B-1)(B-1)….$$ $$Bt-B+1=0.(B-1)(B-1)(B-1)(B-1)(B-1)(B-1)….$$ The right hand side of the previous line is the right hand side of the original $t$ equation so $$Bt-B+1=t$$ $$Bt-t=B-1$$

$$t(B-1)=B-1$$ $$t=1$$ If $y’$ divides a finite number string of $(B-1)\text{’s}$ then there will be a number of repeating digits equal to the minimum length of string that $y’$ divides. The number $(B-1)(B-1)(B-1)(B-1)(B-1)(B-1)$ can be more compactly represented as $B^6-1$. A theorem that is useful for expressions of this form is Fermat’s little theorem. It states that if $a,p\in\Bbb{N}$ where $p$ is prime then $p|a^p-a$ (proof of this can be found here: https://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem). A corollary to this is if $\text{gcd}(a,p)=1$ then $p\space |\space a^{p-1}-1$ or $a^{p-1} \text{mod}\space p \equiv 1$. This implies that if $a$ is raised to a multiple of $p-1$ then that will also be congruent to 1 modulo $p$. For example $a^{3(p-1)}\equiv a^{p-1}\cdot a^{p-1}\cdot a^{p-1}\equiv 1\cdot 1\cdot 1 \equiv 1 \space\text{mod}\space p$. We can use this fact to find the power of $a$ minus one that is dividable by $P^k$. $$a^{p^{k-1}(p-1)}-1=(a^{p-1}-1)(a^{(p^{k-1}-1)(p-1)}+a^{(p^{k-1}-2)(p-1)}+a^{(p^{k-1}-3)(p-1)}+...+a^{3\cdot(p-1)}+a^{2\cdot(p-1)}+a^{p-1}+1)$$

by Fermat's little theorem $p|a^{p-1}-1$

notice that all of the terms in $a^{(p^{k-1}-1)(p-1)}+a^{(p^{k-1}-2)(p-1)}+a^{(p^{k-1}-3)(p-1)}+...+a^{3\cdot(p-1)}+a^{2\cdot(p-1)}+a^{p-1}+1$ are $a$ to a power of a multiple of $p-1$ and there are $p^{k-1}$ terms so $p^{k-1}|(a^{(p^{k-1}-1)(p-1)}+a^{(p^{k-1}-2)(p-1)}+a^{(p^{k-1}-3)(p-1)}+...+a^{3\cdot(p-1)}+a^{2\cdot(p-1)}+a^{p-1}+1)$ This means that $p^k| a^{p^{k-1}(p-1)}-1$

To give a specific example of this $$10^{6\cdot 7^2}-1=(10^6-1)(10^{6\cdot(7^2-1)}+10^{6\cdot(7^2-2)}+10^{6\cdot(7^2-3)}+….+10^{6\cdot 3}+10^{6\cdot 2}+10^6+1)$$ $$7\space|\space 10^6-1$$ $$7^2\space |\space(10^{6\cdot(7^2-1)}+10^{6\cdot(7^2-2)}+10^{6\cdot(7^2-3)}+….+10^{6\cdot 3}+10^{6\cdot 2}+10^6+1)$$

using the property $a^{bc}-1=(a^b-1)(a^{(c-1)b}+a^{(c-2)b}+a^{(c-3)b}+….+a^{3b}+a^{2b}+a^b+1)$ we can find a power of $a$ minus one that is divisible by a given $n$ where $n\in\Bbb{N}$.

let $S=\text{lcm}((p_1-1)\cdot p_1^{e_1-1},(p_2-1)\cdot p^{e_2-1},(p_3-1)\cdot p^{e_3-1},...,(p_n-1)\cdot p_n^{e_n-1})$ where $p_i$ in $\text{lcm}$ divide $y’$. Then $y’|B^S-1$. So the number of repeating digits of $\frac{z}{y}$ is no bigger than $S$. Using the $a^{bc}-1$ property mentioned earlier. The number of repeating digits $\frac{z}{y}$ is a factor of $S$. There currently doesn’t exist a general method to find which factor of $S$ gives the number of repeating digits, so all factors of $S$ must be tested to determine if $B$ to the power of that factor minus one is dividable by $y’$