Proof: Integer Divisibility by 3 via Polynomials

And ##10 \pmod 3 = 1##, so the proof follows.In summary, the proof shows that an integer is divisible by 3 if and only if the sum of its digits is divisible by 3, by using the fact that modulo is a ring homomorphism and the property that ##10\equiv 1\pmod 3##.
  • #1
Math100
802
222
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
  • #2
Though It is not different from your answer,
[tex]10^n \equiv 1(\mod 3)[/tex]
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
[tex]abcd...z \equiv a+b+c+d+...+z(\mod 3)[/tex]
 
  • Like
Likes Delta2
  • #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

FAQ: Proof: Integer Divisibility by 3 via Polynomials

How does the proof for integer divisibility by 3 via polynomials work?

The proof for integer divisibility by 3 via polynomials relies on the fact that any integer can be expressed as a polynomial with coefficients in the set {0, 1, 2}. By evaluating this polynomial at x=1, it is possible to determine if the integer is divisible by 3.

Can this proof be applied to other numbers besides 3?

Yes, this proof can be extended to show divisibility by other numbers as well. For example, to prove divisibility by 4, the polynomial would be evaluated at x=2. However, the coefficients of the polynomial would need to be chosen from the set {0, 1, 2, 3} in this case.

What is the significance of using polynomials in this proof?

Using polynomials allows for a systematic and generalizable approach to proving divisibility by a certain number. It also makes use of the fundamental theorem of algebra, which states that any non-constant polynomial with complex coefficients has at least one root.

Are there any limitations to this proof?

One limitation of this proof is that it only works for integers. It cannot be applied to numbers with decimal or fractional parts. Additionally, the coefficients of the polynomial must be chosen from a specific set of numbers, which may not always be convenient or practical.

How is this proof relevant in real-world applications?

This proof can be useful in various fields such as cryptography, computer science, and number theory. It can also be used to solve problems involving divisibility, remainders, and modular arithmetic.

Similar threads

Replies
5
Views
1K
Replies
3
Views
2K
Replies
7
Views
2K
Replies
6
Views
2K
Replies
1
Views
1K
Replies
1
Views
899
Replies
1
Views
1K
Back
Top