4
$\begingroup$

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.

  • 0
    ahh i see now. makes perfect sense. thanks2011-02-25

3 Answers 3

3

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.

  • 0
    This concept is easily extended to an integer $x$ of any number of digits divided by any integer...2011-12-02
1

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.

1

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.