2
$\begingroup$

When I was still in elementry school (4-12 years old in Holland) we were tought to do multiplication without the use of a calculator, for example 128 * 415. When I came home with some homework my father recalled a trick he learned when he was younger. I remembered this recently, but can't figure out how it works.

First you calculate the result:

    128
    415 x
  -------
    640
   1280
  51200 +
 --------
  53120

Then the trick: Take the separate digits of the first number: 1,2 and 8. Add these together: 1 + 2 + 8 = 11 While the result is more than one digit, do it again: 1 + 1 = 2. The first "checksum" is 2.

Do the same for the second number: 4 + 1 + 5 = 10, then our second checksum is 1: 1 + 0 = 1.

Multiply these checksums: 1 * 2 = 2. The checksum of the input in this case is 2.

Now we do the same for the answer we calculated: 5 + 3 + 1 + 2 + 0 = 11, This means our answer checksum is 2: 1 + 1 = 2.

Finally compare both "checksums": we found 2 for the input and 2 for the answer, which means our answer might be correct. I'm pretty sure it's not a 100% secure check with chances of false-positives, but I haven't come across one where the checksum failed on a correct answer, or where the checksum was correct but the answer was invalid.

The question: Can anyone explain how this works?

$\endgroup$
  • $\begingroup$ Look up: digital roots $\endgroup$ – Robert Israel Jan 13 '17 at 7:24
  • $\begingroup$ Number divided by 9 will have remainder equal to checksum. N*M divided by 9 will have remainder of the remainder of N divided by 9 times the remainder of M divided by nine checksummed. $\endgroup$ – fleablood Jan 13 '17 at 7:39
  • $\begingroup$ So I've written a short little program to test this theory, and I can very easily create a lot of false negatives: bit.ly/2jez1BZ That 415 number you've got seems to be a tad bit magical. $\endgroup$ – fny Jan 13 '17 at 7:42
  • $\begingroup$ When used as an arithmetic check, it's often known as casting out nines. It relies on something called modular arithmetic and, because we use a base-$10$ numeral system, the fact that $10 = 9 + 1$. $\endgroup$ – pjs36 Jan 13 '17 at 8:16
  • $\begingroup$ 11 %False positives are fine as its just a test. There will be no "true negatives" (it will never fail if you have a right answer). If you got the right answer, the test will pass 100% of the time. If you got a wrong answer the test will pass 11% of the time. $\endgroup$ – fleablood Jan 13 '17 at 8:18
2
$\begingroup$

Let N = abcd = 1000a+100b+10c+d.

Divide by by 9 and take the remainder. You get

N = 9 (111a+11b+c) +(a+b+c+d)

So both N and the checksum have the same remainder.

So if checksum N = n and checksum M =m, that means N=9 x something + n, and M = 9 x thingsome + m. So NxM = 9 x athirdthing + nm. So checksum N xM = checksum nxm.

===

Example:

128 = 100 + 20 + 8=9 (11+2)+(1+2+8)

415= 400+10+5=9 (4×11+1)+(4+1+5)

So 128×415=

9[9×(11+2)(4×11+1)+(11+2)(4+1+5)+(4×11+1)(1+2+8)]+(1+2+8)×(4+1+5)

But if 128×415=abcdef then

128×415=

9×(a×11111+b×1111+c×111+d×11+e)+(a+b+c+d+e+f)

So (1+2+8)×(4+1+5) will have the same remainder as (a+b+c+d+e+f) when divided by 9.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

You are actually re-doing the multiplication modulo $9$, using two properties:

  1. the sum of the digits of a number is that number modulo $9$,

  2. modulo "preserves the product"*, $(a\times b)\bmod9=(a\bmod 9)\times(b\bmod 9)$.

Indeed, let $a$ be written $\alpha\beta\gamma$. We have $$(100\alpha+10\beta+\gamma)\bmod9=(100\bmod9)\alpha+(10\bmod9)\beta+\gamma=\alpha+\beta+\gamma.$$

And

$$(a\bmod9)(b\bmod9)=(a-9a')(b-9b')=ab-9a'b-9ab'+81a'b'=ab\bmod9.$$

So if $c=a\times b$, the sum of the digits of $c$ must equal the product of the sum of the digits of $a$ and the sum of the digits of $b$.

$$(128\bmod9)\times(415\bmod9)=2\times1=2=53120\bmod9.$$

The converse is not necessarily true, equality can occur by accident. For instance if you swapped two digits while copying, or wrote a $9$ for a $0$, or made several errors.

$$(128\bmod9)\times(415\bmod9)=2\times1=2=5\color{red}{85}20\bmod9.$$

As the result of a modulo can take $9$ distinct values, one may estimate grossly that the check will detect errors in $8$ cases out of $9$, hence it improves the reliability of the computation by a factor $9$.


*For clarity of the notation, we left implicit that the sums of the digits and the products must be taken modulo $9$ themselves, to discard the possible carries.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.