10
$\begingroup$

Here is a decimal expansion of $\frac{1}{34}$: $$(1/34)_{10}=0.02941176470588235\overline{2941176470588235}\ldots$$ And here is a graphical representation of the 16-digit "repetend," as a directed repetend digit graph (my terminology): $$(2,9,4,1,1,7,6,4,7,0,5,8,8,2,3,5)\;.$$


      Digitsn34b10
I was exploring the digit-expansion of $1/n$ in base $b$—fixing $n$ while letting $b$ vary—and find it puzzling. Here is an example, for $n=51$, and bases $b=5,\ldots,50$. The top row shows base $b$, and underneath, the length of the repetend for $\frac{1}{51}$ in that base: $$ \left( \begin{array}{cccccccccccccccc} 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 16 & 16 & 16 & 8 & 8 & 16 & 16 & 16 & 4 & 16 & 8 & 2 & 2 & 1 & 8 & 16 \\ \end{array} \right) $$ $$ \left( \begin{array}{ccccccccccccccc} 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & 35 \\ 4 & 16 & 16 & 16 & 8 & 8 & 16 & 16 & 16 & 4 & 16 & 8 & 2 & 1 & 2 \\ \end{array} \right) $$ $$ \left( \begin{array}{ccccccccccccccc} 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\ 8 & 16 & 4 & 16 & 16 & 16 & 8 & 8 & 16 & 16 & 16 & 4 & 16 & 8 & 2 \\ \end{array} \right) $$ It is evident that the repetend length is a factor of $17{-}1$; and $n=3 {\cdot} 17$. I tried to understand when the repetend digit graphs were isomorphic, but a pattern is not evident. For example, for $\frac{1}{51}$, for bases $$b = 15,19,25,26,32,36,42,43,49 \;,$$ that graph is an octagon. Here are three of them:
      Digitsn51
So here is a specific question:

Q. Is it possible to predict which of the base-$b$ digit-expansions of $1/n$ result in isomorphic repetend digit graphs? In particular, graphs which are cycles? Perhaps specifically when $n$ is a prime?

$\endgroup$
4
  • $\begingroup$ Are you fixing $n$ and letting $b$ vary? I couldn't tell from the question. $\endgroup$
    – S. Carnahan
    Aug 24, 2014 at 1:17
  • $\begingroup$ Yes, fixing $n$ and letting $b$ vary. I will try to clarify... $\endgroup$ Aug 24, 2014 at 1:34
  • $\begingroup$ Probably this is not "continued-fractions" question. $\endgroup$ Aug 24, 2014 at 13:29
  • $\begingroup$ @AlexeyUstinov: You are right, my incorrect guess. Now removed that tag. $\endgroup$ Aug 25, 2014 at 2:24

1 Answer 1

7
$\begingroup$

The following remarks do not answer your questions completely, but they may nonetheless be helpful.

Note first that computing the base-$b$ expansion of $1/n$ is essentially the same thing as computing the powers of $b$ modulo $n$. Here is one way to write the steps of the base-$b$-expansion algorithm, which makes the connection clear: \begin{align*} 1 &= 0\times n + 1\\ b\times 1 &= q_1\times n + r_1\\ b\times r_1 &= q_2\times n + r_2\\ &\dots\\ b\times r_k &= q_k\times n + r_{k+1}\\ &\dots. \end{align*} At each stage, we divide $b$ times the previous remainder by $n$ to get the next remainder. The base-$b$ expansion is the sequence of quotients $q_k$. Since for all $k$, we have $r_{k+1}\equiv br_k\pmod{n}$, the remainders $1, r_1, r_2,\dotsc$ are the powers of $b$ modulo $n$.

To avoid some distracting details, let us restrict ourselves to $b$ that are relatively prime to $n$. (In this case the ``repetend'' begins immediately.) The element $b$ belongs to the multiplicative group $(\mathbf{Z}/n\mathbf{Z})^\times$ of units modulo $n$, whose order is $\phi(n)$ (Euler totient). Thus the length of the base-$b$ repetend always divides $\phi(n)$. If $n$ is prime, then any divisor of $\phi(n) = n-1$ will occur, since $(\mathbf{Z}/n\mathbf{Z})^\times$ is cyclic, but typically there will be further restrictions on the lengths of the repetends (which one can work out using the prime factorization of $n$).

The sequence of remainders $1, r_1, r_2, \dotsc$ repeats cyclically, where the cycle length is the (multiplicative) order of $b$ modulo $n$. From the algorithm, it is clear that $r_k$ determines $q_k$, and so the ``repetend digit graph'' for the base-$b$ expansion is a sort of contraction of this cycle. As long as $b$ is large compared to $n$, however, there will not be any contraction; indeed, if we have $b\geq n$, then $q_k$ determines $r_k$. (If $br = nq + s$ and $br' = nq + s'$ with $0\leq r,r',s,s'\leq n-1$, then $b(r-r') = s-s'$ and $|b(r-r')|<n$; if $b\geq n$, then we must have $r = r'$.) If $b$ is not too much smaller than $n$, then it is fairly unlikely that one will have a coincidence of quotients without having a coincidence of remainders. (Perhaps someone can think a bit more and improve that statement. You seem to have been lucky in your examples with 8-cycles in that somewhat small bases relative to 51 did not give contracted cycles. A somewhat large example with a contraction is the base-10 expansion of 1/17. It might be amusing to see how small a gap one can find between $b$ and $n$ with a contraction in the base-$b$ expansion of $1/n$.)

To answer your specific question (still with the restriction that $b$ is relatively prime to $n$): if $b\geq n$, all repetends will be cycles. The cycle length is the same as the multiplicative order of $b$ modulo $n$. One can determine the possible cycle lengths using the prime factorization of $n$, but there is no simple pattern in the multiplicative orders of elements modulo $n$. (One can, of course, make elementary statements about, for example, the length of the base-$b_1b_2$ repetend given the lengths of the base-$b_1$ and base-$b_2$ repetends. Such things are probably easier to work out by thinking about the group $(\mathbf{Z}/n\mathbf{Z})^\times$ rather than by thinking directly about fractions.)

$\endgroup$
1
  • $\begingroup$ These are remarkably insightful observations! I see your point that it is easier to think in terms of of $(\mathbf{Z}/n\mathbf{Z})^\times$ than in terms of fractions. $\endgroup$ Aug 25, 2014 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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