IMC 2007 Q23
23. As \(n\) takes each positive integer value in turn (that is, \(n = 1\), \(n = 2\), \(n = 3\), and so on) how many different values are obtained for the remainder when \(n^2\) is divided by \(n + 4\)?
- A 1
- B 8
- C 9
- D 16
- E Infinitely many
Intermediate Mathematical Challenge 2007, Question 23. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: C 9
Note that
\(\dfrac{n^2}{n + 4} = \dfrac{n^2 - 16}{n + 4} + \dfrac{16}{n + 4} = \dfrac{(n + 4)(n - 4)}{n + 4} + \dfrac{16}{n + 4} = n - 4 + \dfrac{16}{n + 4}, (n \neq -4).\)
So when \(n > 12\), the remainder when \(n^2\) is divided by \(n + 4\) is always 16. For \(1 \leqslant n \leqslant 12\), the remainder when \(n^2\) is divided by \(n + 4\) is shown in the table below.
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| \(n + 4\) | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| remainder | 1 | 4 | 2 | 0 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
So there are 9 different remainders, namely 0, 1, 2, 3, 4, 5, 6, 7, 16.
Solution © UK Mathematics Trust, from the IMC 2007 solutions.