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
    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?2011-02-25
  • 0
    Yes i do that if x = y(mod3) then x and y divide 3?2011-02-25
  • 6
    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$.2011-02-25
  • 0
    @Andres, thanks that helped a lot2011-02-25
  • 0
    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$.2011-02-25
  • 0
    @yunone, how could you prove that 3|x by using x=y(mod 3) if 3|(x-y) only2011-02-25
  • 0
    @Krysten, you can't, saying two integers are congruent modulo some modulus means their difference is divisible by the modulus. It doesn't say anything about the numbers themselves being divisible by the modulus. However, if you have that $3|y$ and $x\equiv y\pmod{3}$, then you could show that $3|x$. This would follows since $3|y\implies y\equiv 0\pmod{3}$, and thus $$x\equiv y\equiv 0\implies x\equiv 0\pmod{3}$$ which is to say $3|x-0$. If you don't know $3|y$, then there is no reason to assume $3|x$, and this is generally not the case.2011-02-25
  • 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.