#math trivia #255 solution

Only n-bit numbers for n ≤ 8 can possibly divide 255, so let’s consider the largest n-bit numbers for n from 1 to 8.  They are 1, 3, 7, 15, 31, 63, 127, and 255.  Four of these divide 255:  1, 3, 15, and 255.

There’s a pattern:  the numbers that divide 255 are the largest n-bit numbers for n = 1, 2, 4 and 8.  This makes sense because the largest n-bit number is 2n-1.  This value can be factored as

2n-1 = (2k-1)*(2(n-k)+2(n-2k)+ … +2k+1)

for any k dividing n. Thus the largest k-bit number, 2k-1, divides the largest n-bit number when k divides n.

What about the reverse? What n-bit numbers does 255 divide? Following the same logic, 255 divides the largest n-bit number whenever 8 divides n. For example, 255 divides 216-1 = 65535, 224-1 = 16777215, and so on.

What about the case that k doesn’t divide n (or vice versa)? We can work this out by modular arithmetic. If we want to know whether 2n-1 is divisible by 2k-1, then we just need to know the value

2^n mod 2k-1

(the remainder after dividing 2n by 2k-1). If n is a multiple of k, then the remainder is 1. If n is not a multiple of k, but instead is m more than a multiple of k for some m between 1 and k-1, then the remainder is 2m. This is not 1, so 2n-1 is not divisible by 2k-1 in these cases. It follows that the only divisors (or multiples) of 255 are the ones listed.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s