The Computer Laboratory

Practice Paper 1 Question 15

Does \(30\) divide \(n^5-n\) for all positive integers \(n\)?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. Factorise \(n^2-2n-3\).
  2. Is \(n^2+n\) always even when \(n\) is an integer?
  3. Does \(6\) divide \(100002\)? Try to reason about the divisors of both numbers.

Hints

  • Hint 1
    How do you split \(30\) into a product of prime factors?
  • Hint 2
    Can you factorise \(n^5 - n\)?
  • Hint 3
    You should obtain \(n(n-1)(n+1)(n^2+1)\). What can you say about the product of 3 consecutive numbers in terms of divisibility by \(2\) and \(3\)?
  • Hint 4
    If you assume that \(5\) divides \(n^5-n\), how can you prove that 5 divides \((n+1)^5-(n+1)\)?

Solution

First notice that \(30=2\cdot3\cdot5\). Since \(2\), \(3\) and \(5\) are all coprime we will prove that each of them divides \(n^5-n\) and hence conclude that their product does too. We now factorise \(n^5-n\): \[ \begin{align} n^5-n &= n(n^4-1) \\ &= n(n^2-1)(n^2+1)\\ &= n(n-1)(n+1)(n^2+1) \end{align} \] The product \((n-1)n(n+1)\) is of 3 consecutive numbers, hence necessarily both 2 and 3 must divide it. We must now prove divisibility by \(5\). There are several approaches to do this, but here we shall use induction. It's easy to verify the base case for \(n=0\) or \(n=1\). Then do the inductive step: \[ \begin{align} (n+1)^5 - (n+1) &= n^5 + 5n^4 + 10n^3 + 10n^2 + 5n - n \\ &= n^5-n + 5(n^4+2n^3+2n^2+n) \end{align} \] First part is divisible by \(5\) owing to the induction hypothesis, while the rest is obviously a multiple of 5.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.