Challenge Level

$$\begin{split}pq+1&=p(p+2)+1\\

&=p^2+2p+1\\

&=(p+1)^2\end{split}$$ $p$ is odd so $p+1$ is even

$p,q\gt 3$ so

$$\text{not multiples of 3}\\

\begin{align} &\downarrow & &\downarrow\\

&p &p+1\hspace{5mm} &q\\

& &\uparrow\hspace{10mm}& \end{align}\\

\text{a multiple of 3}\\

\text{(since 1 in every 3 numbers is a multiple of 3)}$$ So $p+1$ is a multiple of $2$ and $3$

$\therefore p+1$ is a multiple of $6$

$\therefore (p+1)^2$ is a multiple of $36$, and $(p+1)^2=pq+1$

Let $k=p+1$. We note that $k$ is even because any prime $p>3$ is odd.

Moreover, neither $p$ nor $q$ can be divisble by three because the only prime number divisible by three is $3$ itself. On the other hand, if you have three consecutive integers exactly one of them must be divisible by three. Thus, $k$ is also a multiple of $3$.

So, we can write $k$ in the form $k=6n$ for some integer $n$. We deduce further that

$$pq = (6n-1)(6n+1) = 36n^2-1$$

which implies that $pq+1 = 36n^2$ is indeed divisible by $36$.

This problem is taken from the UKMT Mathematical Challenges.

You can find more short problems, arranged by curriculum topic, in our short problems collection.