Thread: Prove n is divisible by 3

1. Prove n is divisible by 3

Prove that if n is a positive integer such that the sum of the digits of n in decimal representation is divisible by 3 then n is divisible by 3

2. Originally Posted by mandy123
Prove that if n is a positive integer such that the sum of the digits of n in decimal representation is divisible by 3 then n is divisible by 3
This one is sort of the archetype for the rest of them.

Note that
$10^n \equiv 1 \text{ mod 3}$
for all positive n.

So putting a number x into its decimal representation in base 10:
$x = \sum_n x_n \cdot 10^n$

We see that
$x \equiv \sum_n x_n \cdot 1 \text{ mod 3}$

So if $\sum_n x_n = 0 \text{ mod 3}$ (ie. the sum of the digits of x is divisible by 3), then the number x is divisible by 3.

-Dan