1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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 $\endgroup$ – Ross Millikan Sep 16 '18 at 17:17
  • $\begingroup$ @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. $\endgroup$ – Klangen Sep 17 '18 at 12:20
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 17 '18 at 13:55
  • $\begingroup$ @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$? $\endgroup$ – Klangen Sep 18 '18 at 7:01
  • $\begingroup$ It will be a factor of $\phi(b)$, Euler’s totient function. I don’t know a general way to find it $\endgroup$ – Ross Millikan Sep 18 '18 at 14:21
2
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Klangen Sep 21 '18 at 17:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 21 '18 at 17:28
  • $\begingroup$ Thank you, I understand it perfectly now! $\endgroup$ – Klangen Sep 21 '18 at 19:57
  • $\begingroup$ 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$? $\endgroup$ – Klangen Sep 21 '18 at 20:57
  • $\begingroup$ Disregard my previous question, I understand. je It's late... $\endgroup$ – Klangen Sep 21 '18 at 20:59
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.