Proof That 6 Divides Any Integer N

  • Thread starter Thread starter Math100
  • Start date Start date
  • Tags Tags
    Integer Proof
AI Thread Summary
The discussion provides a proof that a positive integer N is divisible by 6 if and only if a specific integer M, defined as M = a0 + 4a1 + 4a2 + ... + 4am (where ak are the digits of N), is also divisible by 6. The proof begins by establishing that since 6 = 2 × 3, both conditions for divisibility by 2 and 3 must hold for N. It demonstrates that if 6 divides N, then 2 and 3 also divide M, leading to the conclusion that 6 divides M. Conversely, if 6 divides M, the proof shows that it leads to the conclusion that 6 divides N. Thus, the divisibility of N by 6 is equivalent to the divisibility of M by 6.
Math100
Messages
813
Reaction score
229
Homework Statement
Let ## N=a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0} ##, where ## 0\leq a_{k}\leq 9 ##, be the decimal expansion of a positive integer ## N ##.
Prove that ## 6 ## divides ## N ## if and only if ## 6 ## divides the integer
## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.
Relevant Equations
None.
Proof:

Suppose that ## 6 ## divides ## N ##.
Let ## N=a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0} ##, where ## 0\leq a_{k}\leq 9 ##, be the
decimal expansion of a positive integer ## N ##.
Note that ## 6=2\dotsb 3 ##.
This means ## 2\mid 6 ## and ## 3\mid 6 ##.
Then ## 2\mid [4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m}]\implies 2\mid N\Leftrightarrow 2\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})] ##.
Now we have ## 3\mid (a_{0}+a_{1}+a_{2}+\dotsb +a_{m})\Leftrightarrow 3\mid [a_{0}+(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})+3(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]\Leftrightarrow 3\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]\Leftrightarrow 3\mid N ##.
Observe that ## 6\mid N\Leftrightarrow 6\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})] ##.
Thus, ## 6 ## divides the integer ## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.
Conversely, suppose ## 6 ## divides the integer ## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.
Then ## 10^{m}\equiv 4\pmod {6} ## ## \forall m\in\mathbb{N}\implies 10^{m}-4\equiv 0\pmod {6} ## ## \forall m\in\mathbb{N} ##.
This means ## 6\mid (10^{m}-4) ## ## \forall m\in\mathbb{N} ##.
Observe that ## 6\mid [(a_{0}+4a_{1}+\dotsb +4a_{m})+(10-4)a_{1}+(10^{2}-4)a_{2}+\dotsb +(10^{m}-4)a_{m}]\implies 6\mid (a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0}) ##.
Thus ## 6\mid N ##.
Therefore, ## 6 ## divides ## N ## if and only if ## 6 ## divides the integer ## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.
 
Physics news on Phys.org
Math100 said:
Homework Statement:: Let ## N=a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0} ##, where ## 0\leq a_{k}\leq 9 ##, be the decimal expansion of a positive integer ## N ##.
Prove that ## 6 ## divides ## N ## if and only if ## 6 ## divides the integer
## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.
Relevant Equations:: None.

Proof:

Suppose that ## 6 ## divides ## N ##.
Let ## N=a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0} ##, where ## 0\leq a_{k}\leq 9 ##, be the
decimal expansion of a positive integer ## N ##.
Note that ## 6=2\dotsb 3 ##.
This means ## 2\mid 6 ## and ## 3\mid 6 ##.
Then ## 2\mid [4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m}]\implies 2\mid N\Leftrightarrow 2\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})] ##.
I wouldn't use ##\Leftrightarrow ## if you only prove one direction. You said ##6\,|\,N.##
So ##2 \,|\,N = 2\cdot 5 \cdot (a_{m}10^{m-1}+\dotsb +a_{2}10+a_{1}) + a_0## and ##2\,|\,a_0.##
Now, I see that ##2\,|\,(a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})).##
Math100 said:
Now we have ## 3\mid (a_{0}+a_{1}+a_{2}+\dotsb +a_{m})\Leftrightarrow 3\mid [a_{0}+(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})+3(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]\Leftrightarrow 3\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]\Leftrightarrow 3\mid N ##.
Looks correct. But again, avoid the equivalence. We are only interested in one direction. It is easier to read as
\begin{align*}
3\mid (a_{0}+a_{1}+a_{2}+\dotsb +a_{m})&\Rightarrow 3\mid [a_{0}+(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})+3(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]\\
&\Rightarrow 3\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]
\end{align*}
Math100 said:
Observe that ## 6\mid N\Leftrightarrow 6\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})] ##.
Thus, ## 6 ## divides the integer ## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.
The key is again that ##2## and ##3## are coprime. We have shown ##6\,|\,N \Longrightarrow ##
\begin{align*}
2&\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]\\
&\text{and}\\
3&\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]\\
&\Longrightarrow \\
2\cdot 3 = 6&\mid [a_{0}+4(a_{1}+a_{2}+a_{3}+\dotsb +a_{m})]
\end{align*}
But the last conclusion is only correct for coprime numbers.
E.g. ##2\,|\,12 \wedge 4\,|\,12 \nRightarrow 2\cdot 4= 8\,|\,12.## But ##2## and ##3## are coprime, so ##2\,|\,12 \wedge 3\,|\,12 \nRightarrow 2\cdot 3= 6\,|\,12.##

Math100 said:
Conversely, suppose ## 6 ## divides the integer ## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.

Then ## 10^{m}\equiv 4\pmod {6} ## ## \forall m\in\mathbb{N}\implies 10^{m}-4\equiv 0\pmod {6} ## ## \forall m\in\mathbb{N} ##.
This means ## 6\mid (10^{m}-4) ## ## \forall m\in\mathbb{N} ##.
Observe that ## 6\mid [(a_{0}+4a_{1}+\dotsb +4a_{m})+(10-4)a_{1}+(10^{2}-4)a_{2}+\dotsb +(10^{m}-4)a_{m}]\implies 6\mid (a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0}) ##.
Thus ## 6\mid N ##.
Therefore, ## 6 ## divides ## N ## if and only if ## 6 ## divides the integer ## M=a_{0}+4a_{1}+4a_{2}+\dotsb +4a_{m} ##.
Correct. Only the layout isn't optimal:

Observe that
\begin{align*}
6&\mid [(a_{0}+4a_{1}+\dotsb +4a_{m})+(10-4)a_{1}+(10^{2}-4)a_{2}+\dotsb +(10^{m}-4)a_{m}]\\
&\implies \\
6&\mid (a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0}) =N
\end{align*}
 
If you want to prove both directions at once, you can use your second part and write:
\begin{align*}
6\,&|\,a_0+4(a_1+\ldots+a_m)=a_0+ 2\cdot (2a_1+\ldots+2a_m) = a_0+a_1+\ldots+a_m+3(a_1+\ldots+a_m)\\
&\Longleftrightarrow \\
2\,&|\,a_0 \wedge 3\,|\,(a_0+a_1+\ldots+a_m)\\
&\Longleftrightarrow \\
2\,&|\,N\wedge 3\,|\,N\\
&\Longleftrightarrow \\
6\,&|\,N
\end{align*}
 
Interesting. Getting to know for m=1,2,3...

10^m =99..99+1 \equiv 1 (\mod 3)
10^m -4 \equiv 0 (\mod 3)
10^m -4 \equiv 0 (\mod 2)
So
10^m \equiv 4 (\mod 6)
a_m 10^m \equiv 4 a_m (\mod 6)
\sum_{m=1}^n a_m 10^m \equiv 4 \sum_{m=1}^n a_m (\mod 6)
a_0+\sum_{m=1}^n a_m 10^m \equiv a_0+4 \sum_{m=1}^n a_m (\mod 6)
 
Last edited:
Back
Top