Divisibility rule

Dec 2015
1,084
169
Earth
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:
Aug 2012
2,496
781
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."
 
  • Like
Reactions: 1 person

skipjack

Forum Staff
Dec 2006
21,481
2,470
Consider the numerical difference between an integer and the sum of its digits.
 
Dec 2015
1,084
169
Earth
Im not sure about this way , but the result works
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)\)
 
May 2016
1,310
551
USA
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.
 
May 2016
1,310
551
USA
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.$