— 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 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.