|
|
| Author |
Message |
xyzer@hotmail.com
science forum beginner
Joined: 27 Oct 2005
Posts: 5
|
 Posted: Mon Jun 12, 2006 3:42 am Post subject:
Why is this true
|
|
|
Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble by
3. |
|
| Back to top |
|
 |
Stan Liou
science forum addict
Joined: 27 Mar 2005
Posts: 54
|
| Posted: Mon Jun 12, 2006 4:25 am Post subject:
Re: Why is this true
|
|
|
On 11 Jun 2006 20:42:25 -0700, xyzer@hotmail.com wrote:
| Quote: | Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble by
3.
|
Call numbers "congruent modulo 3" iff their difference is
divisible by three. This partitions them into three classes:
{0,3,6,9,12,...}, {1,4,7,9,13,...}, {2,5,8,10,14,...}. Note
that the first set consists of numbers in the form 3k+0, the
second in the form 3k+1, and the third in the form 3k+2--in
other words, accoriding to their remainded after division by
three.
Now, let if N = 3n+p and M = 3m+q, then
N + M = 3(n+m) + (p+q),
i.e., the congruence class (mod 3) of the sum of N and M is the same
as that of the sum of their remainders. Furthermore,
NM = (3n+p)(3m+q) = 3(3nm+nq+mp) + pq,
so that the congruence class of their product is the same as that of
the product of their remainders as well.
In particular, every power of 10 ({1,10,100...}) has a remainder of
1 when divided by 3, so the class of 10^k * A is the same as that of
A. As previously, sums do not change congruence class, so a number
expanded in digits (sums of multiples of powers of 10)
N = Sum[ N_k 10^k ] = Sum[ N_k ] (mod 3).
Hence, the remainder of a number after division by three is the same
as the remainder for the sum of its digits. The trick is repeatable
for large numbers, for which the sum of digits may itself be large.
Since every power of 10 also has remainder 1 when divided by 9, the
exact same trick works for division by 9 as well. Additionally,
every power of 10 is congruent to either 1 or -1 (=10) modulo 11, so
when dividing by 11, an alternating sum of digits with the
ones-place digit positive works. For example, if N = 3846, then
-3+8-4+6 = 7,
so the remainder of 3846/11 is 7.
---
Stan Liou |
|
| Back to top |
|
|
The World Wide Wade
science forum Guru
Joined: 24 Mar 2005
Posts: 790
|
| Posted: Mon Jun 12, 2006 5:19 am Post subject:
Re: Why is this true
|
|
|
In article
<1150083745.901370.281850@h76g2000cwa.googlegroups.com>,
xyzer@hotmail.com wrote:
| Quote: | Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble by
3.
|
Hint: Consider 457 = 4*100 + 5*10 + 7 = 4*(99 + 1) + 5*(9 + 1) +
7 = 4*99 + 4 + 5*9 + 5 + 7 = 4*99 + 5*9 + (4 + 5 + 7). Now 99 and
9 are divisible by 3, hence so is 4*99 + 5*9, therefore ... (and
the rule of 9's falls out the same way). |
|
| Back to top |
|
|
Narcoleptic Insomniac
science forum Guru
Joined: 02 May 2005
Posts: 323
|
| Posted: Mon Jun 12, 2006 5:22 am Post subject:
Re: Why is this true
|
|
|
On Jun 11, 2006 10:42 PM CT, xyzer@hotmail.com wrote:
| Quote: | Can someone explain in plain language why the
following is true?
Any integer is divisible by 3 if the sum of its
digits is divisble by 3.
|
This isn't exactly "plain language" and is essentially
what Stan said in a previous post, but I can't resist.
Any integer n may be written as
n = d_k 10^k + ... + d_2 10^2 + d_1 10^1 + d_0 10^0
...where d_i are the digits of n. For instance, the
integer 4321 can be expressed as
4321 = 4 * 10^3 + 3 * 10^2 + 2 * 10^1 + 1 * 10.
Now if an integer n is divisible by three then we have
n == 0 (mod 3)
...or equivalently, n = 0 + 3k for some integer k. Thus,
if n is divisble by three then
n = d_k 10^k + ... + d_1 10^1 + d_0 10^0 == 0 (mod 3).
It follows that 10^m == 1 (mod 3) for any positive integer
m since 10 == 1 (mod 3). Hence, if n is divisble by three
we have
n = d_k 10^k + ... + d_1 10^1 + d_0 10^0 ==
d_k + ... + d_1 + d_0 == 0 (mod 3),
...which implies the digit sum of n is divisible by three.
We can take this whole process the other way and prove
that if the digit sum of n is divisble by three, then
the integer n is also divisble by three.
The same technique can be used to prove a few other
similar statements; for example, an integer is divisble
by 11 iff the alternating digit sum is divisble by 11.
In this example we would have, by assumption,
n = d_k 10^k + ... + d_1 10^1 + d_0 10^0 == 0 (mod 11).
Now 10^m == (-1)^m (mod 11) for any positive integer m
since 10 == -1 (mod 11). Thus, we obtain
n = d_k 10^k + ... + d_1 10^1 + d_0 10^0 ==
(-1)^k d_k + ... -d_1 + d_0 == 0 (mod 11).
This establishes the "if" part of the statement and the
converse statement is no harder to prove.
A quick example of this would be the integer n = 261206.
Since the digit sum
2 - 6 + 1 - 2 + 0 - 6 = -11 == 0 (mod 11)
we can conclude that 261206 is divisble by 11.
Regards,
Kyle Czarnecki |
|
| Back to top |
|
|
A N Niel
science forum Guru
Joined: 28 Apr 2005
Posts: 475
|
| Posted: Mon Jun 12, 2006 12:21 pm Post subject:
Re: Why is this true
|
|
|
In article <1150083745.901370.281850@h76g2000cwa.googlegroups.com>,
<xyzer@hotmail.com> wrote:
| Quote: | Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble by
3.
|
The powers of 10 all have remainder 1 when divided by 3. |
|
| Back to top |
|
|
Richard Henry
science forum Guru Wannabe
Joined: 29 Apr 2005
Posts: 280
|
| Posted: Mon Jun 12, 2006 3:46 pm Post subject:
Re: Why is this true
|
|
|
<xyzer@hotmail.com> wrote in message
news:1150083745.901370.281850@h76g2000cwa.googlegroups.com...
| Quote: | Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble by
3.
|
Clue: this works in base-10 representation, but not in all others. |
|
| Back to top |
|
|
The Last Danish Pastry
science forum Guru Wannabe
Joined: 29 Apr 2005
Posts: 176
|
| Posted: Mon Jun 12, 2006 5:06 pm Post subject:
Re: Why is this true
|
|
|
<xyzer@hotmail.com> wrote in message
news:1150083745.901370.281850@h76g2000cwa.googlegroups.com...
| Quote: | Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble
by
3.
|
Who is going to post a proof by induction? A little messy, but not
toooo bad.
--
Clive Tooth
www.clivetooth.dk
Stock photos:
http://submit.shutterstock.com/?ref=61771 |
|
| Back to top |
|
|
Dave Seaman
science forum Guru
Joined: 24 Mar 2005
Posts: 527
|
| Posted: Mon Jun 12, 2006 5:20 pm Post subject:
Re: Why is this true
|
|
|
On Mon, 12 Jun 2006 18:06:27 +0100, The Last Danish Pastry wrote:
| Quote: | xyzer@hotmail.com> wrote in message
news:1150083745.901370.281850@h76g2000cwa.googlegroups.com...
Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble
by
3.
Who is going to post a proof by induction? A little messy, but not
toooo bad.
|
Induction on the highest power of 10 doesn't look so bad.
--
Dave Seaman
U.S. Court of Appeals to review three issues
concerning case of Mumia Abu-Jamal.
<http://www.mumia2000.org/> |
|
| Back to top |
|
|
Bill Dubuque
science forum Guru Wannabe
Joined: 04 May 2005
Posts: 236
|
| Posted: Mon Jun 12, 2006 6:29 pm Post subject:
Re: Why is this true
|
|
|
Dave Seaman <dseaman@no.such.host> wrote:
| Quote: | The Last Danish Pastry wrote:
xyzer@hotmail.com
Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble by 3.
Who is going to post a proof by induction?
A little messy, but not toooo bad.
Induction on the highest power of 10 doesn't look so bad.
|
SIMPLER Casting out nines is a special case x,y = 10,1 of
FACTOR THEOREM x-y | P(x)-P(y) in Z[x,y] for poly P in Z[x]
This faq is discussed much further in many of my prior posts:
http://google.com/groups/search?q=group:*math*+dubuque+casting
--Bill Dubuque |
|
| Back to top |
|
|
Shmuel (Seymour J.) Metz
science forum Guru
Joined: 03 May 2005
Posts: 604
|
| Posted: Wed Jun 14, 2006 11:44 am Post subject:
Re: Why is this true
|
|
|
In <1150083745.901370.281850@h76g2000cwa.googlegroups.com>, on
06/11/2006
at 08:42 PM, xyzer@hotmail.com said:
| Quote: | Can someone explain in plain language why the following is true?
|
Because you're using base 10.
| Quote: | Any integer is divisible by 3 if the sum of its digits is divisble
by 3.
|
Well, start with 1-digit numbers: obvious. For two-digit numbers, n*10
+ (3-n) = 9*n + 3, which is divisible by 3. Apply induction.
--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>
Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spamtrap@library.lspace.org |
|
| Back to top |
|
|
The Ghost In The Machine
science forum Guru
Joined: 25 Mar 2005
Posts: 1551
|
| Posted: Sun Jun 18, 2006 3:00 am Post subject:
Re: Why is this true
|
|
|
On Mon, 12 Jun 2006 18:06:27 +0100, The Last Danish Pastry wrote:
| Quote: | xyzer@hotmail.com> wrote in message
news:1150083745.901370.281850@h76g2000cwa.googlegroups.com...
Can someone explain in plain language why the following is true?
Any integer is divisible by 3 if the sum of its digits is divisble by
3.
Who is going to post a proof by induction? A little messy, but not toooo
bad.
|
Herewith an ad hoc proof, that turns out to be very clean. At least, I
think it's clean.  (I should know. I have a dirty mind. )
I'll induct on P=floor(log10(N)), a form
of strong induction, and I want to prove the statement:
Theorem: N % 3 == (S_N % 3)
for all integers N >= 0, where S_N = sum(i=0,P) digit(N,P).
('%' here is the mod operator, a common usage in C/C++ - type languages.)
Case P=floor(log10(N)) < 1. This means N is a single digit. For all
digits the theorem is trivially true. (Note that floor(log10(0)) = -oo,
which is easily handled as a special case.)
Case P=floor(log10(N)) >= 1. Let n = floor(N/10) and d = N-n*10.
Colloquially, d is the trailing digit. This also means N = n*10+d and
p <= P-1 < P.
I assume n % 3 = S_n % 3, for the induction hypothesis, and then grind
it out:
(n * 10) % 3 = n % 3 since 10 % 3 = 1
N % 3 = (n * 10 + d) % 3 = (n + d) % 3 = (S_n + d) % 3 = S_N % 3
since S_N = S_n + d.
Corollary: if a number, represented in base 10, has digits that sum to a
multiple of 3, then the number is a multiple of 3, and vice versa.
This proof could be cleaned up a bit by rigorously defining digit(N,P) =
floor(N/10^P) - 10*floor(N/10^(P+1)) and by doing more grinding, but
presumably you get the general idea.
A similar proof for divisibility by 9 is almost identical.
--
#191, ewill3@earthlink.net
It's still legal to go .sigless. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 2:58 am | All times are GMT
|
|
MPAA | Car Loan | Debt Consolidation | Business Credit Card | Bankruptcy
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
