Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 8 down vote accepted

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

share|improve this answer
    
Great, thanks for that quick response. –  yunone Sep 16 '10 at 7:16
add comment

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)\:$ with the obvious inverse $\rm\;(b,c)\to (a = (11\:b-c)/10,\:b)\:$ which clearly exists in any ring $\rm\:R\:$ where $10\:$ has an inverse. In particular, let $\rm\;R =\mathbb Z\pmod 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$. But 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.

The method also works for nonlinear recurrences with invertible shift map, e.g. from one of my old posts

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). I've even encountered some solutions that 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 the cycle 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.

NOTE 2 $\;\;$ For another very nice application of orbit decompositions see my recent post which illustrates how they prove key for finding polynomial and rational function solutions of recurrences.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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