Friday, December 22, 2006

A Saucerful Of Secrets

In response to Kimota94's post about math tricks...here's a few 'tests for divisibility' that you can use to impress your (geeky) friends.

1) An integer is divisible by 2 iff (that's if and only if for you non-geeks) its last digit is divisible by 2. If you didn't know this one already there's a problem ;).

2) An integer is divisible by 4 iff its last two digits are divisible by 4 because 100 is equivalent to 0 mod 4 (again, for the non geeks, mod is short for modulus meaning remainder (100/4 = 25 remainder 0, 0/4 = 0 remainder 0 - the two remainders are equal so 100 and 0 are equivalent mod 4)

3) A number is divisible by 3 iff the sum of its digits is divisible by 3.
Proof:
coming later

4) An integer is divisible by 9 iff the sum of its digits is divisible by 9 (casting out nines)

Proof:
Let x be an integer with digits arar-1…a1a0.
Therefore x = ar*10r + ar-1*10r-1+…+a1*10+a0

Now 10 is equivalent to 1 mod 9
Therefore, for all k > 0, 10k is equivalent to 1k which is equivalent to 1 mod 9.

Now look at x mod 9:
x = ar*1 + ar-1*1 +… + a1*1 + a0 (mod 9)
Therefore x is congruent to 0 (mod 9) (i.e. it is divisible by 9) when the sum of:
ar+ar-1+…+a1+a0 is congruent to 0 (mod 9)

Another way of saying it is that x is divisible by 9 when the sum of its digits is divisible by 9.

5) A number is divisible by 11 iff the alternating sum of its digits is divisible by 11.

Proof:
Mainly left to the reader. It is almost identical to the proof for 9s except 10 is equivalent to -1 mod 11 so the 10k is either 1 or -1 depending on if k is even or not.

1 comment:

Kimota94 aka Matt said...

That kind of talk really makes me hot... if you know what I mean!!