Every prime number > 19 divides one plus the product of two smaller primes?  This is a part of my answer to  this question I think it deserves to be treated separately. 
 Conjecture Let $A$ be the set of all primes from $2$ to $p>19$. Let $q$ be the next prime after $p$. Then $q$ divides $rs+1$ for some $r,s\in A$. 
I wonder if this conjecture is already known. I checked it for all $p<692,000$. 
A reformulation of the conjecture is this (motivated by  Gjergji Zaimi's comment). Let $p > 19$ be prime. Let $A$ be the set of primes $< p$ considered as a subset of the cyclic multiplicative group $\mathbb{Z}/p\mathbb{Z}^*$. Then the product $A\cdot A$ contains $-1$. 
It is interesting to know how large $A\cdot A$ is. This seems to be related to Freiman-type results of Green, Tao and others. Also as Timothy Foo pointed out, perhaps Vinogradov's method of trigonometric sums can apply. 
 A: This answer is a heuristic along the lines of Joro's.
We use $p,q,r$ to denote primes.  Let $S(p,a)$ denote the number of pairs of primes $(q,r)$ with $q,r\leq p$ and $p|(qr+a)$.  We are interested in the case $a=1$, but in general by the orthogonality relations of the characters we have $$ S(p,a)=\frac{1}{\phi(p)}\sum_{r\leq p}\sum_{q\leq p}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\chi\left(qr\right).\ \ \ \ \ \ \ \ \ \ (1)$$   Rearranging this is $$S(p,a)=\frac{1}{p-1}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\left(\sum_{q\leq p}\chi\left(q\right)\right)^{2}.$$
We might hope, as is the often the case, that the sums are all very small except when $\chi$ is principal, and that only the principal character contributes.  With this in mind we expect
$$S(p,a)\approx \frac{1}{p} \text{li}(p)^2.$$ 
This is the same as conjecturing that $S(p,a)$ does not vary largely between $a$.  In particular, if we average over all $a$ modulo $p$, then using (1) along with the orthogonality relation $\sum_{a\text{ mod } p}\sum_{\chi\text{ mod } p}\chi (a)=\phi(p)$, we see that $$\frac{1}{\phi(p)}\sum_{a\text{ mod } p} S(p,a)=\frac{1}{p-1}\sum_{r\leq p}\sum_{q\leq p}1=\frac{1}{p}\pi(p)^2\sim \frac{1}{p}\text{li}(p)^2.$$  
Numerically this is remarkably close for $a=1$.  Using the calculation done in Joro'sanswer, letting $a=1$ and $p=1000003$ we have $$S(p,1)=6184$$ whereas $$\frac{1}{p} \text{li}(p)^2=6182.307\dots $$
Now all that remains is to understand the sum $$\sum_{q\leq p}\chi\left(q\right)$$ for a character modulo $p$.  However, I believe this is very difficult.  
A: A pari/gp program verified the conjecture to $10^9$ in about 40 minutes.
On naiive probabilistic grounds I would expect the number of solutions to be about $\frac{p}{(\log{p})^2}$.
For $p=1000003$ got 6184 solutions and the expectation was 5239.
Here is the pari program:
{
inv1(p)=
local(q,a);
forprime(q=2,p-1,
a=lift(Mod(-1,p)/q);
if(isprime(a),return(1););
);
return(0);
}
default(primelimit,10^10)

forprime(p=23,10^9,a=inv1(p);if(a==0,print("+++",p);break; );/*print(p)*/)

A: Perhaps this might be another perspective on this problem. In an answer to a question I had previously asked on Math Overflow, "A generalized Möbius function?", the following paper of Addison was cited (which I simply copy from that answer):
A Note on the Compositeness of Numbers, A. W. Addison, Proceedings of the American Mathematical Society, Vol. 8, No. 1 (Feb., 1957), pp. 151-154
In this paper, it is proven that if one divides the integers into $q$ classes according to whether $\Omega(n)$ is $0,1,\dots,q-1 \bmod q$, $q>2$ then the function $C_{q,i}(x)$ which counts integers less than $x$ with $\Omega(n) \equiv i \bmod q$ satisfies
$$
C_{q,i}(x) - \frac{x}{q} = \Omega_{\pm}\left(\frac{x}{(\log x)^r}\right)
$$
where $r = 1-\cos(2\pi/q)$. (Here the variables $q$ and $r$ are taken from the paper and mean different things from elsewhere in this page.)
Let's assume that the relative frequencies of $\Omega(n) \bmod q$ should not differ much whether we consider $n\in [1,p^2]$ or $n\in (p\mathbb{Z}-1)\bigcap [1,p^2]$. Then we take $x$ to be about $p^2$ and $q$ to be about 
$$
f(p)=\max_{n \in (p\mathbb{Z}-1)\bigcap [1,p^2]}\Omega(n).
$$ 
Then a necessary (but not sufficient) condition for the conjecture is that $C_{f(p),2}(p^2)\geq 1$. I'm not really sure if one can take $x$ and $q$ in this relative range, but if so, then one can't even get a necessary condition from this because, using $1-\cos x \approx x^2/2$ for small $x$, we have 
$$
f(p) \gg (\log p)^{1-\cos(2\pi/f(p))}.
$$
