This is a part of my answer to  [this question](https://mathoverflow.net/questions/84310/generalizing-euclids-proof-of-the-infinity-of-primes/84342#84342) 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. 



Every prime number > 19 divides one plus the product of two smaller primes? 
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. 


