Singapore Mathematical Olympiad (SMO)

Lemma: Suppose $p$ is prime and $a_1, \dots, a_p$ are primes forming an A.P. with common difference $d$. If $a_1 > p$, we claim that $p \mid d$.

Proof: Since $p$ is prime and every $a_i$ is a prime $> p$, $p$ does not divide $a_i$ for any $i$. By the pigeonhole principle, there exist $1 \le i < j \le p$ so that $a_i \equiv a_j \pmod{p}$. Now $a_j - a_i = (j-i)d$, and $p$ does not divide $j-i$. So $p$ must divide $d$.

Apply the Lemma to the sequences $a_1, \dots, a_k$ for $k = 2, 3, 5, 7, 11$ and $13$. Then all such $k$'s are factors of $d$. So $d > 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 > 30,000$.