Background

It was found first that the sum of the digits of a decimal number is essentially equal to its remainder upon division by 9. Furthermore the remainder modulo 9 of the product of two numbers is equal to the remainder modulo 9 of the product of the remainders of the two numbers. This is a property of remainder arithmetic. Later it was found that the net sum of the digits of a decimal number created by alternately adding and subtracting its digits is equal its remainder upon division by 11.

A decimal representation of a number is a polynomial in powers of ten. The above relationships generalize, as shown below, to the representations of numbers to any other integer base beside ten. They further generalize to polynomials with coefficients and base of any real numbers or any other mathematical field, but that is a different story that will be dealt with elsewhere.

The Analysis

Consider a polynomial

P(C, k) = c_nkⁿ + c_n-1k^n-1 + … + c₁k + c₀

where C is the sequence of coefficients c_nc_n-1…c₁c₀, which is the representation of the number N=P(C, k) to the base k if all of the coefficients are nonnegative and less than k.

The sum of the coefficient can be represented as the value of P(C, k) with k set equal to 1; i.e.,

[c_n+c_n-1+…+c₁+c₀] = P(C, 1)

Likewise the alternating net sum of the digits of a number is equal to the value of P(C, k) with k set equal to −1; i.e.,

[(−1)ⁿc_n+(−1)^n-1c_n-1+…−c₁+c₀] = P(C, −1)

There is also the trivial special case of the remainders modulo k, [P(C, k) mod k] which is equal to c₀. This is the value of P(C, k) with k set equal to zero.

Two Divisibility Lemmas

Note that

(k−h)(k^n-1 + k^n-2h + k^n-3h² + … + kh^n-2 + h^n-1)
= kⁿ − hⁿ

This is established by representing the two terms created from the LHS as

kⁿ + k^n-1h + k^n-2h² + … + k²h^n-2 +kh^n-1
               − (k^n-1h + k^n-2h² + k^n-3h³ + … + kh^n-1 + hⁿ)
        __________________________________________
kⁿ − hⁿ

Thus the lemma:

Lemma1: For all n, (k−h) is a factor of kⁿ−hⁿ.

Now consider the polynomial

P(C, k) = c_nkⁿ + c_n-1k^n-1 + … + c₁k + c₀

Now form P(C, h) and [ P(C, k) − P(C, h)]

[ P(C, k) − P(C, h)] = c_n(kⁿ−hⁿ) + c_n-1(k^n-1−hⁿ) + … + c₁(k−h)

Note that (k−h) is a factor of each term of the above and therefore is a factor of the sum. Consequently

Lemma 2: For any polynomial P(C, k), [ P(C, k) − P(C, h)] is divisible by (k−h).

This means that

[ P(C, k) − P(C, h)] = (k−h)Q

where Q is a polynomial in k and h. Hence

P(C, k) = P(C, h) mod (k−h)

Thus P(C, h) is in the nature of a remainder upon the division of P(C, k) by (k−h). If 0≤P(C, h)<(k−h) then it is the remainder. If not, the remainder is easily obtained by a simple operation such as [(k−h)+P(C, h)] when P(C, k) is negative.

Note the special cases

P(C, k) = P(C, 1) mod (k− 1)
P(C, k) = P(C, −1) mod (k+1)
because (k−(−1))=(k+1)
P(C, k) = P(C, 0) mod k

Two Lemmas Concerning Remainders

Let N, M and p be three numbers. The remainders r and s of N and M, respectively, with respect to p are numbers 0≤r<p and 0≤s<p such that there exist two integers K and L such that

N = Kp + r
and
M = Lp + s

Let Rem(Q, p) denote the remainder function, the remainder of q with respect to p. Then

Lemma 3:
Rem(N+M, p) = Rem(Rem(N, p)+Rem(M, p), p)

And

Lemma 4:
Rem(N*M, p) = Rem(Rem(N, p)*Rem(M, p), p)

The proofs consist of noting that Kp and Lp, the multiples of p in N and M are irrelevant in determining the remainders.

Remainders for Sums
and Products of Polynomials

Now consider two polynomials in k, P(C , k) and P(D, k) and form their sum S(C+D, k)=P(C, k)+P(D, k) and their product Q(E, k)=P(C, k)*P(D, k). Then

S(C+D, h) = P(C, h) + P(D, h)
which is the same as
[S(C+D, k) mod (k−h)] = [P(C, k) mod (k−h)] + [P(D, k) mod (k−h)]

and

Q(E, h) = P(C, h)*P(D, h)
which is the same as
[Q(E, k) mod (k−h)] = [P(C, k) mod (k−h)]*[P(D, k) mod (k−h)]

Restated these are:

Lemma 5:
Rem(P(C, k) + P(D, k), (k−h)) = Rem(Rem(P(C, k), (k−h))+P(D, k), (k−h)))
= Rem(P(C, h)+P(D, h), (k−h))

Lemma 6:
Rem(P(C, k)*P(D, k), (k−h)) = Rem(Rem(P(C, k), (k−h))*P(D, k), (k−h)))
= Rem(P(C, h)*P(D, h), (k−h))