Why do primes other than 2 and 5 divide infinitely many repunits?

Solution 1:

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 analyze periodicity of 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.

Solution 2:

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