The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large numbers are multiples of three, because we can recursively apply this rule:
$$1212582439 \rightarrow 37 \rightarrow 10\rightarrow 1 \implies 3\not\mid 1212582439$$
$$124524 \rightarrow 18 \rightarrow 9 \implies 3\mid 124524$$
This works for as many numbers as I've tried. However, I'm not sure how this may be proven. Thus, my question is:
Given a positive integer $n$ and that $3\mid\text{(the sum of the digits of $n$)}$, how may we prove that $3\mid n$?
Answer
HINT: Suppose that you have a four-digit number $n$ that is written $abcd$. Then
$$\begin{align*}
n&=10^3a+10^2b+10c+d\\
&=(999+1)a+(99+1)b+(9+1)c+d\\
&=(999a+99b+9c)+(a+b+c+d)\\
&=3(333a+33b+3c)+(a+b+c+d)\;,
\end{align*}$$
so when you divide $n$ by $3$, you’ll get
$$333a+33b+3c+\frac{a+b+c+d}3\;.$$
The remainder is clearly going to come from the division $\frac{a+b+c+d}3$, since $333a+33b+3c$ is an integer.
Now generalize: make a similar argument for any number of digits, not just four. (If you know about congruences and modular arithmetic, you can do it very compactly.)
No comments:
Post a Comment