Dutch Mathematical Olympiad

Suppose by contradiction that $n$ is not prime. Now consider the greatest divisor $d<n$ of $n$. Then we can write $n$ as $de$. Since $n$ is not prime, we have $d>1$ and hence also $e<n$. Now $e$ must satisfy $e>1$ and $e\le d$ (because $d$ is the greatest divisor satisfying $d<n$). Now $d+1$ must be a divisor of $n+1$. Moreover, $d+1$ is a divisor of $(d+1)e=de+e=n+e$. This means that $d+1$ must also be a divisor of the difference $n+e-(n+1)=e-1$. This, however, is impossible, because $e-1$ is a number between 1 and $d-1$. Therefore, our assumption that $n$ is not prime must be false, and $n$ must actually be a prime number. $\square$