modulomathy.com

#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ⁿ-1.  This value can be factored as

2ⁿ-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¹⁶-1 = 65535, 2²⁴-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ⁿ-1 is divisible by 2^k-1, then we just need to know the value

2^ⁿ mod 2^k-1

(the remainder after dividing 2ⁿ 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ⁿ-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.