#math trivia for #September12: #255 is the largest 8-bit number. For what n does the largest n-bit number divide 255? Vice versa?

— Burt Kaliski Jr. (@modulomathy) September 13, 2013

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 2^{n}-1. This value can be factored as

2^{n}-1 = (2^{k}-1)*(2^{(n-k)}+2^{(n-2k)}+ … +2^{k}+1)

for any k dividing n. Thus the largest k-bit number, 2^{k}-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 2^{16}-1 = 65535, 2^{24}-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 2^{n}-1 is divisible by 2^{k}-1, then we just need to know the value

2^^{n} mod 2^{k}-1

(the remainder after dividing 2^{n} by 2^{k}-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 2^{m}. This is not 1, so 2^{n}-1 is not divisible by 2^{k}-1 in these cases. It follows that the only divisors (or multiples) of 255 are the ones listed.