Show that pos int divisible by 3 iff sum of digits divisible by 3

Printable View

November 18th 2009, 07:48 PM
oldguynewstudent

Show that pos int divisible by 3 iff sum of digits divisible by 3

Show that a positive integer is divisible by 3 iff the sum of its digits is divisible by 3.

This is from Rosen but I can't follow the proof in the solutions manual (again). Section 3.6 problem 29.

Please explain the detail so I'll understand the whole process.
November 18th 2009, 07:51 PM
Drexel28

Quote:

Originally Posted by oldguynewstudent

Show that a positive integer is divisible by 3 iff the sum of its digits is divisible by 3.

This is from Rosen but I can't follow the proof in the solutions manual (again). Section 3.6 problem 29.

Please explain the detail so I'll understand the whole process.

What part of the proof eludes you?
November 18th 2009, 08:17 PM
Sampras

Suppose $n = a_0 + a_{1}10+ a_{2}10^{2} + \cdots + a_{n} 10^n$ .

Consider $s = a_0 + \cdots a_n$ and look at n-s.
November 18th 2009, 08:42 PM
oldguynewstudent

Quote:

Originally Posted by Drexel28

What part of the proof eludes you?

Since 10 $\equiv$ 1 (mod 3) we have a $\equiv$ $a_n$ $_-$ $_1$ + ... + $a_1$ + $a_0$ (mod 3). Therefore a $\equiv$ 0 (mod 3) iff the sum of the digits is congruent to 0 (mod 3).

I don't follow the part we have a $\equiv$ sum (mod 3).

Is this because 10 to any power divided by 3 has a 1 remainder? Then a divided by 3 leaves the sum of the digits?

I just now saw this relationship. The solutions manual assumes this is intuitively obvious, I guess.
November 19th 2009, 04:20 PM
gmatt

Let $x = \sum _{i=0} ^n a_i 10^i$ .

Suppose $3 | x$ then $0 \equiv x \equiv \sum _{i=0} ^n a_i {10} ^n \equiv \sum _{i=0} ^n a_i {1} ^n \bmod{3}$
February 20th 2013, 09:32 AM
pspss

Re: Show that pos int divisible by 3 iff sum of digits divisible by 3

Let a number be abc
= 100a + 10b + c
= 99a + 9b + a + b + c
99a and 9 b are divisible by 3
so (a + b + c) must be divisible by 3.
so (a + b + c) is sum of digits must be divisible by 3.
---