Proof: Integer Divisibility by 3 via Polynomials

AI Thread Summary
The discussion presents a proof that an integer is divisible by 3 if and only if the sum of its digits is divisible by 3. It establishes that for a polynomial function P(x), the evaluation at 10 modulo 3 is equivalent to the evaluation at 1 modulo 3, due to the property that 10 is congruent to 1 modulo 3. This leads to the conclusion that the integer N, represented by its digits, is congruent to the sum of its digits modulo 3. The proof is supported by the concept of ring homomorphism, which maintains the operations of addition and multiplication under modulo conditions. Thus, the divisibility rule for 3 is confirmed through polynomial evaluation and modular arithmetic principles.
Math100
Messages
813
Reaction score
229
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 ##.
 
  • Like
Likes fresh_42, malawi_glenn and Delta2
Physics news on Phys.org
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)
 
Math100 said:
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.
 
Last edited:
  • Like
Likes Math100 and Delta2
I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
Essentially I just have this problem that I'm stuck on, on a sheet about complex numbers: Show that, for ##|r|<1,## $$1+r\cos(x)+r^2\cos(2x)+r^3\cos(3x)...=\frac{1-r\cos(x)}{1-2r\cos(x)+r^2}$$ My first thought was to express it as a geometric series, where the real part of the sum of the series would be the series you see above: $$1+re^{ix}+r^2e^{2ix}+r^3e^{3ix}...$$ The sum of this series is just: $$\frac{(re^{ix})^n-1}{re^{ix} - 1}$$ I'm having some trouble trying to figure out what to...

Similar threads

Back
Top