Intereting Posts

Congruence question with divisibility
Math Major: How to read textbooks in better style or method ? And how to select best books?
counting the patterns
Differential equations that are also functional
$1/r^2\int_{\mathbb{S}_r}u-u(x)$ converging to $\Delta u(x)$?a
Given that a,b,c are distinct positive real numbers, prove that (a + b +c)( 1/a + 1/b + 1/c)>9
The distribution of barycentric coordinates
Making trigonometric substitutions rigorous
A dilogarithm identity?
Which undergraduate math book cover topics about polynomials?
How to find $\lim_{n \to \infty} \int_0^1 \cdots \int_0^1 \sqrt{x_1+\sqrt{x_2+\sqrt{\dots+\sqrt{x_n}}}}dx_1 dx_2\dots dx_n$
Fun math for young, bored kids?
Showing $\log(2)$ and $\log(5)$
Has the opposite category exactly the same morphisms as the original?
The Matrix Equation $X^{2}=C$

Here is the proof of the converse:

Iff a number $n$ is divisible by $3$, then the sum of its digits is also divisible by $3$.

Proof:

- Does the set of $m \in Max(ord_n(k))$ for every $n$ without primitive roots contain a pair of primes $p_1+p_2=n$?
- Integer solutions of $xy+9(x+y)=2006$
- Is $n=1073$ a strong pseudoprime to bases $a=260, 813?$
- Why is $a\equiv b \pmod n$ equivalent to the congruences $a\equiv b,b+n,b+2n,\dots,b+(c-1)n\pmod {cn}$?
- How to prove $n^5 - n$ is divisible by 30 without reduction
- Solve for $A,B$: $\mathrm{LCM}(A,B)=168$, $\mathrm{HCF(A,B)}=12$

We know $n \mod 3 = 0$. By the basis representation theorem, $n$ can be re-written as $n_k10^k + n_{k-1}10^{k-1} + \cdots + 10n_1 + n_0 \equiv 0 \mod 3$. By the modular arithmetic addition rule, we can take $n_k10^k \mod 3 + n_{k-1}10^{k-1} \mod 3 + \cdots + 10n_1 \mod 3 + n_0 \mod 3$. But then we just get $n_k + n_{k-1} + \cdots + n_1 + n_0$, since $10 \mod 3 \equiv 1$.

Now suppose that the sum of the digits was divisible by 3. How can I prove that the representation in base $10$ is divisible by $3$?

- Prove that $n$ is a sum of two squares?
- Chicken Problem from Terry Tao's blog (system of Diophantine equations)
- Intuition of why $\gcd(a,b) = \gcd(b, a \pmod b)$?
- Elementary proof that $-1$ is a square in $\mathbb{F}_p$ for $p = 1 \mod{4}$
- Primality test for Proth numbers using Fibonacci numbers
- Is it right that the fundamental recurrence of an arbitrary continued fraction cannot be proved without induction?
- Show that $17 \mid 15! -1$
- Probability that two random numbers are coprime
- What is complete induction, by example? $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$
- Generalizing Ramanujan's sum of cubes identity?

The key point which you seem to have noted is that $10\equiv 1\pmod{3}$. This means that a number is congruent to the sum of its digits mod 3 because $10^k\equiv 1\pmod{3}$, which you also seem to have noted. Thus $n$ is divisible by $3$ (congruent to $0$ mod 3) if and only if the sum of its digits is. The same is true for other remainders modulo 3; a number has a remainder of $1$ when divided by $3$ if and only if the sum of its digits does, etc.

Your observation that $10^k\equiv 1\pmod{3}$ is the reason why it has been commented that you have already proved the result.

I hope this will suffice:

$$

n

= (d_{m-1}\cdots d_0)_{10}

= \sum_{k=0}^{m-1} d_k 10^k

= \sum_{k=0}^{m-1} d_k (10^k – 1) + d_k

= \sum_{k=0}^{m-1} d_k (10^k – 1) + S(n)

$$

with $S(n)$ being the digit sum in base $10$ and

$$

10^k – 1 = 9 \frac{10^{k} – 1}{10-1} = 9 \sum_{i=0}^{k-1} 10^i

= \sum_{i=0}^{k-1} 9 \, 10^i

= (\underbrace{9\cdots 9}_{k \times})_{10}

$$

is divisible by $3$, it depends on the divisibility of $S(n)$.

The same statement should hold for division by $9$.

- Trouble to prove L'Hopital theorem to the case $\infty/\infty$
- If $\operatorname{ran} F \subseteq \operatorname{dom} G$, then $\operatorname{dom}(G \circ F) = \operatorname{dom} F$.
- First Pontryagin class on real Grassmannian manifold?
- Integer coordinate set of points that is a member of sphere surface
- To show that Fermat number $F_{5}$ is divisible by $641$.
- If $P(x)=2013x^{2012}-2012x^{2011}-16x+8$,then $P(x)=0$ for $x\in\left$ has
- Proof Strategy for a Dynamical System of Points on the Plane
- How to construct a line with only a short ruler
- When do regularization methods for divergent series disagree?
- What is the usefulness of matrices?
- Limit problem: $\sqrt{x+1} – \sqrt{x}$ as $x$ approaches infinity
- Residue at essential singularity
- Indefinite integral of $\log(\sin(x))$
- induction proof of fibonacci number
- Intermediate step in deducing Jacobi's triple product identity.