An equivalent fact will be proven: If a number sums to 76, using the numbers 1, 5, and 9, it can't be divisible by 37. Constructing this number is easier: twice the number of 1s chosen plus the number of 5s chosen must equal 8, filling the remaining spots with 9s.
Thus from this, it can be shown that all are of the form 99999999999999  8 terms of 3*10^k (where k is from 0 to 11, and no number is reused more than twice)
Since 999999999999 = 9*3*37*1001001001, it is a multiple of 37. Then we just need to show the removal of the 3*10^k terms can't add up to a mutlple of 37. Thus 30^k mod 37 can equal 3, 30, or 4, since it starts repeating after 4.
We have to add 8 of those terms, but we need to add them in sets of 3 to get the number to be 0 mod 37. Since that is impossible, the resulting number must not be divisible by 37, and if numbers that sum to 76 using 1, 5, and 9 can't be divisible by 37, then numbers using 1, 5, and 9 that are divisible by 37 can't sum to 76.

Posted by Gamer
on 20070123 02:24:04 