Prime time .....

The following is a test one can use to see if a prime $r$ can be written in this way.

Look at the divisors $k$ of $r^{2} - 1$ that are less than $r$ and then find $j$ such that $r^{2} - 1 = kj$ .

Then the prime $r$ can be written in the desired way if and only if both $r + k$ and $r + j$ are both prime for some pair $k, j$ . (Insert proof here .... sometime). We will then have $p = r + k$ and $q = r + j$ such that

$\dfrac{pq + 1}{p + q} = \dfrac{r^{2} + r(k + j) + kj + 1}{2r + k + j} = \dfrac{2r^{2} + r(k + j)}{2r + k + j} = r$ .

So, for $r = 71$ we have $r^{2} - 1 = 5040 = 2^{4} * 3^{2} * 5 * 7$ .

The divisors $k \lt 71$ for which $71 + k$ is prime are $2, 8, 12, 18, 30, 36, 42, 56$ and $60$ . The respective values of $j$ are $2520, 630, 420, 280, 168, 140, 120, 90$ and $84$ .

Now of these we have that $71 + j$ is prime for $j = 2520, 630, 420, 168, 140$ and $120$ . So we have a choice of $p,q$ in the case of $r = 71$ . For example, with $k = 42$ and $j = 120$ we have primes $p = 113$ and $q = 191$ .

We can go through this process for all primes less than $71$ as well and successfully find suitable values for $p$ and $q$ . However, for $r = 73$ , we find no such primes $p,q$ , and so $\boxed{73}$ is the smallest prime that cannot be written in the desired way.

Note: Testing all the primes this way is a bit tedious; a computer program might be of use here. If anyone has a more elegant way of showing that $73$ is the answer then I would be interested to see your method.

I have no formal proof either, but a little shortcut for programatically testing:

WLOG $p < q$ .

Then $\frac{p}{2} = \frac{pq}{2q} < \frac{pq}{p+q} < \frac{pq+1}{p+q} = p + \frac{1-p^2}{p+q} < p$ . So for the given prime $r=\frac{pq+1}{p+q}$ we have to check whether there is a prime $q=\frac{pr-1}{p+r}$ for any $p$ satisfying $r<p<2r$ .

No proof here, but I solved this by writing a program that uses the first 94 primes as variables p and q in the equation. Any prime that came up as a result of the equation was eliminated. 73 came up as the smallest remaining prime after this process of elimination. (Originally I had tried my program with just the first 20 primes and gotten 37 as a result, but it turns out 41 and 379 [the 75th prime] can be used as p and q to get 37, so I kept increasing the list of primes.) Not an elegant proof, but a solution nonetheless.

I'm very interesting in seeing a mathematical proof of this equation.