Cyclic and Reverse Divisibility

Let N denote an n-digit integer in the base B, and let g denote the greatest common divisor of N and Bⁿ – 1. Now let Nʹ denote the result of rotating the digits of N one place to the right, wrapping the least significant digit d₀ 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 co-prime 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 12-digit 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¹² − 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 digit-reversal 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⁰, 3¹, 3², 3³, 3⁴, 3⁵, ..., 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₇[x] of polynomials with integer coefficients modulo 7:

The right hand factor is formally 1/(1 – x⁶), 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², and the second factor, evaluated in the field Z₇[x] is Q(x) = 1 + 2x – x² + 5x³, 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 6-complements.

For another example, consider the polynomial in Z₁₁[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¹⁰ − 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₁₇[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 base-17 digits 18d2g94f and its digit reversal f49g2d81 (and all their rotations and 16-complements) are divisible by the base-17 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 non-prime 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 second-order 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₁₀[x] can be verified by noting that

Therefore, we’ve shown that the decimal number 127361983749 and its digit-reversal 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₁₀[x] can be verified by noting that

Therefore the decimal number 213471897639 and its digit-reversal 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² + 0x³ + 3x⁴ + ... + 1x¹⁹, we have

This congruence can be verified by noting that

In this case the algebraic factor shared by F(x) and (1 – x²⁰) is just 1 + x² + x⁵ + x⁷, so we have found that the base-5 integer 12303314044320224101 and its digit-reversal (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² − 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 digit-reversal, 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³ = 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² − 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 base-13 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₍₁₃₎. 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 base-26 number with these digits, and the digit-reversal of this number, and all their rotations and 25s complements, are divisible by the cyclotomic divisor 111111₍₂₆₎.

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.

Return to MathPages Main Menu