11
$\begingroup$

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.

  • 0
    http://math.stackexchange.com/questions/443/why-is-the-decimal-representation-of-1-7-cyclical2011-08-12
  • 0
    @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.2011-08-12
  • 1
    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.2011-08-12
  • 1
    @EuYu : I think this would be inventing a new proof for the statement.2012-01-31
  • 1
    @Iyengar Meaning that the statement is currently unproven?2012-01-31

3 Answers 3

4

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}

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

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

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_{0cyclotomic 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$.

0

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

  • 0
    Unfortunately, doesn't excluding leading zeros exclude almost all such numbers?2012-02-03
  • 0
    @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.2012-02-03
0

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