Repetend digit graphs for $1/n$ in base $b$

Question

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)\;.$$

---

     

---

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:

---

     

---

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?

Answer 1

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.)