Cyclic numbers are characterized by the reciprocals of full reptend primes?

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.

Solution 1:

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

Solution 2:

I consider Matthew L. Wright's excellent article highly worth reading before approaching this problem. It outlines how long division, the ring of integers modulo a prime $p$ and its group of units $U_p$ is central to understanding the problem, and demonstrates the "if" direction: Every "full reptend prime", an odd prime $p$ for which $10$ is a primitive root, generates (corresponds to) a (unique) cyclic number (by the map) $n=\frac{10^{p-1}-1}{p}=\lfloor10^{p-1}/p\rfloor$ with period/length $d=p-1$. Some partial work in the "only if" direction follows below.

Suppose that $$n=(n_1n_2\cdots n_d)_{10}=\sum_{i=1}^{d}n_i10^{d-i}$$ is a cyclic number, i.e., for each $1<k \le d$, the $k$th multiple $kn$ of $n$ has decimal representation $$kn=(n_{\sigma_k(1)}n_{\sigma_k(2)}\cdots n_{\sigma_k(d)})_{10} =\sum_{i=1}^{d}n_{\sigma_k(i)}10^{d-i},$$ where $\sigma_k\in S_d$ is a cyclic permutation (bijection) of $\{1,2,\dots,d\}$ satisfying $$\sigma_k(i)\equiv{i+t_k}\pmod{d}$$ for some shift $0\le t_k<d$; let $t_1=0$ (since $1n=n$ fixes all the digits of $n$). Note that the map $k\to t_k$ is a bijection from $\{1,\dots,d\}$ to $\{0,\dots,d-1\}$. We wish to prove that $$\frac1{d+1}=\frac{n}{10^d-1}=(0.\overline{n_1n_2\cdots n_d})_{10},$$ i.e., that $(d+1)n=10^d-1$. Let $s=\sum_{i=1}^{d}n_i$ be the sum of the digits of $n$. Noting that $$ \frac{d(d+1)}{2}n = \sum_{k=1}^{d}kn =\sum_{k=1}^{d}\sum_{i=1}^{d}n_{\sigma_k(i)}10^{d-i} =\sum_{i=1}^{d}\sum_{k=1}^{d}n_{\sigma_k(i)}10^{d-i} =s\sum_{i=1}^{d}10^{d-i}=\frac{10^d-1}{10-1}s, $$ we have $$ (d+1)n=\frac{2s}{9d}\left(10^d-1\right) \qquad\mbox{or}\qquad u=\frac{2s}{9d}=\frac{(d+1)n}{10^d-1}, $$ so what remains is to show that $2s=9d$, or $$\mbox{(wanted):}%\qquad\boxed{2s=9d}\quad\mbox{or} \quad\boxed{s=\frac92d} \quad\mbox{or}\quad\boxed{n=\frac{10^d-1}{d+1}} \quad\mbox{or}\quad\boxed{u=1} . $$ Note that the desired quantity for $s$ is the expected value of the sum of $d$ equiprobable decimal digits, and the desired quantity for $n$ implies a cyclic, repeating fraction of length $d$ for $\frac1{d+1}$ upon performing long division.

Perhaps a thorough consideration of the material in the article mentioned above should be enough to stop here (see also the last paragraph below). But if we could prove it by even more elementary means, without resorting to the structure of cyclic groups and needing to assume that $p$ is an odd prime so that $d$ is even and $t_{1+d/2}=d/2$ (since the order of $10$ modulo $p$ is even and hence $10^{(p-1)/2}\equiv-1\pmod p$), we might continue as below.

Now the "trivial" case $n=1$ gives rise to the fraction $0.\overline{1}=\frac19$, with $s=1$ and a succession of $d=8$ multiples, which are not cyclic, and do not satisfy this equation or give rise to a full reptend prime. Therefore, since we have already assumed $n$ is a cyclic number, we can also assume, without loss of generality, that $d>1$. Backtracking slightly in preparation to examine things modulo $10$, we have that $$\frac{d(d+1)}2\cdot9n=s\left(10^d-1\right)$$ $$\implies s \equiv \frac{d(d+1)}2 \cdot n \pmod{10}.$$

Also, since $dn$ has $d$ digits, we have $$ \frac29\frac{s}{d+1}=\frac{dn}{10^d-1}\le1 \quad\implies\quad s\le\frac92(d+1), $$ a promising upper bound which could be enough if we also had $s\ge\frac92(d-1)$ and ${2s}\equiv{9d}\pmod{10}$. This is as far as I have gone by elementary means, and is enough to see where I started in 2012 with the general base $b$.

However, I suspect that the answer is pretty clear once one realizes that the order (minimal power) $d$ of $10$ (to reach $1$) modulo an odd prime $p$ is always even, and that $10^{d/2}\equiv-1\pmod{p}$ will always hold; this, then, implies that the second half of the sequence of cyclic numbers will always complement the first half, adding to $9$ digit by digit, so that for $1\le k\le\frac{d}2$ and $j=k+\frac{d}2$, we will have $(kn)+(jn)=(9\cdots9)_{10}=10^d-1$, where the addition is $9$ in each decimal place with no carries, i.e., $n_{\sigma_k(i)}+n_{\sigma_j(i)}=9$ for each $1\le i\le d$.

The first few cyclic numbers and the full reptend primes generating them are given below:

7 -> 142857
17 -> 0588235294117647
19 -> 052631578947368421
23 -> 0434782608695652173913
29 -> 0344827586206896551724137931
47 -> 0212765957446808510638297872340425531914893617
59 -> 0169491525423728813559322033898305084745762711864406779661
61 -> 016393442622950819672131147540983606557377049180327868852459
97 -> 010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567
109 -> 009174311926605504587155963302752293577981651376146788990825688073394495412844036697247706422018348623853211
113 -> 0088495575221238938053097345132743362831858407079646017699115044247787610619469026548672566371681415929203539823
131 -> 0076335877862595419847328244274809160305343511450381679389312977099236641221374045801526717557251908396946564885496183206106870229
149 -> 0067114093959731543624161073825503355704697986577181208053691275167785234899328859060402684563758389261744966442953020134228187919463087248322147651
167 -> 0059880239520958083832335329341317365269461077844311377245508982035928143712574850299401197604790419161676646706586826347305389221556886227544910179640718562874251497
179 -> 0055865921787709497206703910614525139664804469273743016759776536312849162011173184357541899441340782122905027932960893854748603351955307262569832402234636871508379888268156424581
181 -> 005524861878453038674033149171270718232044198895027624309392265193370165745856353591160220994475138121546961325966850828729281767955801104972375690607734806629834254143646408839779
193 -> 005181347150259067357512953367875647668393782383419689119170984455958549222797927461139896373056994818652849740932642487046632124352331606217616580310880829015544041450777202072538860103626943