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.

Return to MathPages Main Menu