[Math] Cyclic numbers are characterized by the reciprocals of full reptend primes

decimal-expansionnumber theoryprime numbers

The number $142,857$ is widely known as a cyclic number, meaning consecutive multiples are cyclic permutations, i.e.

$1 × 142,857 = 142,857$

$2 × 142,857 = 285,714$

$3 × 142,857 = 428,571$

and so on.

142857 is the repeating unit of $\frac{1}{7} = 0.\overline{142857}$ and in fact, every prime for which $10$ is a primitive root will generate a cyclic number (if we allow $0$ as a first digit, for example $0588235294117647$ which is the repeating unit of $\frac{1}{17}$). These primes are called full reptend primes.

From what I've read, it seems that there is a bijection between full reptend primes and cyclic numbers: a number is cyclic if and only if it is the repeating unit for the reciprocal of a full reptend prime.

I was able to find a proof for the if part. I was wondering if anyone can provide a proof for the only if part.

Edit: It's been a while since I posed this question and I still haven't found a proof. I've added a bounty in hopes of prompting some interest.

Best Answer

Here is a possible line of approach, lacking only the insight why $(d+1)\frac{n}{b^d-1}$ must be $1$.

If the base $b$ representation of a number $n$ is cyclic of (exact) length $d\geq\lceil{\log_b n}\rceil$ (with inequality for leading zeros), then the first $d$ consecutive multiples of $n$, $\{kn|1\leq k\leq d\}$, exhaust (i.e. are in bijection with) all the cycles, which in turn correspond bijectively with the repeating base-$b$ expansions of $\frac{kn}{b^d-1}\in(0,1)$. Their sum satisfies $$ \frac{b^d-1}{b-1}s= \frac{d(d+1)}{2}n \qquad\text{where}\qquad s=d\frac{b-1}{2}\frac{(d+1)n}{b^d-1}\in\mathbb{N} $$

is the sum of the base-$b$ digits of $n$. Since each digit is between $0$ and $b-1$, $s$ must lie between $0$ and $d(b-1)$ inclusive. However, for the sum $s$, the range must be exclusive (for $b>2$), since otherwise the digits would all be the same ($0$ or $b-1$) and $d$ would have to be $1$. Thus we have $$0<\frac{s}{d}=\frac{b-1}{2}\frac{(d+1)n}{b^d-1}<b-1$$ $$0<0.\overline{n_{d-1}\dots n_0}=\frac{(d+1)n}{b^d-1}<2$$ where the middle quantities in the first and second lines are the average value $\frac{1}{d}\sum a_i$ of the base-$b$ digits of $n$, and the fraction obtained from repeating the digits of $n=\sum_0^{d-1}a_ib^i$ after the base-$b$ decimal point, respectively. These quantities are rational numbers, but not guaranteed to be integers. What we want to show however, as we shall see, is that the latter quantity is in fact an integer, and therefore $1$.

Let's assume that $d>1$, and that $d$ is minimal, in the sense that the $n$ is not a repeated or decomposable cycle:

$$ \nexists c\vert\;d, \quad 1<c<d \quad(c\;\text{a proper divisor of}\;d) \quad\text{with} \quad\frac{b^{d}-1}{b^c-1}\vert\;n. $$

We should also note that $s\equiv n\pmod{b-1}$, i.e. that $\frac{n-s}{b-1}\in\mathbb{Z}$, since each base-$b$ digit of $n$ remains fixed modulo $b-1$ when multiplied by its respective nonnegative power of $b$.

We actually want to show that $$n=\frac{b^d-1}{d+1} \qquad\text{and that}\qquad t=\frac{b^d-1}{n}=d+1\in\mathbb{N}$$ is in fact prime with $b$ as primitive root.

Perhaps there is a good argument why $s=d\frac{b-1}{2}$ lies exactly in the middle (the expected value) of the prescribed range or, equivalently, that the average value of the digits of $n$ base $b$ is $\frac{b-1}{2}$, or that the first noncyclic multiple of $n$ (which we know is the $d+1^\text{th}$) satisfies $(d+1)n=b^d-1$ (which is $b-1$ times the repunit of length $d$).

Certainly we know that the sequence $\{kn\}_{k=1}^d$ is increasing and bounded by $b^d$ (since each term has at most $d$ digits base $b$). Therefore, they must correspond with the lexicographic ordering of cyclically shifted length-$d$ strings starting with $n$, zero-padded if necessary (i.e. if $b^{d-1}>n$). And since $(d+1)n=dn+n$ is the sum of the smallest and largest of these cyclic shifts, its leading digit must also be the sum of the smallest and largest digits of $n$ (unless a carry increases the sum to $\geq b^d$).

If we need to resort to an examination in more detail of the products $\{kn\}_{k=1}^d$ and their relation to base-$b$ shifts of $n$, we need not resort to naming $n$'s digits. We can in stead rely on the division algorithm, and note that if $$ n=q_k b^k+r_k \quad\text{with}\quad \left\{\begin{matrix} q_k=\lfloor{b^{-k}n}\rfloor,\\ r_k=n-b^kq_k \end{matrix}\right. \quad\text{for}\quad 0\leq k\leq d \quad\text{and if}\quad n_k=r_k b^{d-k}+q_k, $$ then $\{n_k\}_{k=1}^{d-1}$ is a permutation of $\{nk\}_{k=1}^{d-1}$. Note that if $n$ and $n_k$ are identified with strings of $d$ letters in the alphabet $\{0,\dots,b-1\}$, then $n_k=\text{right}(n,k)+\text{left}(n,d-k)$, where the plus symbol here indicates string concatenation and the right and left functions are familiar from some programming languages, since $q_k$ and $r_k$ are the left $d-k$ and right $k$ digits of $n$ base $b$ respectively.

Once we can establish that $n=\frac{b^d-1}{d+1}$, we would have that $b^d\equiv 1\pmod t$. From here we could argue that $b$ must have order $d$ modulo $t$ using the minimality of $d$: if $1<c=\text{ord}_t(b)<d$, then we would have a nontrivial repunit factorization $$ \frac{b^c-1}{t}\cdot\frac{b^d-1}{b^c-1}=n $$ so that $n$ is a repetition of a shorter cycle of length $c$, contradicting our assumption.

But this would prove the result, since then $t-1=d=\text{ord}_t(b)\leq\phi(t)\leq t-1$, i.e. we would have sandwiched Euler's totient function $\phi(t)$ into attaining its theoretical maximum, which only occurs when $t$ is prime, while on the other hand, the order of any element $b$ mod $t$ only attains $\phi(t)$ when the element $b$ is a primitive root, i.e. a generator of $(\mathbb{Z}/t\mathbb{Z})^*$.

Finally (just for fun), note that a start at factoring $n$ for $d>1$ is $$ n=\frac{b^d-1}{t}=\frac{1}{t}\prod_{0<c|d}\Phi_c(b) $$ where $\Phi_c(x)$ denotes the cyclotomic polynomial of degree $c$, and the product above will be a partial factorization with $\tau(d)$ terms, one of which must be divisible by the prime $t$, where $\tau(d)$ is the number of positive divisors of $d$.

Related Question