Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that for every positive integer $x$ of exactly four digits, if the sum of digits is divisible by $3$, then $x$ itself is divisible by 3 (i.e., consider $x = 6132$, the sum of digits of $x$ is $6+1+3+2 = 12$, which is divisible by 3, so $x$ is also divisible by $3$.)

How could I approach this proof? I'm not sure where I would even begin.

share|improve this question
    
This is true for a number with any number of digits, and is a very well-known fact. As to where to begin to prove it yourself, do you know modular arithmetic? –  Matt E Feb 25 '11 at 2:32
    
Yes i do that if x = y(mod3) then x and y divide 3? –  Krysten Feb 25 '11 at 2:32
5  
Here is a big hint: $6132=6000+100+30+2=6\cdot1000+1\cdot100+3\cdot10+2$. Why is this a hint? Well, what happens when you subtract $6+1+3+2$ from it? You get $6\cdot999+1\cdot99+3\cdot9+0$. –  Andres Caicedo Feb 25 '11 at 2:33
    
@Andres, thanks that helped a lot –  Krysten Feb 25 '11 at 2:46
    
By the way Krysten, if $x=y\pmod{3}$, it means $3$ divides $x-y$, NOT that $x$ and $y$ divide $3$. For example, $5=2\pmod{3}$ since $3$ divides $5-2$, but neither $2$ nor $5$ divide $3$. –  yunone Feb 25 '11 at 3:01

3 Answers 3

up vote 3 down vote accepted

Suppose you have a number whose decimal digits are represented $a$, $b$, $c$, and $d$, so $x=abcd$.

In base $10$, this means $$ x=abcd=a\cdot 10^3+b\cdot 10^2+c\cdot 10^1+d\cdot 10^0. $$ Try looking at $x$ modulo $3$, and remember that $10\equiv 1\pmod{3}$.

This concept is easily extended to an integer $x$ of any number of digits.

share|improve this answer
    
This concept is easily extended to an integer $x$ of any number of digits divided by any integer... –  Quixotic Dec 2 '11 at 22:17

Actually, this is true for an integral number with any digits. The proof is quite easy. Let's denote the integral number by $\overline{a_n a_{n-1} \ldots a_1}$. If the sum of its digits $\sum_{i=1}^n{a_i}$ is divisible by 3, then $\sum_{i=1}^n{(1+\overline{9...9}_{i-1})*a_i}$ is too. Here $\overline{9...9}_{i-1}$ denotes the integer with $i-1$ 9's. But this second sum is just the original number $\overline{a_n a_{n-1} \ldots a_1}$ expanded.

share|improve this answer

It's due to radix representation being polynomial form in the radix, e.g. $\rm\ n = 4321 = p(10)\ $ for $\rm\ p(x) = 4\: x^3 + 3\: x^2 + 2\: x + 1\:.\:$ Thus mod $\rm\:3\::\ 10\equiv 1\ \Rightarrow\ p(10)\equiv p(1)\ =\ \sigma(n) :=$ sum of digits. Aternatively one may simply put $\rm\ x = 10\ $ in the $\:$ Factor Theorem $\rm\ \ x-1\ |\ p(x)-p(1)\:,\: $ hence $\rm\ 3\ |\ 9\ |\ p(10)-p(1) = n - \sigma(n)\:.\:$ This is a special case of casting out nines.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.