Cyclic and Reverse Divisibility 

Let N denote an ndigit integer in the base B, and let g denote the greatest common divisor of N and B^{n} – 1. Now let Nʹ denote the result of rotating the digits of N one place to the right, wrapping the least significant digit d_{0} around to become the most significant digit. (For example, the number 1234 would become 4123.) Thus we have 



and therefore 


Since g divides the right hand side (and is coprime to B), it also divides the left, and consequently g divides Nʹ. From this it follows that g divides every rotation of the digits of N. 

To illustrate, with B = 10 and n = 12 we have the factorization 



Arbitrarily selecting the prime divisors 13, 37, and 9901, and multiplying these together with a completely arbitrary factor 73151, we have the 12digit number 



It’s easy to verify that all the rotations of this number are divisible by g = (13)(37)(9901). In addition, the 9s complement of this number, equal to 651627067468, is obviously also divisible by g, as are all the rotations of that number, since 10^{12} − 1 = 999999999999. 

However, the digit reversal of the number in the preceding example is not divisible by g. Our objective is to show how to construct integers N such that the digitreversal of N, denoted by rev(N), is also divisible by g. Let us begin by working in the base B = 7, and consider an integer whose digits, from least to most significant, consist of the powers of 3 modulo 7. Thus the digits are 3^{0}, 3^{1}, 3^{2}, 3^{3}, 3^{4}, 3^{5}, ..., which when reduced modulo 7 have the values 1, 3, 2, 6, 4, 5, after which they repeat. Therefore, using the formal geometric series, we can write the following identity in the ring Z_{7}[x] of polynomials with integer coefficients modulo 7: 



The right hand factor is formally 1/(1 – x^{6}), so we can write this as 



Indeed we can show by direct factorization that 



The first factor on the right side is P(x) = 1 + x + x^{2}, and the second factor, evaluated in the field Z_{7}[x] is Q(x) = 1 + 2x – x^{2} + 5x^{3}, which can be verified by noting that 



In general, reversing the coefficients of a polynomial gives a polynomial with the same factors but with their coefficients reversed. Since the factor P(x) is palindromic, it is also a factor of the polynomial with reversed coefficients. Therefore, setting x = B = 7, we see that the numbers (in the base 7) 132645 and 546231 both share the common factor of 111 with the number 666666, as do all their rotations and 6complements. 

For another example, consider the polynomial in Z_{11}[x] whose digits are the powers of 2 modulo 11. Similar to the previous example, we have the identity 



where 


The division in the expression for Q(x) can be verified by noting that 



Letting “a” denote the digit 10 in the base 11, these relations show that the integer 12485a9736 and its digit reversal 6379a58421 (and all their rotations and 10s complements) share the common factor 11111 with the number 11^{10} − 1. 

In both of the above examples the period of the coefficients of the geometric series modulo the odd prime base B was equal to B – 1, but in general the period is only guaranteed to be a divisor of B – 1. For example, the powers of 8 module 17 are the eight residues 1, 8, 13, 2, 16, 9, 4, 15, after which the cycle repeats. Therefore, in the field Z_{17}[x] we have 



where 


The division in the expression for Q(x) can be verified by noting that 



Letting a, b, c, etc., denote the digits 10, 11, 12, etc., it follows that the integer with base17 digits 18d2g94f and its digit reversal f49g2d81 (and all their rotations and 16complements) are divisible by the base17 number 1111. 

So far we’ve focused on prime bases, and considered only sequences of coefficients (or digits) formed by geometric series, i.e., consecutive powers of a given integer r modulo the base B, which have a period n. We have found that the corresponding polynomial factors as 



We can generalize this nonprime bases, and to allow other sequences of digits. For example, consider the sequence of integers 1, 2, 7, 23, 76, 251, ..., whose terms satisfy the secondorder linear recurrence relation s_{k} = 3s_{k−1} + s_{k−2}. These numbers have the generating function 



When the coefficients of the series are reduced modulo 10 they have a period of 12, and by the same reasoning as we used above we can write the relation 



where 


The division in the expression for Q(x) in Z_{10}[x] can be verified by noting that 



Therefore, we’ve shown that the decimal number 127361983749 and its digitreversal 947389163721 (and all their rotations and 9s complements) are divisible by 111111. 

For another example, consider the Lucas sequence 2, 1, 3, 4, 7, 11, 18, ..., consisting of integers that satisfy the Fibonacci recurrence s_{k} = s_{k−1} + s_{k−2}. The generating function for this sequence is 



Just as in the previous example, these coefficients have a period of 12 when reduced modulo 10, and we have the factorization 



where 


Again the division in the expression for Q(x) in Z_{10}[x] can be verified by noting that 



Therefore the decimal number 213471897639 and its digitreversal 936798174312 (and all their rotations and 9s complements) are divisible by 111111. 

In each of the examples discussed above the common divisor has been of the form “111...11” in the respective base, but this is not always the case. Consider, for example, the integer whose digits (from least to most significant) in the base 5 are one complete cycle of the numbers 1, 2, 3, 0, 3,... satisfying the Fibonacci recurrence modulo 5. The period of the cycle is 20. Letting F(x) denote the polynomial 1 + 2x + 3x^{2} + 0x^{3} + 3x^{4} + ... + 1x^{19}, we have 



This congruence can be verified by noting that 



In this case the algebraic factor shared by F(x) and (1 – x^{20}) is just 1 + x^{2} + x^{5} + x^{7}, so we have found that the base5 integer 12303314044320224101 and its digitreversal (and all their rotations and 4s complements) are divisible by 10100101 in the base 5. Unlike the previous examples, in this case the universal divisor includes factors from both B^{n/2} – 1 and B^{n/2} + 1. This is also the only one of our examples in which the base equals the discriminant of the characteristic polynomial. Also the period of the sequence in this case equals the full period of the recurrence. 

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 modulo 10 must be a divisor of 60. The longest such sequence corresponds to the decimal number 



It can be shown that this number, and its digitreversal, and each of their rotations and 9s complements, are divisible by the decimal number 



Returning to our previous example for the decimal number N = 213471897639, one simple way of seeing that this number and its digit reversal are both divisible by 11 is to note that the base B=10 is congruent to 1 modulo 11, so the decimal expansion of N modulo 11 is simply the sum of the digits with alternating signs. (This is an old arithmetic trick to check decimal numbers for divisibility by 11.) Indeed we find 



Obviously this sum is unaffected by rotating or reversing the digits. Similarly if we write this number in the base B^{3} = 1000 it has the digits 213, 471, 897, 639, so the values modulo 999 and 1001 are given by the sums with all positive and with alternating signs (respectively) 



The first congruence show that the number and its reversal are both divisible by 1001, and the second congruence shows that they are both divisible by 111. Consequently both N and rev(N) are divisible by 111111, as shown previously. This also implies that these sums are undisturbed by rotating the digits. 

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, gives the base13 number 124836cb95a7 where a,b,c denote the digits 10, 11, and 12. We can verify that this number, its digit reversal, and all their rotations and 12s complements, are divisible by the cyclotomic divisor 111111_{(13)}. We also note that the sequence 1, 2, 4, 8, 3, 6, ... etc. is also just 2^{k} mod 13. 

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 



We can verify that the base26 number with these digits, and the digitreversal of this number, and all their rotations and 25s complements, are divisible by the cyclotomic divisor 111111_{(26)}. 

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 B^{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 3^{rd} element of the sequence with period 20 (mod 5) from above, we have 10142202344041330321, which is simply the reversal of the original sequence. 
