Wednesday, February 15, 2017

elementary number theory - How to prove the divisibility rule for $3, $ [casting out threes]



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...