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.

immediately. In the latter case because one has a binary problem instead of one with three variables, and in the former because I think you can have both $A.A \subsetneq Z/pZ^*$ and $A + A^{-1} \subsetneq Z/pZ$ with $A$ reasonably large, even positive density. But both of these are good ideas on which to base further thought. – Ben Green Dec 27 '11 at 12:48