## Powerful Divisibility

#### Problem

Given that `n` is a positive integer, prove that 21^{n} 5^{n} + 8^{n} is always divisible by 24.

#### Solution

By using the result,`x ^{n}`

`y`= (

^{n}`x`

`y`)(

`x`

^{n 1}+ ... +

`y`

^{n 1})

21^{n} 5^{n} + 8^{n} = (21 5)(21^{n 1} + ... + 5^{n 1}) + 8^{n} = 16`X` + 8^{n} 0 `mod` 8

And by writing the expression differently,

8^{n} 5^{n} + 21^{n} = (8 5)(8^{n 1} + ... + 5^{n 1}) + 21^{n} = 3`Y` + 21^{n} 0 `mod` 3

As the expression is divisible by both 3 and 8, it must be divisible by 24.

Problem ID: 32 (Jan 2001) Difficulty: 3 Star