# Divisibility rule

#### idontknow

If 3 divides $$\displaystyle n$$ for $$\displaystyle n \in N$$
Show that the sum of digits of $$\displaystyle n$$ must be divisible by 3

Last edited:

#### Maschke

If 3 divides $$\displaystyle n$$ for $$\displaystyle n \in N$$
Show that the sum of digits of $$\displaystyle n$$ must be divisible by 3
This definitely calls out for a round of, "Show us what you've done so far."

1 person

#### skipjack

Forum Staff
Consider the numerical difference between an integer and the sum of its digits.

#### idontknow

First express $$\displaystyle n$$ as powers of $$\displaystyle 10$$ , example: $$\displaystyle 273=10^2 \cdot 2 +10^1 \cdot 7 +10^0 \cdot 3$$
Let $$\displaystyle x_1,x_2,...,x_k$$ be the digits of $$\displaystyle n$$
$$\displaystyle n=10^{k-1}x_k + 10^{k-2}x_{k-1} + ...+10x_2+x_1=(10^{k-1}-1)x_k +x_k+(10^{k-2}-1)x_{k-1} + x_{k-1} +...+9x_2 + x_2 +x_1$$
$$\displaystyle 10^p -1$$ is a multiple of $$\displaystyle 9$$, so write $$\displaystyle 10^p -1=9a$$
$$\displaystyle n=9a_k x_k +x_k +9a_{k-1}x_{k-1}+x_{k-1} +...+9x_2 +x_2 +x_1$$
$$\displaystyle n=9(a_k x_k +a_{k-1}x_{k-1}+...+x_2)+(x_1+x_2+...+x_k)$$
$$\displaystyle 3|9(a_k x_k +a_{k-1}x_{k-1}+...+x_2)$$ but also $$\displaystyle 3$$ must divide the other part of the sum (if 3|p and 3|q , then 3|(p+q))
so $$\displaystyle 3|(x_1+x_2+...+x_k)$$

#### JeffM1

It is hard to comment on proofs because we do not know what axioms and theorems you have available and what conventions of presentation you should follow.

But the basic thought behind your proof looks sound to me.

#### JeffM1

I keep thinking that this argument would be much clearer with better notation.

Given

$m,\ n \in \mathbb Z.$

$m > 0.$

$10^{(m- 1)} < n < 10^ m.$

$3\ |\ n \implies \exists \ a \in \mathbb Z \text { such that } 3a = n.$

$k \in \mathbb Z \text { and } 1 \le k \le m.$

$\text {Define } d_k \text { such that } d_k \in \mathbb Z,\ 0 \le d_k \le 9, \text { and } \displaystyle \left ( \sum_{k=1}^m d_k * 10^{(k-1)} \right ) = n.$

$\text {Let } p = \displaystyle \sum_{k=1}^m d_k.$

$\text {Prove } 3 \ | \ p.$

$\text {Let } x_k = d_k * 10^{(k-1)} - d_k \implies x_k \in \mathbb Z \ \because d_k \in \mathbb Z.$

$\text {Also } x_k + d_k = d_k * 10^{(k-1)}.$

$\text { Let } q = \displaystyle \sum_{k=1}^m x_k \implies q \in \mathbb Z \ \because x_k \in \mathbb Z.$

$n = \displaystyle \left ( \sum_{k=1}^m d_k * 10^{(k-1)} \right ) = \left ( \sum_{k= 1}^ m d_k + x_k \right ) = \left ( \sum_{k=1}^m d_k \right ) + \left ( \sum_{k=1}^m x_k \right ) = p + q \implies$

$p = n - q = 3a - q.$

$x_k = d_k * 10^{(k-1)} - d_k = d_k(10^{(k-1)} - 1).$

We now apply the following theorem.

$\alpha \in \mathbb Z \text { such that } \alpha \ge 1 \implies \exists \ \beta \in \mathbb Z \text { such that } 9\beta = 10^{(\alpha -1)} - 1.$

$\therefore \exists \ y_k \in \mathbb Z \text { such that } 9y_k = 10^{(k-1)} - 1.$

$\therefore x_k = 9d_ky_k.$

$\therefore q = \displaystyle \left ( \sum_{k=1}^m 9d_ky_k \right ) = 9 * \left ( \sum_{k=1}^m d_ky_k \right ).$

$\text {Let } r = \displaystyle \left ( \sum_{k= 1}^m d_ky_k \right ) \in \mathbb Z \ \because \ d_k, \ y_k \in \mathbb Z.$

$\therefore q = 9r \implies p = 3a - 9r = 3(a - 3r) \implies$

$3 \ | \ p \ \because \ a,\ r \in \mathbb Z.$