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

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$)?

• This is a duplicate of this question as there is nothing special about base $10$ except that it has two prime factors. In a base with only one prime factor there is never a nonrepeating part of the decimal. The nonrepeating part of a decimal (not the whole number part) in base $10$ covers factors of $2$ or $5$ in the denominator. Also see this question – Ross Millikan Sep 16 '18 at 17:17
• @RossMillikan Thanks for the comment and the links. However, I don't agree with the statement "In a base with only one prime factor there is never a nonrepeating part of the decimal", since in my example $\frac{47}{16}$ has a nonrepeating part of length $1$ in the base $9$, which has a single prime factor. – Klangen Sep 17 '18 at 12:20
• No, the nonrepeating part of a decimal has to come after the decimal point. The $2$ in your example is the quotient. The decimal comes from the remainder $\frac {15}{16}=0.838383\ldots_9$ with no nonrepeating part. In base $10$ we have $\frac 16=0.16666\ldots$ with the $1$ being nonrepeating because of the factor $2$. But you are right in that in base $9$ we could ask for $\frac 16=0.14444_9$ The factor $3$ in $6$ makes the nonrepeating part. – Ross Millikan Sep 17 '18 at 13:55
• @RossMillikan Thank you. But is there a general "formula" for positive integer base $n$? I.e., one that could be applied to an fraction $\frac a b$, where $b$ contains a factor coprime to $n$? – Klangen Sep 18 '18 at 7:01
• It will be a factor of $\phi(b)$, Euler’s totient function. I don’t know a general way to find it – Ross Millikan Sep 18 '18 at 14:21

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}$$

• Thank you for your answer. However I don't understand it in the case of the following example: let $n=\frac{1}{16\times 7}$. Then in base $8$, $n=0.0044444\ldots$ Since $8=2^3$, I would expect the nonrepeating part to have length $3$, however it has length $2$. What am I misunderstanding? – Klangen Sep 21 '18 at 17:23
• You need enough factors of $2$ in $8^k$ to take care of all the factors of $2$ in the denominator. As $8^1=2^3$ has less factors of $2$ than the denominator and $8^2=2^6$ has at least as many factors of $2$ as the denominator, the non-repeating part will have length $2$. If the denominator were $2^17\cdot 7$ the non-repeating part would be $6$ long. – Ross Millikan Sep 21 '18 at 17:28
• Thank you, I understand it perfectly now! – Klangen Sep 21 '18 at 19:57
• Sorry for all these questions, but I have another one, hopefully the last. On your example or 1/52 in base 10, the two factors of 2 can be accounted for with $10^1$, since $10^1$ is greater than $2^2$. So why is there not a single nonrepeating digit, instead of $2$? – Klangen Sep 21 '18 at 20:57
• Disregard my previous question, I understand. je It's late... – Klangen Sep 21 '18 at 20:59

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’$$