San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA |
---|
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 D_{10}(Z). Thus D_{10}(386)=D_{10}(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 r_{9}(Z). The proposition is that
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.
Proof:
If N-hM = kM + r for 0≤r<M then also
Let N_{1} and N_{2} with remainders of r_{1} and r_{2}, respectively. Then
Likewise
Now consider a two digit number n=ab=10a+b, where a and b belong to the set {0, l, 2, …, 9}.
Then
But (a+b) is equal to some 10c+d and thus
This process must terminate with some digit q. This digit q is D_{10}(n).
Let n be an m digit number. Then n=Σ10^{i}a_{i} for i=0 to m and hence'
But Σa_{i} is equal to some number Σ10^{j}b_{j} and so
Thus
Let B be the base of a notation for integers. Thenfor an integer n
Thus
The number 36 in base 10 notation is 44 in base 8 notation. This is denoted as 44_{8} The DigitSum of 44 is 8=10_{8} and hence D_{8}(44_{8})=1. The remainder of 36_{10}=44_{8} upon division by 7 is 1, i.e.; r_{7}(44_{8}) = 1_{8}.
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.,
With these definitions all of the previous relationships also hold for negative integers.
HOME PAGE OF Thayer Watkins |