Monday, 5 January 2015

elementary number theory - $11$ divisibility



We know that $1331$ is divisible by $11$.
As per the $11$ divisibility test, we can say $1331$ is divisible by $11$. However we cannot get any quotient. If we subtract each unit digit in the following way, we can see the quotient when $1331$ is divided by $11$.



$1331 \implies 133 -1= 132$
$132 \implies 13 - 2= 11$
$11 \implies 1-1 = 0$, which is divisible by $11$.



Also the quotient is, arrange, all the subtracted unit digits (in bold and italic) from bottom to top, we get $121$. Which is quotient.
I want to know how this method is working? Please write a proof.



Answer



Look how the method works for the number $abcde$. You substract $e$ from $abcd$, getting $a'b'c'd'$, and you apply the method to $a'b'c'd'$. If the method works for $a'b'c'd'$, it yields $n'$ such that $a'b'c'd'=11\times n'$. But $a'b'c'd'0$ is $a'b'c'd'\times 10=11\times 10\times n'$ and $abcde=a'b'c'd'\times 10+e\times 11$ hence $abcde=11\times 10\times n'+11\times e$ is $11\times(10\times n'+e)$. This proves that $n=10\times n'+e$ is indeed the correct answer for $abcde$.



Edit (Upon OP's request, the same proof, with more apparatus but with zero more mathematics.)



Look how the method works for the number $N=a_ka_{k-1}\cdots a_2a_1a_0$ with $k\geqslant1$. You substract $a_0$ from $a_ka_{k-1}\cdots a_2a_1$, getting $M=b_kb_{k-1}\cdots b_2b_1$, and you apply the method to $M$. If the method works for $M$, it yields $m$ such that $M=11\times m$. But $b_kb_{k-1}\cdots b_2b_10$ is $M\times 10=11\times 10\times m$ and $N=M\times 10+a_0\times 11$ hence $N=11\times 10\times m+11\times a_0$ is $11\times(10\times m+a_0)$. This proves that $n=10\times m+a_0$ is indeed the correct answer for $N$ if $m$ was the correct answer for $M$. A recursion on the number of digits of $N$ yields the result.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...