Question

Show that a positive integer is divisible by 3 if and only if the sum of its decimal digits
is divisible by 3

Answer 1

Call the number \(x\), where the digits of \(x\) are \(a_{n}...a_{-k}\) (n is the furthest place to the left of the decimal point, -k is the furthest place to the right of it).
Then we can express \(x\) as sums of powers of 10:
\(x=10^n \times a_{n} + ... + 10^2 \times a_{2} + 10^1 \times a_{1} + 10^0 \times a_{0} + 10^-1 \times a_{-1} + ... + 10^{-k} \times a_{-k} \)
Where \(0\le a_{i}\le 9\) (these are the digits).

If \(x\) is divisible by \(3\) then \(x=0mod3\)
Then \(10^n a_{n}mod3+...+10^2 a_{2} mod3+...\) etc \(=0mod3\).
Now, any multiple of 10 is equal to 1mod3 (e.g: 1000 =999+1).
So we now have:
\[a_{n}mod3+...+a_{2}mod3+a_{1}mod3+a_{0}mod3+a_{-1}mod3+...+a_{-k}mod3=0mod3\]
So:
\[(a_{n}+...+a_{2}+a_{1}+a_{0}+a_{-1}+...+a_{-k}=0mod3\]
In other words, the sum of the digits \(a_{i}\) is divisible by 3.

Does this make sense? Please say if I can explain any more. :)

Answer 2

Thank you for your response, it will take me a while to find out what's going on here.

Answer 3

Let me know if I can explain something, I'm around for the next 10 minutes :) Are you familiar with modular arithmetic?

Answer 4

No unfortunately, i was hoping this could be done by induction

Answer 5

Hmm I'm not sure, it's definitely easier to do it this way I think. (Any problems involving divisors are usually best solved using modular arithmetic). Maybe you could assume that if a number which has \(n\) digits is divisible by 3 (where the sum of its digits are divisible by 3) then use the inductive step to show that a number with \(n+1\) digits is?

Answer 6

That is, show that the (n+1) digit number is divisible by 3 iff the the new digit is a multiple of 3:
Base: n=1: Take a 1 digit number x. Then it is divisible by 3 if and only if its digit is divisible by 3.

Inductive step: assume that the digits of the number \(x\) with \(n\) digits is divisible by 3 if and only if the sum of its digits are divisible by 3.

Take an (n+1) digit number \(a_{n+1} 10^{n+1} + x \). Then this is divisible by 3 if and only if \(a_{n+1} \) is divisible by 3. So the sum of all the digits of \(x\) and of \(a_{n+1}\) will be divisible by 3.

Answer 7

I don't understand where the 10 comes from

Answer 8

Take the number 2459 as an example. You can write this as:
\[(10^3\times 2) + (10^2 \times 4) + (10^1 \times 5) + (10^0 \times 9) \]
The powers of 10 just show the place value of each digit.