The integer $n$ is not zero if and only if there is some prime $p>n$ such that $p-n$ is composite I recently solved a problem (it was posed in a spanish-talking forum) in which I used the following lemma.

The integer $n$ is not zero if and only if there is a prime $p>n$ such that $p-n$ is composite.

This is my proof (I only write the "non-trivial" implication):

Let $n$ be a non-zero integer and let $p>|n|$ be a prime. Then there are integers $q$ and $r$ such that $$n=pq+r$$ and $0<r<p.$ It follows that if $p'>n+p$ is a prime of the form $p'=pk+r,$ $k\in\mathbb Z$ (its existence follows from Dirichlet's Theorem) then $$p'-n=pk+r-pq-r=p(k-q)$$ and since $k-q>1,$ $p'-n$ is a composite number (note that in fact there are infinitely many such primes). 

My question is, can that result be proved in a more elementary way (without appealing to Dirichlet's theorem)?

For any non-zero $n$, some arithmetic progression mod $n$ contains infinitely many primes (this doesn't require Dirichlet's theorem, only Euclid + pigeonhole).  But if $n$ is a counterexample, then the stated condition forces every (sufficiently large) term of that arithmetic progression to be simultaneously prime (this is especially true for $n<0$ where we don't even need to assume infinitely many primes in that progression, just one).  This is clearly impossible (for instance, pick any prime $q$ that doesn't divide $n$ and some of the terms of the progression will be divisible by $q$).
