Monday, 23 March 2015

Analysis for Realsies (2015): 1

Hey guys! Sooo, last week in Tute A y'all saw this cool fact that one way to check the divisibility of a (natural) number by \(3\) is to add up all of its digits and check to see if the resulting sum is divisible by \(3\).

E.g.: take \(832745812349\), now \(8+3+2+7+4+5+8+1+2+3+4+9=56\) and \(56\) isn't divisible by \(3\). Therefore \(832745812349\) isn't divisible by \(3\).

And in fact, this is also true for \(9\), you can add up the digits of a number and if this sum is divisible by \(9\), then the original number must also be divisible by \(9\) (and vice versa).

I then asked you to try to figure out a similar trick for \(11\), and you can find the rule (and a derivation/proof) here!

Well, I then issued like a super-ninja-hax-challenge version of this where I asked you to derive a similar rule for divisibility by \(101,1001,10001,100001,\ldots\) How did you go with this? I'll write the answer below, but I kinda want you to take a look at the above blog post first.

Here we go:

So, the trick for divisibility with respect to \(11\) of a \(k\)-digit whole number (with digit representation) \(\overline{n_0 n_1 n_2\ldots n_k}\) is to take the following "alternating sum" \begin{align} n_k-n_{k-1}+n_{k-2}-\ldots+(-1)^kn_0,\end{align} and if this sum is divisible by \(11\), then the original number is divisible by \(11\). Note in particular, the order in which we've go - we've taken the last digit, subtracted the second last...etc. And the reason that we've done this is because this presentation generalises more easily to \(101,1001,\ldots\)

So, what about \(101\)? Well, the rule is to take the last two digits, subtract the next pair, then add the next pair, and so forth. So, let's see an example:

the number \(74914071682\) satisfies that \begin{align} 82-16+7-14+49-7=101,\end{align} which is clearly divisible by \(101\). Thus, \(74914071682\) should be divisible by \(101\) and indeed:  \(74914071682=101\times 741723482\).

And the generalisation to \(1001\) involves us taking the last three digits, then subtracting the next triple, and adding the next triple...etc. And I the pattern goes on...

What about the proof!? I hear you ask. Well, it's pretty similar to the proof for our rule regarding divisibility by \(11\). So, I'll let this to you guys as a healthy challenge exercise. =)

No comments:

Post a Comment