TITLE: Repetend digit graphs for $1/n$ in base $b$
QUESTION [10 upvotes]: 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?

REPLY [7 votes]: 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.)
{"set_name": "stack_exchange", "score": 10, "question_id": 179240}