Prove that ## 7, 11 ##, and ## 13 ## all divide ## N ##

[Math100]

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 $7, 11$, and $13$ all divide $N$ if and only if $7, 11$, and $13$ divide the integer $M=(100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})-\dotsb$.
[Hint: If $n$ is even, then $10^{3n}\equiv 1, 10^{3n+1}\equiv 10, 10^{3n+2}\equiv 100\pmod {1001}$; if $n$ is odd, then $10^{3n}\equiv -1, 10^{3n+1}\equiv -10, 10^{3n+2}\equiv -100\pmod {1001}$.]

Relevant Equations

None.

Proof:

Assume that $7, 11$, and $13$ all divide $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$.
Observe that $7\cdot 11\cdot 13=1001$.
Now we consider two cases.
Case #1: Suppose $n$ is even.
Then $10^{3n}\equiv 1\implies 10^{3n+1}\equiv 10$.
Thus $10^{3n+2}\equiv 100\pmod {1001}$.
Case #2: Suppose $n$ is odd.
Then $10^{3n}\equiv -1\implies 10^{3n+1}\equiv -10$.
Thus $10^{3n+2}\equiv -100\pmod {1001}$.
Since $N=a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0}\equiv [(100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})-\dotsb]\pmod {1001}$, it follows that $N\equiv 0\pmod {1001}$.
Thus $7, 11$, and $13$ divide the integer $M=(100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})-\dotsb$.
Conversely, suppose $7, 11$, and $13$ divide the integer $M=(100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})-\dotsb$.
Note that $7\cdot 11\cdot 13=1001$.
Then $(100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})-\dotsb\equiv 0\pmod {1001}$.
This means $a_{m}10^{m}+\dotsb +a_{2}10^{2}+a_{1}10+a_{0}\equiv 0\pmod {1001}\implies N\equiv 0\pmod {1001}$.
Thus $7, 11$, and $13$ all divide $N$.
Therefore, $7, 11$, and $13$ all divide $N$ if and only if $7, 11$, and $13$ divide the integer $M=(100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})-\dotsb$.

 

[fresh_42]

What happens at the end of the line? Your proof works well if $6\,|\,m$ so you can group the numbers in packages of three even $n$ and three odd $n$, but what happens in the five other cases?

 

[Math100]

What happens at the end of the line? Your proof works well if $6\,|\,m$ so you can group the numbers in packages of three even $n$ and three odd $n$, but what happens in the five other cases?

I don't understand. If $6\mid m$, then how can I group them in packages of three even...? How can this be applied?

 

[Math100]

$(100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})-\dotsb\pmod {6}$

 

[fresh_42]

I don't understand. If $6\mid m$, then how can I group them in packages of three even...? How can this be applied?

You start with
\begin{align*}
1001\,|\,N&=(100a_{2}+10a_{1}+a_{0})\cdot 10^0+(100a_{5}+10a_{4}+a_{3})\cdot 10^3+(100a_{8}+10a_{7}+a_{6})\cdot 10^6\mp \dotsb\\
&\equiv (100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})\mp \dotsb =M \pmod {1001}
\end{align*}

Oh, now I see that $1001\,|\,M.$

The other direction is the same, only that we start with $1001\,|\,M=\ldots \equiv N\pmod {1001}$

I mistakenly first thought that you would group the polynomial as packages of three with alternating signs:
$$
N=\underbrace{(100a_{2}+10a_{1}+a_{0})\cdot 10^0}_{n=0}+\underbrace{(100a_{5}+10a_{4}+a_{3})\cdot 10^3}_{n=1}+\underbrace{(100a_{8}+10a_{7}+a_{6})\cdot 10^6}_{n=2}\mp \dotsb
$$
and wondered if we can do this if $6\nmid m.$

 

[Math100]

You start with
\begin{align*}
1001\,|\,N&=(100a_{2}+10a_{1}+a_{0})\cdot 10^0+(100a_{5}+10a_{4}+a_{3})\cdot 10^3+(100a_{8}+10a_{7}+a_{6})\cdot 10^6\mp \dotsb\\
&\equiv (100a_{2}+10a_{1}+a_{0})-(100a_{5}+10a_{4}+a_{3})+(100a_{8}+10a_{7}+a_{6})\mp \dotsb =M \pmod {1001}
\end{align*}

Oh, now I see that $1001\,|\,M.$

The other direction is the same, only that we start with $1001\,|\,M=\ldots \equiv N\pmod {1001}$

I mistakenly first thought that you would group the polynomial as packages of three with alternating signs:
$$
N=\underbrace{(100a_{2}+10a_{1}+a_{0})\cdot 10^0}_{n=0}+\underbrace{(100a_{5}+10a_{4}+a_{3})\cdot 10^3}_{n=1}+\underbrace{(100a_{8}+10a_{7}+a_{6})\cdot 10^6}_{n=2}\mp \dotsb
$$
and wondered if we can do this if $6\nmid m.$

What does $\mp$ symbolize?

 

[fresh_42]

What does $\mp$ symbolize?

That the signs alternate between $+$ and $-$. If the next one is a minus sign, then it is $\mp$ and if it is a plus sign, then it is $\pm$.