If an integer n is to be chosen at random from the integers 1 to 96, inclusive, what is the probability that n (n 1) (n 2) will be divisible by 8

If n is even, then n = 2k for integers 1 ≤ k ≤ 48, and

n (n - 1) (n - 2) = 2k (2k - 1) (2k - 2) = 4k (k - 1) (2k - 1)

and this product is clearly divisible by 4. k (k - 1) is the product of two consecutive integers, and one of these must be even, so it follows that n (n - 1) (n - 2) is always divisible by 8. So

Pr[n (n - 1) (n - 2) is divisible by 8 AND n is even]

= Pr[n (n - 1) (n - 2) is divisible by 8 || n is even] * Pr[n is even]

= 1 * 1/2

= 1/2

(where I write Pr[A || B] to denote the conditional probability of A given B)

If n is odd, then n = 2k - 1 for integers 1 ≤ k ≤ 48, and

n (n - 1) (n - 2) = (2k - 1) (2k - 2) (2k - 3) = 2 (k - 1) (2k - 1) (2k - 3)

This is clearly divisible by 2. We then need to find out when this is divisible by 4. We have

(k - 1) (2k - 1) (2k - 3) = 4k^3 - 12k^2 + 11k - 3

and we have divisibility by 4 if 4 divides 11k - 3. We have

11k - 3 = 0 mod 4

==> 11k = 3 mod 4

==> 33k = 3^2 = 1 mod 4

==> (32 + 1) k = 1 mod 4

==> k = 1 mod 4

That is, 4 divides 11k - 3 if k = 4r + 1 for integers 0 ≤ r ≤ 11. This means there are 12 integers r (and hence 12 integers k) for which 4 divides 11k - 3, which in turn means there are 12 integers n for which n (n - 1) (n - 2) is divisible 8. So

Pr[n (n - 1) (n - 2) is divisible by 8 AND n is odd]

= Pr[n (n - 1) (n - 2) is divisible by 8 || n is odd] * Pr[n is odd]

= 12/48 * 1/2

= 1/8

The cases that n is even or odd are mutually exclusive, so

Pr[n (n - 1) (n - 2) is divisible by 8 = 1/2 + 1/8 = 5/8