Thursday, February 9, 2012

What is the smallest integer?

What is the smallest integer greater than 0 that can be written entirely with zeros and ones and is evenly divisible by 225?

The prime factorization of 225 is 5*5*3*3. So the answer will be both a multiple of 25 and of 9.
All multiples of 25 end in either 00, 25, 50, or 75. The only one of these composed of 0's and 1's is obviously 00, so the answer must end in 00. The hard part is finding a series of 0's and 1's preceeding the 00 that will make the entire number divisible by 9.
If you didn't already know the following trick then this problem would be very hard. If you did know it then the problem was was likely very easy. The trick is that if the sum of digits of a number is divisible by 9 then the number itself is also divisible by 9. Note that this is true for 3 also. For example the number 17685 is divisible by 9 because 1+7+6+8+5=27, and 27 is divisible by 9.
To prove this let's consider any five digit number, abcde. This number can be expressed as follows.

a*10000 + b*1000 + c*100 + d*10 + e =
a*(9999+1) + b*(999+1) + c*(99+1) + d*(9+1) + e*1 =
a*9999 + b*999 + c*99 + d*9 + a + b + c + d + e =
9*(a*1111 + b*111 + c*11 + d*1) + a + b + c + d + e

Thus 9*(a*1111 + b*111 + c*11 + d*1)  is a multiple of 9. So if  a+b+c+d+e  is also a multiple of 9 then the entire number must be a multiple of 9. Note also that the remainder of abcde/9 is the same as the remainder of  (a+b+c+d+e)/9
The smallest number consisting of all 1's and divisible by 9 is thus 111,111,111. Adding the two zeros at the end results in the answer to the problem: 11,111,111,100.

No comments:

Post a Comment