﻿ Six Lemmas on Divisibility and Remainders for the Division of Polynomials
San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
USA

Six Lemmas on
Divisibility and Remainders
for the Division of Polynomials

## 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) = cnkn + cn-1kn-1 + … + c1k + c0

where C is the sequence of coefficients cncn-1…c1c0, 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.,

#### [cn+cn-1+…+c1+c0] = 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)ncn+(−1)n-1cn-1+…−c1+c0] = P(C, −1)

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

## Two Divisibility Lemmas

Note that

#### (k−h)(kn-1 + kn-2h + kn-3h² + … + khn-2 + hn-1) = kn − hn

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

Thus the lemma:

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

Now consider the polynomial

#### P(C, k) = cnkn + cn-1kn-1 + … + c1k + c0

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

#### [ P(C, k) − P(C, h)] = cn(kn−hn) + cn-1(kn-1−hn) + … + c1(k−h)

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

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

## 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

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

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: