I first noticed this is true for the integers of the sequence $9, 99, 999, 9999,\dots$, since for some term $a_n=10^n-1$ in the sequence and $p$ a prime other than $2$ or $5$, we have $a_n\equiv 0 (mod\ p)\Leftrightarrow 10^n\equiv 1 (mod\ p)$ and we can find infinitely many $n=k(p-1)$ so that $10^n=(10^{p-1})^k\equiv 1^k\equiv 1 (mod\ p)$ by Fermat's little theorem.

I'm curious, is there a similar way to show this is true for repunits $1, 11, 111,\dots$?


Note that the $n$-th repunit is $r_n=(10^n-1)/9$. If $p$ is a prime and $p\ne 3$ then $p\mid r_n$ iff $p\mid(10^n-1)$. (This is due to Euclid's lemma that $p\mid ab$ implies $p\mid a$ or $p\mid b$.) So when $p\notin\{2,3,5\}$ the problem reduces to the one you've done.

Only the case $p=3$ remains. Now remember that $3\mid n$ iff $3$ divides the digital sum of $n$ (the sum of the decimal digits of $n$)....

  • $\begingroup$ Great, thanks for that quick response. $\endgroup$ – yunone Sep 16 '10 at 7:16

The essence of the matter is both strikingly simple and extremely general. Namely, there are infinitely many solutions to your congruence simply because the solutions lie in the orbit of an invertible map on a finite set. But such permutations decompose into finite cycles - so they repeat infinitely often upon iteration. Below I discuss your simple linear example and then I show how the technique generalizes to nonlinear recursions.

First we convert $\rm\,f_n = 10^n\!-1 \,$ to shift form. Note $\rm\,f_{n+2}-f_{n+1}\! = 9\cdot 10^{n+1}\! = 10\ (f_{n+1}\!-f_n) \,$ which yields the recurrence relation $\rm\,\, f_{n+2} =\, 11\ f_{n+1}-10\ f_n. \,$ This is simpler as a shift map on pairs: $\rm\,S\, :\, (f_n,f_{n+1})\to (f_{n+1},f_{n+2}) =\, (f_{n+1},\,11\,f_{n+1}\! - 10\ f_n). \,$ Extended to all pairs it yields the map $\rm\,S\, :\, (a,b)\to (b,\,11\,b-10\,a = c).\,$ Computing the inverse of this map we obtain $\rm\,(b,c)\to (a = (11\,b-c)/10,\,b),\,$ which exists in any ring $\rm\,R\,$ where $10\,$ has an inverse. In particular, let $\rm\,R =\mathbb Z/m\,$ be the ring of integers modulo $\rm\,m>1\,$, for any $\rm\,m\,$ coprime to $10.\,$ Since $\rm\,R \,$ is finite, so too is its set of pairs $\rm R^2.\,$ On such pairs the shift map $\rm\,S \,$ is an invertible map on a finite set, so it is a permutation. Therefore its orbit decomposition consists of finite cycles. Thus the values $\rm f_n$ all occur in the orbit of the initial condition pair $\rm (f_0,f_1) = (0,9)$, and each value necessarily occurs infinitely many times since the shift map successively steps along the finite circular orbit.

This also works for nonlinear recurrences with invertible shift map, e.g. from an old post

Exercise $\,\,$ A sequence $\rm f_n$ satisfies the recurrence $\rm\, f_{n+2} = f_{n+1}^{\,2}\! - f_n,\,$ with $\rm\, f_1 = 39,\, f_2 = 45.$
Prove that $\, 1986 \,$ divides infinitely many terms of the sequence.

Hint $\,\,$ The shift map is $\rm\, (a,b)\to (b,\,b^2-a = c)\,$ with inverse $\rm\, (b,c)\to (a = b^2-c,\, b)\,$
and maps $\ (39,45)\to (45,0) \ \pmod {1986}$

Note $\,\,$ When the recurrence is linear the shift map has a matrix representation, which may be used to quickly compute the terms of the recurrence by fast exponentiation algorithms (e.g. repeatedly squaring). However, neither the matrix nor any other consequences of linearity are required to deduce the cyclicity properties above. Often many students (and even some professors) don't realize this, which can lead to obfuscated solutions (compared to the simple approach above). Some solutions completely overlook the innate symmetry and, as a result, end up completely reinventing the wheel, i.e. discovering the innate cycle structure completely from scratch - not realizing that it is simply a special case of cyclic structure of permutations, i.e. orbit decomposition. The moral of the story is: always look for any innate symmetries of a problem before diving in head-first to apply more brute-force techniques.

For another nice application of orbit decompositions see this answer, which illustrates how they prove key for finding polynomial and rational function solutions of recurrences.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.