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

-
@DJC That question is concerned with the cyclic nature of the numbers whereas I'm more interested in a proof that every cyclic number is the reciprocal of a full reptend prime. –  EuYu Aug 12 '11 at 2:29
If $n$ is the cyclic number and $d$ the number of digits (counting the $0$ if present), then we need to prove $(10^d-1)/n$ is a whole prime and also a primitive root modulo $10$. No doubt both parts will involve exploiting $n$'s cyclical nature and the arithmetic properties of its cycles. –  anon Aug 12 '11 at 3:21
@EuYu : I think this would be inventing a new proof for the statement. –  Iyengar Jan 31 '12 at 17:20
@Iyengar Meaning that the statement is currently unproven? –  EuYu Jan 31 '12 at 18:11

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

-

a probably flawed attempt

n=cyclic number m=number of digits of n

sums of digits of n $142857\\ 857142\\ 999999\\ \\ \space \\285714\\ 714285\\ 999999\\ \space \\428571\\ 571428\\ 999999\\ \space \\(m+1)n=xn+(m+1-x)n x\leq m+1$

sum $=(m+1)n \space\forall x$ every pair of last digts has same sum k modulo 10

$3\not|n \to 9|n \to k=9$

$3|m \to 999|m \to 27|n \to k=9$

$n(m+1)=99...9 \to \frac{1}{m+1}=0.n \land m+1$ is a reptend

not sure how to show m+1 is prime

-

The only if part is: if some number $n$ in base $b$ of length $d=\lfloor{\log_b n}\rfloor+1$ cycles for $2n$ through $(d-1)n$ then $n/(b^d-1)=1/k$, $k$ prime and not a factor of $b$.

(This definition excludes the solutions with leading zeros.)

I think the approach is to show $dn=n+(d-1)n$ must equal $b^d-1$ and hopefully the rest follows...

Let $$n=n_1 n_2\dots n_d$$ then $$n/(b^d-1)=0.\overline{n_1 n_2\dots n_d}$$ so $$bn/(b^d-1)=n_1.\overline{n_2\dots n_d n_1}=n_1+m_1n/(b^d-1) \text{ for some m_1 between 2 and d-1}$$

because $n$ is cyclic.

$$\therefore b=n_1(b^d-1)/n+m_1$$ and similarly $$b^i=n_1n_2\dots n_i(b^d-1)/n+m_i, 2 \le m_i \le d-1, m_d=1, 1\le i \lt d, m_i \text{ distinct }$$

So all of $n_1n_2\dots n_i(b^d-1)/n$ must be integers.

Specifically

$$n_1n_2\dots n_i(b^d-1)/n = b^i-m_i$$

$$\therefore (b^d-1)/n = (b^i-m_i) / n_1n_2\dots n_i$$

and reciprocating...

$$n/(b^d-1) = n_1n_2\dots n_i / (b^i-m_i), 2 \le m_i \le d-1, m_d=1, 1\le i \lt d, m_i \text{ distinct }$$

etc... Now just to show $n/(b^d-1) = 1/k, k$ prime and not a factor of $b$ :-) ...

-
Unfortunately, doesn't excluding leading zeros exclude almost all such numbers? –  EuYu Feb 3 '12 at 7:28
@EuYu: No, you can do a computer search for such numbers and, except for base 6 IIRC, only the bases that are perfect squares (or cubes, etc) don't have at least one cyclic number that don't need a leading zero. –  Mark Hurd Feb 3 '12 at 10:39