Proof: Integer Divisibility by 3 via Polynomials

[Math100]

Homework Statement

Establish the following divisibility criteria:
An integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$.

Relevant Equations

None.

Proof:

Let $P(x)= \Sigma^{m}_{k=0} a_{k} x^{k}$ be a polynomial function.
Then $N=a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0}$ for $0\leq a_{k}\leq 9$.
Since $10\equiv 1\pmod {3}$, it follows that $P(10)\equiv P(1)\pmod {3}$.
Note that $N\equiv (a_{m}+a_{m-1}+\dotsb +a_{1}+a_{0})\pmod {3}$.
Thus $3\mid N\Leftrightarrow N\equiv 0\pmod {3}\Leftrightarrow P(10)\equiv 0\pmod {3}\Leftrightarrow P(1)\equiv 0\pmod {3}$.
This means $3\mid P(1)\Leftrightarrow 3\mid (a_{m}+a_{m-1}+\dotsb +a_{2}+a_{1}+a_{0})$.
Therefore, an integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$.

 

[anuttarasammyak]

Though It is not different from your answer,
$$10^n \equiv 1(\mod 3)$$
Proof
For n=0 $10^0=1\equiv 1(\mod 3)$
Say n satisfy it $10^{n+1} \equiv 10 \equiv 1(\mod 3)$
prooved
Say abcd...z a decimal positive integer number
$$abcd...z \equiv a+b+c+d+...+z(\mod 3)$$

 

[fresh_42]

Homework Statement:: Establish the following divisibility criteria:
An integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$.
Relevant Equations:: None.

Proof:

Let $P(x)= \Sigma^{m}_{k=0} a_{k} x^{k}$ be a polynomial function.
Then $N=a_{m}10^{m}+a_{m-1}10^{m-1}+\dotsb +a_{1}10+a_{0}$ for $0\leq a_{k}\leq 9$.
Since $10\equiv 1\pmod {3}$, it follows that $P(10)\equiv P(1)\pmod {3}$.
Note that $N\equiv (a_{m}+a_{m-1}+\dotsb +a_{1}+a_{0})\pmod {3}$.
Thus $3\mid N\Leftrightarrow N\equiv 0\pmod {3}\Leftrightarrow P(10)\equiv 0\pmod {3}\Leftrightarrow P(1)\equiv 0\pmod {3}$.
This means $3\mid P(1)\Leftrightarrow 3\mid (a_{m}+a_{m-1}+\dotsb +a_{2}+a_{1}+a_{0})$.
Therefore, an integer is divisible by $3$ if and only if the sum of its digits is divisible by $3$.

Correct, yes.

You have used $10\equiv 1\pmod 3 \Longrightarrow P(10)\equiv P(1) \pmod 3.$

The reason why this is true is that modulo is a ring homomorphism. A ring is a structure with addition, multiplication (but without division), and the distributive law, e.g. $\mathbb{Z}$. A ring homomorphism means it respects the two operations. This means
\begin{align*}
a+b \pmod n &\equiv a\pmod n +b \pmod n \\
a\cdot b \pmod n &\equiv a\pmod n \cdot b \pmod n
\end{align*}
Therefore $P(x) \pmod n \equiv P(x\pmod n)$ by consecutive applications of these two laws.