Cyclic Divisibility

The integer 865281023607 happens to be a multiple of 111111, but in
addition it can easily be verified that every cyclical rotation of
these decimal digits is also a multiple of 111111, as shown below

         865281023607  =  111111 *  7787537
         786528102360  =  111111 *  7078760
         078652810236  =  111111 *   707876
         607865281023  =  111111 *  5470793
         360786528102  =  111111 *  3247082
         236078652810  =  111111 *  2124710
         023607865281  =  111111 *   212471
         102360786528  =  111111 *   921248
         810236078652  =  111111 *  7292132
         281023607865  =  111111 *  2529215
         528102360786  =  111111 *  4752926
         652810236078  =  111111 *  5875298

Furthermore, if we reverse the digits of these number, we find that
each of them is again a multiple of 111111, as shown below

         706320182568  =  111111 *  6356888
         870632018256  =  111111 *  7835696
         687063201825  =  111111 *  6183575
         568706320182  =  111111 *  5118362
         256870632018  =  111111 *  2311838
         825687063201  =  111111 *  7431191
         182568706320  =  111111 *  1643120
         018256870632  =  111111 *   164312
         201825687063  =  111111 *  1816433
         320182568706  =  111111 *  2881646
         632018256870  =  111111 *  5688170
         063201825687  =  111111 *   568817

Of course, since the number

             10^12 - 1  =  999999999999

is a multiple of 111111, it's clear that the 10's complement of each 
of the above numbers is also a multiple of 111111.  In other words, 
the number 134718976392 AND its reversal AND all of their cyclic 
rotations are each multiples of 111111.

What's going on here?  Well, if we rotate the number 134718976392
to the right by one digit, and write the digits as a sequence, we
see that they represent a cycle of the Fibonacci recurrence 
s[n] = s[n-1] + s[n-2] reduced modulo 10:

 s[n]:  2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 ...
                                         |
        2 1 3 4 7  1  8  9  7  6   3   9 | 2   1   3    4  ....
                                         |

The period of this sequence is 12, so to express the repeating decimal
expansion

        0.213471897639 213471897639 213471897639 ...

as a ratio of integers we decompose it into a geometric series

                  /    1       1       1          \
    213471897639 (   ----- + ----- + ----- + ....  )
                  \  10^12   10^24   10^36        /


                 213471897639     1921249 * 111111       1921249
            =    ------------  =  ----------------  =    -------
                  10^12 - 1       9000009 * 111111       9000009

So, the fact that the sequence of digits gives a decimal number with
a large common divisor with 10^12 - 1 results in a significant 
reduction in the fractional expression for the repeating decimal.
We also note that this large common factor is (10^6 - 1)/(3^2).

More generally, we know that the period of any recurrence of the
Fibonacci sequence modulo 10 must be a divisor of the least common
multiple of the fundamental periods modulo 2 and 5.  The fundamental 
period modulo 2 is 2^2 - 1 = 3, whereas the fundamental period modulo 
5 is 5(5-1) = 20 (because 5 divides the discriminant of the Fibonacci 
polynomial).  Hence, the period of any Fibonacci sequence must be a 
divisor of 60.

Now, if j is a divisor of 60 there exists an integer G_j that divides
10^j - 1 such that if {d0, d1, d2, ..., dj} is any cycle of positive 
residues modulo 10 that satisfy the Fibonacci recurrence, then the 
integer
            d0 + d1*10 + d2*10^2 + ... + dj*10^j

is divisible by G_j.  This is why all the rotations of any such
sequence automatically are divisible by the same G_j.  Also, the
reverse recurrence has the same properties, noting that we can
write it as s[n-2] = -s[n-1] + s[n]  which has the reverse 
characteristic polynomial x^2 + x - 1, whose discriminant is the
same as that of x^2 - x - 1.  Of course, the divisibility of the
10's complement integers is obvious from the fact that G_k divides
10^k - 1.

The above is really just a special case of a much more general
phenomenon.  If the discriminant of a 2nd-degree polynomial f(x) is 
divisible by the odd prime p, then we can consider the sequences 
that satisfy the linear recurrence corresponding to that polynomial, 
and reduce the sequence modulo m = p or 2p.  The period of any
such reduced sequence must be a divisor of p(p-1) or 3p(p-1)
respectively.  If j is any such integer period length, then 
there exists an integer G_j that divides m^j - 1 such that if 
{d0, d1, d2, ..., dj} is any cycle of positive residues modulo 
10 that satisfy the Fibonacci recurrence, then the integer

            d0 + d1*m + d2*m^2 + ... + dj*m^j

is divisible by G_j.

For example, staying with the Fibonacci recurrence, suppose we
evaluate sequences modulo 5, which means they must have periods
dividing 20.  Once such sequence is

         1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1

Interpreting these as the digits of a number in the base 5, this
equals the decimal integer 

           20520701511336 = (2^3)(3^2)(13)(521)(42080281)

We can easily verify that this number, and all its rotations, 
reflections, and 5s-complements, share a greatest common divisor
of (2^3)(3)(13)(521) with the number

      5^20 - 1  =  (2^4)(3)(11)(13)(41)(71)(521)(9161)

For another example, consider the polynomial f(x) = x^2 - 4x - 9,
whose discriminant is 4*13 = 52.  Every sequence of residues mod 13
that satisfies this recurrence must have a period dividing 156.  One
such sequence, with a period of 12, is

               1 2 4 8 3 6 12 11 9 5 10 7

which gives an integer with the decimal equivalent

       13984822237218  =  (2)(3)(7)(41)(61)(157)(847997)

and we can verify that this numbers and all its rotations, reversals,
and 13s-complements share a common divisor of (2)(3)(7)(61)(157) with
13^12 - 1.

For just one more example, consider the same polynomial, but this time
evaluate the recurrence modulo 2(13) = 26.  One solution sequence,
having a period of 12, is

            1 2 17 8 3 6 25 24 9 18 23 20

which gives an integer with the decimal equivalent of

    76753544008735881  =  (3^6)(7)(19)(31)(37)(149)(4632011)

This number, and all its rotations, reflections, and 13s-complements
share a common factor of (3^4)(7)(19)(31)(37) with 26^12 - 1.

Incidentally, notice that m^2k - 1 splits as (m^k + 1)(m^k - 1), and
it appears that in most cases G_{2k} is a divisor of m^k - 1.  However
the exception is the case with the Fibonacci recurrence (mod 5), when
G_{20} contained factors from both 5^10 + 1 and 5^10 - 1.  This is
also the only one of our examples in which the period of the sequence
we examined was equal to the full period.

It's also interesting to examine the numbers produced by taking
every jth element of one of these sequences.  If j divides the period
of the sequence then obviously the new sequence has a period reduced
by a factor of j.  Such a sequence still shares a large common factor
with m^k - 1.  If j is coprime to the period of the sequence, then
the new sequence must be either the same as the original, or else
the reversal of the original.  For example, if we take every 3rd
element of the sequence with period 20 (mod 5) from above, we have

          1 0 1 4 2 2 0 2 3 4 4 0 4 1 3 3 0 3 2 1

which is simply the reversal of the original sequence.