Friday, 1 August 2008

It is sort of like casting out sevens


Sometimes I enter the math contest they host at the Wild About Math blog site, and usually am among the people who get a correct answer, but haven't been the lucky name pulled from the hat yet. A recent problem about divisibility got me thinking about testing by divisibility by sevens again.

The problem was actually about divisibility by eleven, and asked
Consider all of the 6-digit numbers that one can construct using each of the digits between 1 and 6 inclusively exactly one time each. 123456 is such a number as is 346125. 112345 is not such a number since 1 is repeated and 6 is not used.


How many of these 6-digit numbers are divisible by 11?

The answer, of course, is none. If you don't know the rule for testing eleven see my blog on casting out nines and elevens. My interest was piqued by a resonse by Jonathan, of the jd2718 blog made these observations about the 6! or 720 possible numbers formed with the six digits as described:

As a consolation, all 720 of them are multiples of 3.

Half of them (360) are even (multiples of 2)

One in 6 (120) are multiples of 5.

Eight in thirty (192) are multiples of 4.

None are multiples of 9.

Fourteen of 120 (84) are multiples of 8.

Multiples of 7? New puzzle, good place to stop.

It is Not surprising that Jonathon covered all the other one digit divisors but did NOT test seven. Seven is the one that books on mental math simply say "divide by seven"; but thinking about it, it shouldn’t be too hard

I wrote recently about a mental test for divisibility by seven but it did have one flaw. It worked fine to tell you a number was divisible by seven, but if the number was not divisible by seven it did not give the correct modulus. Casting out nines will always give you the correct modulus. The sum of the digits of 2134 is 10 which has a digit root of 1, so if you divide 2134 by 9 you get a remainer of one. My rule for seven didn't give the true remainder.

The remainder when you divide a number by seven (or any other number) is frequently called the modulus. I've mentioned this before, it is just a way to divide integers into sets. Odd numbers are all equivalent to 1 mod 2 (they all leave a remainder of one when you divide by 2) and even numbers are all equivalent to zero. If a number is equivalent to zero mod (something) that means it is divisible by that (something). One of the things that makes them effective is the simple rule that if a+b=c then for any modular index n(the number you are dividing by) c mod n = a mod n + b mod n. For example 25 mod 7 = 4 and 25 = 20 + 5 by 20 mod 7 = 6, and 5 mod 7 = 5... 6+5 = 11 which is equivalent to 4 mod 7. So now we have the basics.


Every increase of one in the units increases the modulus 1, and every increase in the tens increases the modulus three, (for example 21 mod 7 = 0; 31 mod 7 = 3,and 41 mod 7 = 6). I figured out that the rest would be an increase of two in the hundreds, six in the thousands (think minus one) four in the ten-thousands (minus three?) and five in the hundred-thousands (minus two….) so the sequence is 546231… and what a coincidence, if you multiply 5(-2)+4(-3)+6(-1)+2(2) +3(3) + 1(1) …YOU GET -14, which is zero mod 7, the sequence of moduli used in each place makes it a multiple of seven…(546231 = 0 [mod 7]… but wait, 231 by itself is a multiple of seven, since4 23 - 2(1) =21… and 546 is also. [54 - 2(6)=42]..

It is probably easier on retrospect for that particular number to just square each digit in the sequence and discard any sevens (kind of like casting-out sevens) 25+16+36+4 + 9 + 1 is simplified to 4+2+1+4+2+1 and it is obvious the mod is seven…


To check other numbers, you can just write them out multiplied times the correct modulus for that place value and probably check it in your head, but you would have to check each one… so making up a sequence, 234561, we would think 2×5=10 (the first digit times the first modulus) drops to 3, plus 3(second digit)x4(second modulus) is 15 which drops to modulus of one, now add 4(6) to get 25 and drop to mod 4, then add 2×5 to get 14, and we are at mod 0 [so 234500 is divisible by seven] and we know that 61 is NOT divisible by seven, so we can be assured that 234561 == 61 == 5 mod 7… ok, not EASY, but certainly could be done sans calculator…. [footnote, for those of you who have just gone through an pre-calc class and somewhere along the way they taught you about vectors, you probably imagined that you would never run across another dot product in your life, but you just did. IF you think of the sequence of modular values as one vector (5,4,6,2,3,1) and the six-digits of the number as a second vector, then the dot product is an integer that has the same modulus as the original six digit number....come on... that's pretty cool use of vectors!!!]

It is easy enough to write remember the modulus up to ten-thousands (6231) to make this pretty useful as a factoring tool if you really needed the correct modulus. If the number is 4723 we just think 4(6)=24--> 3 + 7x2---> still 3, + 2(3)=9 -->2 and then + 3(1)= 5 so 6231 divided by seven leaves a remainder of five.

Ok, so if that seems too hard, here is a different problem I want to explain next time... IF you try to find the decimal number for 1/17 on the TI-84 it says 1/17 = .0588235294... and that's all you get. Now the challenge.... can you write out the complete decimal expansion (one complete cycle of the repeating expansion) of 1/17 using only what the calculator gave you and simple arithmetic... don't do the long division (you don't have to if you know something neat that I will show.. Try looking at 1/7 and 1/13 etc and see if you can find a clue...in fact, 1/11 is an incredibly interesting one to look at.... LATER!!!

Post a Comment