Key idea. Factor the polynomial and isolate the case in which a factor is 1.

1. Try a factor \(n^2+n+1\). Dividing \(n^5+n+1\) by it starts with \(n^3\), then \(-n^2\), then 1, and gives

   \[n^5+n+1=(n^2+n+1)(n^3-n^2+1).\]

2. You can check the identity by multiplying the brackets: the coefficients of \(n^4,n^3,n^2\) cancel, leaving \(n^5+n+1\).

3. If \(n=1\), the expression equals 3, which is prime.

4. If \(n\ge2\), then \(n^2+n+1\ge7\) and

   \[n^3-n^2+1=n^2(n-1)+1\ge5.\]

   Both factors exceed 1, so the expression is composite. These cases cover every positive integer n.

Remember. A polynomial factorisation turns a primality problem into a check of small exceptional cases.