San José State University


applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

The DigitSum of a Number and
Its Remainder for Division by Nine

Consider a non-negative integer expressed in Base 10 notation. Its DigitSum is the sum of its digits computed iteratively until a single digit result is obtained. For example, the sum of the digits of 386 is 3+8+6=17. Then the sum of the digits of 17 is 8. Thus 8 is the DigitSum of 386. The DigitSum function of an integer Z will be denoted as D10(Z). Thus D10(386)=D10(17)=8.

One remarkable fact about the DigitSum function is that it is equal to the remainder for a number upon division by 9, with the provision that 9 and 0 are equivalent. Let the remainder upon division by 9 for a non-negative integer Z be denoted as r9(Z). The proposition is that

D10(Z) = r9(Z)
if D10(Z) belongs to {1, 2, … 8}
and
if D10(Z)=9 then r9(Z)=0.

There is nothing special about the base 10 notation. For any base B the DigitSum of any integer is equal to its remainder upon division by (B-1), with the provision that a DigitSum of (B-1) is equivalent to a remainder of 0 upon division by ((B-1).

The proof will be carried out for numbers in base 10 notation, but the extension to an arbitrary base B is obvious.

First some of the properties of remainder arithmetic must be considered. The remainder for a number N for division by M is an integer r between 0 and (M-1) such that N=Mk+r for some integer k.

Lemma: The remainder of N for division by M is the same as the remainder of N-hM for any hM≤N.

Proof:

If N-hM = kM + r for 0≤r<M then also

N = (h+k)M + r

Let N1 and N2 with remainders of r1 and r2, respectively. Then

r9(N1+N2) = r9(r1+r2)

Likewise

r9(N1*N2) = r9(r1r2)

Now consider a two digit number n=ab=10a+b, where a and b belong to the set {0, l, 2, …, 9}.

Then

r9(n) = r9(10a+b)= r9(r9(10a)+r9(b))
but r9(b) = b and
r9(10a) = r9(10)*r9(a) = 1*r9(a) = a
and thus
r9(n) = r9(a+b)

But (a+b) is equal to some 10c+d and thus

r9(n) = r9(c+d)

This process must terminate with some digit q. This digit q is D10(n).

If D10(n) belongs to the set {0, 1, 2, …, 8} then
r9(n)=D10(n).
If D10(n)=9 then
r9(n)=r9(9)=0.

The General Case

Let n be an m digit number. Then n=Σ10iai for i=0 to m and hence'

r9(n) = r9(Σai)

But Σai is equal to some number Σ10jbj and so

r9(n) = r9(Σbj)
and so on down to a single digit D10(n)

Thus

r9(n) = r9(D10(n))
and hence
if D10 belongs to {0, 1, 2, …, 8} then
r9 = D10
and if D10=9 then r9 =0

A More General Case

Let B be the base of a notation for integers. Thenfor an integer n

rB-1(n) = rB-1(DB(n))

Thus

if DB(n) belongs to {0, 1, 2, … (B-2)} then rB-1(n) = DB(n)
and rB-1(n) = 0 if DB(n)=B-1

The number 36 in base 10 notation is 44 in base 8 notation. This is denoted as 448 The DigitSum of 44 is 8=108 and hence D8(448)=1. The remainder of 3610=448 upon division by 7 is 1, i.e.; r7(448) = 18.

Extension to Negative Integers

The DigitSum and remainder functions for a negative integer N can be defined as the negative value of the corresponding functions for the absolute value of N; i.e.,

DK(N) = sgn(N)DK(|N|)
rK(N) = sgn(N)rK(|N|)

With these definitions all of the previous relationships also hold for negative integers.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins