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)?
 A: Case 1: $n$ is positive.
Let $p$ be the least prime number greater than $(n+1)!+1$. As there are infinitely many primes, such a $p$ certainly exists. Note that the $n$ numbers
$$
(n+1)!+2,(n+1)!+3,\dots,(n+1)!+(n+1)
$$
are all composite. Thus $p>(n+1)!+(n+1)$, and so $p > p-n>(n+1)!+1$. As there are no prime numbers in this interval, $p-n$ is composite.
Case 2: $n$ is negative.
If $2-n$ is composite, take $p=2$. Otherwise, take $p=2-n$.
A: 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$).
A: Let $n\neq 0$ and $q>n$ be prime. Consider $x=q-n$, now if $n$ be an odd integer, then $q-n$ is even and so $x$ is composite number. Now let $n$ an even integer. then $n=q-x$ now if $\gcd(x,q)= 1, q$, since $x\neq q$ so if $\gcd(x,q)=q$ then $q|x$ i.e., $x$ is composite number, so let $\gcd(x,q)=1$, then there is integers $r ,s$ such that $rx+sq=1$ and so $(ns-1)q=(-nr-1)x$ now if is a prime then $ns-1=x$ and $q=-nr-1$, therefore $$n=-nr-1-ns+1=n(-r-s);$$
$$-r-s=1\rightarrow r=1-s \rightarrow s(q-x)=1 \rightarrow s=1, r=0$$
where this implies that $q=1$, but $q$ is prime, thus $x$ can not be a prime and proof is done.
