a buddy of mine likes to post hard math questions on his myspace blog for us to solve. I'm not a math guy but its nice to know the answer so a little help would be great.

here it is

Assume x is an integer with many, many digits. In fact, just assume it has a googol digits. What is the minimum number of digits you need to know from x to determine if it is divisible by:

17?
40?
128?
3125?



good luck

Well I can do 40, if the last digit is 0 and the penultimate 2 digits are divisible by 4 then it is divisible by 40.

i.e.. You need the last 3 digits.

The other ones I need more time to think about :)

Well think hard and quick!

128 = 2^7. 10 = (5 x 2).

To be sure that the number is divisible by 128, you will need the last seven digits. This is because 10^7, and all multiples of 10^7, are divisible by 128.

Similarly, 3125 = 5^5, so you'll need the last five digits to determine if the number is divisible by 3125.

17 is a prime number, and will not divide evenly into any multiple of ten. Intuitively, this tells me that you will require all of the digits of the number to determine if it is divisible by 17. Unfortunately, I don't have a rigorous mathematical proof of this.

BTW - 40 = 5 x 2^3, so you'll need the last three digits, just as Capuchin says.

I had the same inkling about 17 as dmatos did. If that helps :)

40 : you need to have 3 right digits
17 : you can't tell and have to see all of it.
128: you have to have7 the first digits.
3125:you have to have 5 the first numbers.
I'm 100% sure.

3x+2y=2
y+8=3x

Quote:

---

Originally Posted by BIGBUG13

40 : you need to have 3 right digits
17 : you can't tell and have to see all of it.
128: you have to have7 the first digits.
3125:you have to have 5 the first numbers.
I'm 100% sure.

---

Interesting problem - I like it, and the solution looks good. However -- no where does the problem state that you are limited to numbers in base 10. So, for example, if the number is given in hexadecimal (base 16), and recognizing that 128 is hexadec 80, you can determine if a number is divisible by 128 with just the last two digits. If the number is given in base 17, the determination of whether its divisible by 17 is trivial.