Prove that $n^2+n+41$ is prime for $n<40$ Here's a problem that showed up on an exam I took, I'm interested in seeing if there are other ways to approach it.

Let $n\in\{0,1,...,39\}$. Prove that $n^2+n+41$ is prime. 

I shall provide my own solution, though I am curious does anyone know how to do this without using PIDs?

Below is problem $\rm 6\ (B3)$ from IMO $1987$ and its solution (from AoPS, or Scholes)

Theorem. If $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le \sqrt\frac{n}{3}$, then $k^2+k+n$ is prime for all integers $0\le k\le n-2$.
Proof. First observe that if $m$ is relatively prime to $b+1$, $b+2$, $\cdots$, $2b$, then $m$ is relatively prime to any number less than $2b$. Indeed if $c\leq b$, then we can choose some $i$ to make $2^ic$ lies in range $b+1,b+2,\cdots,2b$, so $2^ic$ is relatively prime to $m$. Hence $c$ is also a prime. If we also have $(2b+1)^2>m$, then we can conclude that $m$ is a prime, otherwise there must be a factor of $m$ less than $\sqrt{m}$.
Let $n=3r^2+h$ where $0\leq h<6r+3$, so $r$ is the greatest integer less than or equal to $\sqrt{n/3}$. (to see this, just let $r=\lfloor\sqrt{n/3}\rfloor$, then we can write $n=3(r+\epsilon)^2(0\leq\epsilon< 1)$, so $h=6r\epsilon+3\epsilon^2\leq 6r+3$).
Assume that $n+k(k+1)$ is prime for $k=1,2,3\cdots,r$. We show that $N=n+(r+s)(r+s+1)$ is prime for $s=0,1,2,\cdots,n-r-2$. By our observation above, it is sufficient to show that $(2s+2r+t)^2>N$ and $N$ is relatively prime to all of $r+s+1,r+s+2,\cdots,2r+2s$. We have $(2r+2s+1)^2=4r^2+4s^2+8rs+4r+4s+1$. Since $s,r\ge1$, we have $4s+1>s+2$, $4s^2>s^2$ and $6rs>3r$. Hence $$(2s+2r+1)^2>4r^2+2rs+s^2+7r+s+2=3r^2+6r+2+(r+s)(r+s+1)\ge N.$$ Now if $N$ has a factor which divides $2r-i$ int the range $-2s$ to $r-s-1$, then so does $N-(i+2s+1)(2r-i)=n+(r-i-s-1)(r-i-s)$ which have the form $n+s'(s'+1)$ with $s'$ in range $0$ to $r$.

