Re: Proof that a Number is a Multiple of 3 If the Sum Of Its Digits in Decimal Notation Is a Multiple Of 3
- From: Bill Dubuque <wgd@xxxxxxxxxxxxxxxxxxxx>
- Date: 31 Dec 2008 18:39:22 -0500
Ray Vickson <RGVickson@xxxxxxx> wrote:
On Dec 26, 9:09 am, Michael Ejercito <mejercit@xxxxxxxxxxx> wrote:
On Dec 25, 3:54 pm, Ray Vickson <RGVickson@xxxxxxx> wrote:
On Dec 24, 3:16 pm, Michael Ejercito<mejercit@xxxxxxxxxxx> wrote:
What is the proof that if a the sum of the digits of a number's
decimal representation is a multiple of 3, then the number is a
multiple of 3?
Take a two-digit example, where the number is of the form x2x2 = x2*10
+ x1 = (x1+x1) + 9*x2. You are assuming that x1+x2 is divisible by 3,
and certainly the term 9*x2 is divisible by 3, so both terms are
divisible by three. That means that the entire number is divisible by
three. The same argument holds for a 3-digit number or a 4-digit
number or .... .
I do detect a pattern than subtracting 1 from a power of 10 would
yield a multiple of 3.
But what is the proof that 10^n-1 is a multiple of 3 for all
nonnegative integers n?
It is true that 10^n is divisible by 9 for small n = 1 or 2. Assuming
it is true for n = m, look at 10^(m+1) - 1; this equals 10^(m+1) -
10^m + 10^m - 1 = 9*10^m + 10^m - 1, so the result is true also for n=m+1.
My 3 posts in the thread [0] contain in-depth discussions of various
elementary ways to prove such results. In particular they highlight
the elegant approach via the FACTOR THEOREM 10-1 | P(10)-P(1).
I've excerpted one of these posts below, but one should see the
entire thread for appropriate context and for further discussion.
[1] Symbolic Sum Manipulation
a + 10 b + 10^2 c + 10^3 d + ...
- a + b + c + d + ...
--------------------------
= 9 b + 99 c + 999 d + ... which is divisible by 9.
[2] Induction via Integer Division Algorithm
| If n < 10 then n - s(n) = 0 = 9*0. [with s(n) := digit sum of n]
| If n >= 10 then n = 10a + b where 0 <= a < n and 0 <= b < 10.
| Then s(n) = s(a) + b, so n - s(n) = 10a - s(a) = 9a + a - s(a)
| and so is the sum of two multiples of 9.
[3] Instance of Polynomial Root-Factor Theorem
N = P(10) = a + 10 b + 10^2 c + ... is a polynomial P in the radix 10.
Thus 10-1 | P(10)-P(1) since x-r | P(x)-P(r) for any polynomial P.
The problem with proof [1] is that, when fully formalized, one must
resort to the clumsy manipulation of symbolic sums and, further,
one needs to prove that 9 | 10^n-1, say by induction. Passing to
polynomial notation avoids the first problem: the clumsy sum
a + 10 b + 10^2 c + 10^3 d + ... is replaced by the polynomial
P(10), and the digit-sum a + b + c + d + ... is replaced by P(1),
which is a very efficient representation, omitting irrelevant
details such as specific digits, the sum index variable, and the
(symbolic) upper limit of the sum = deg P. As for the second point,
one could avoid using induction by deriving 9 | 10^n-1 as an
instance of a cyclotomic factorization x-1 | x^n-1, but this
is essentially equivalent to passing to polynomials as I do in [3],
In fact, by linearity, the Root-Factor Theorem x-r | P(x)-P(r)
is equivalent to its instance on the basis P(x) = x^n, i.e. to
the cyclotomic case x-r | x^n-r^n which, of course, has a simple
inductive proof
n+1 n+1 n n
x - r n x - r
---------- = x + r -------
x - r x - r
an alternative to the simple proof of the Root-Factor Theorem
from my first post, based on the Polynomial Division Algorithm.
The problem with proof [2] is that, like [1], it too requires
an explicit induction argument and, moreover, the structure of
the induction is not immediately intuitive (i.e. it is pulled
out of a hat). It can be made intuitive: if you "unwind" the
induction it is essentially an iteration of the rewrite rule
9 | r + 10 s
<=> 9 | r + s [R]
applied to radix 10 notation of N "unwound" as a Horner polynomial
9 | a + 10 (b + 10 (c + 10 (d + ...))) = N
<=> 9 | a + (b + (c + (d + ...))) = s(N) = digit sum of N
i.e. 9 divides N iff 9 divides N's digit sum s(N). Above I have applied
the rewrite rule [R] three times to replace each 10 with 1; explicitly
9 | a + 10 (b + 10 (c + 10 (d + ...)))
apply [R] with r=a
<=> 9 | a + b + 10 (c + 10 (d + ...))
apply [R] with r=a+b
<=> 9 | a + b + c + 10 (d + ...)
apply [R] with r=a+b+c
<=> 9 | a + b + c + d + ... ...
However, just as in [1], if you're going to introduce a polynomial
to make the proof clear, then you may as well proceed as I do in [3]
since it avoids any explicit use of induction and, instead of any
ad-hoc methods, uses only a well-known elementary result -- the
Polynomial Root-Factor Theorem x-r | P(x)-P(r), a fundamental
result that has widespread applications, and should have already
been committed to memory from high-school algebra.
The power of the lowly polynomial should not be underestimated!
| Why is congruence arithmetic considered "advanced" when (to risk
| sounding like Herman Rubin) it can be taught to primary school
| children? I suspect that if someone knows enough to understand the
| statement of the result, they know enough to understand an
| appropriately phrased version of the congruence proof. You never
| even need to use the word "congruent", you can just say "divides".
I certainly agree that congruences (modular arithmetic) could be
taught at a very early age. But I interpreted the problem as
"how to supply an elegant one-line proof to someone who was not
already familiar with congruences?". To develop the machinery
of congruences would require much more work than then one-line
proof I present in [3] above. However, I do not pretend in any
way that [3] is the "correct" way to view casting out 9s. Surely
it is best viewed via modular arithmetic, i.e. as an instance of
problem reduction methods employing structure preserving maps
(homomorphisms) to "simpler" structures, of which there are many
examples (Chinese Remainder Theorem, Hensel's Lemma, localization,
various other local-global techniques, etc).
--Bill Dubuque
[0] sci.math, 8/6/97, elegant proofs of casting 9s [was: Ugly Mathematics?]
http://google.com/groups?threadm=y8zoh73mzp8.fsf%40nestle.ai.mit.edu
.
- Prev by Date: Re: nothing anyone would want to read (or: crank boxing (or: the death of the dance))
- Next by Date: Re: nothing anyone would want to read (or: crank boxing (or: the death of the dance))
- Previous by thread: Re: nothing anyone would want to read (or: crank boxing (or: the death of the dance))
- Next by thread: Re: Well ordering of reals
- Index(es):
Relevant Pages
|
Loading
