MOG 2015 Q5
The integer \(N\) is a square. Find, with proof, all possible remainders when \(N\) is divided by 16.
Find all positive integers \(m\) and \(n\) such that\[m! + 76 = n^2.\]
[The notation \(m!\) stands for the factorial of \(m\), that is, \(m! = m \times (m - 1) \times \dots \times 2 \times 1\).
For example, \(4! = 4 \times 3 \times 2 \times 1\).]
Mathematical Olympiad for Girls 2015, Question 5. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: (a) 0, 1, 4 and 9 (b) \((m, n) = (4, 10)\) and \((5, 14)\)
Commentary
It seems reasonable to start by working out remainders of some square numbers; you may soon notice a pattern. However, we need to produce a general argument.
If number \(n\) gives remainder \(r\) when divided by 16, we can write it as \(n = 16k + r\). The possible values of \(r\) are \(0, 1, 2, \dots, 15\). For example, if \(n\) gives remainder 5 when divided by 16 then \(n = 16k + 5\), so\[n^2 = (16k + 5)^2 = 256k^2 + 160k + 25.\]Notice that the first two terms are divisible by 16, so \(n^2\) gives the same remainder as 25 when divided by 16.
We can repeat this calculation for each \(r\) from 0 to 15 to get the list of all possible remainders. It is worth noticing a slight shortcut: the remainders seem to repeat from \(r = 8\). The solution below demonstrates why this is the case.
Write \(N = n^2\) and \(n = 8k + r\) where \(r\), the remainder when \(n\) is divided by 8, is one of 0, 1, 2, \(\dots\), 7. Then \(N = (8k + r)^2 = 64k^2 + 16kr + r^2\), and this leaves the same remainder as does \(r^2\) when divided by 16.
Those remainders \(R\) are shown in the following table.
| r | R |
| 0 | 0 |
| 1 | 1 |
| 2 | 4 |
| 3 | 9 |
| 4 | 0 |
| 5 | 9 |
| 6 | 4 |
| 7 | 1 |
Thus the possible remainders when \(N\) is divided by 16 are 0, 1, 4 and 9.
Commentary
Part (a) suggests that it may be helpful to look at remainders when dividing by 16. The possible remainders of \(n^2\) are 0, 1, 4 and 9, and 76 gives remainder 12. So \(m!\) needs to give the remainder 4, 5, 8 or 13 when divided by 16.
Looking at some factorial numbers suggests that after a certain point, they are all divisible by 16. This is because \(6!\) is a multiple of 16 and all further factorial numbers are multiples of \(6!\) (e.g., \(7! = 6! \times 7\), \(8! = 6! \times 7 \times 8\) and so on).
This means that \(m\) cannot be greater or equal to 6. We only need to check positive integers smaller than 6 to find all the solutions.
If \(m \ge 6\) then \(m!\) is a multiple of \(6! = 720\), which itself is a multiple of 16. Therefore the remainder when \(m! + 76\) is divided by 16 is the same as the remainder when 76 is divided by 16, which is 12. From part (a) we know, then, that \(m! + 76\) cannot be a square if \(m \ge 6\).
If \(m\) is 1, 2 or 3, then the remainders after division of \(m! + 76\) by 16 are 13, 14 and 2 respectively, and so \(m! + 76\) cannot be a square.
But if \(m = 4\) then \(m! + 76 = 24 + 76 = 100 = 10^2\), and if \(m = 5\) then \(m! + 76 = 120 + 76 = 196 = 14^2\). Therefore the only pairs \((m, n)\) of positive integers such that \(m! + 76 = n^2\) are \((4, 10)\) and \((5, 14)\).
Note
We could look at remainders on division by some other numbers. For example, a similar argument works if we look at division by 7. For \(m \ge 7\), \(m! + 76\) gives remainder 6 when divided by 7, and we can show that a square number cannot give this remainder.
Solution © UK Mathematics Trust, from the MOG 2015 solutions.