I found the following problem on the internet, and my initial intuition turned out to be entirely incorrect. The question asked what is the smallest prime $r$ that does not have a representation of the form $$\frac{pq + 1}{p+q},$$ where $p,q$ are distinct primes. One approach to the problem is as follows. Suppose $r$ admits such a representation, then we must have $$pq + 1 = r(p+q),$$ which is equivalent to $$(p-r)(q-r) = (r-1)(r+1).$$ The problem is that the right hand side tends to be highly composite (indeed, if $r > 3$ then the right hand side is always divisible by $24$), so there should be lots of choices for the primes $p,q$ that appear on the left hand side.

Are there infinitely many primes $r$ which admits this representation? Are there infinitely many primes which do not have such a representation? If so, can one give an explicit infinitely family for either situation?

  • 1
    $\begingroup$ $(p,q,r)=(p,p+2,(p+1)/2)$ is always an integral solution, but of course, not always prime numbers. $\endgroup$ Commented Feb 20, 2015 at 16:33
  • 3
    $\begingroup$ @DietrichBurde In fact, never primes for $p > 5$, because one of $p, p+2, (p+1)/2$ is always divisible by $3$. $\endgroup$ Commented Feb 20, 2015 at 16:43
  • $\begingroup$ The answer is $73$. $\endgroup$
    – Lucian
    Commented Feb 20, 2015 at 18:04
  • $\begingroup$ @Lucian Why is 73? $\endgroup$ Commented Feb 21, 2015 at 12:13
  • $\begingroup$ $73=72+1=3\cdot24+1$ $\endgroup$
    – Lucian
    Commented Feb 21, 2015 at 12:17

1 Answer 1


$73$ really is the smallest prime $r$ which cannot be represented by means of \begin{equation*} \frac{pq+1}{p+q} \end{equation*}

because as you noticed before, \begin{equation*} \frac{pq+1}{p+q}=r \end{equation*} \begin{equation*} pq+1=r\left(p+q\right) \end{equation*} \begin{equation*} pq+1=pr+qr \end{equation*} you may add $r^{2}$ on both sides, \begin{equation*} pq+1+r^{2}=pr+qr+r^{2} \end{equation*} \begin{equation*} pq-pr-qr+r^{2}=r^{2}-1 \end{equation*} \begin{equation*} \left(p-r\right)\left(q-r\right)=\left(r-1\right)\left(r+1\right) \end{equation*} is highly composite on right side; anyway making $r=73$ \begin{equation*} \left(p-73\right)\left(q-73\right)=\left(73-1\right)\left(73+1\right) \end{equation*} \begin{equation*} \left(p-73\right)\left(q-73\right)=72\cdot74 \end{equation*} \begin{equation*} \left(p-73\right)\left(q-73\right)=5328 \end{equation*} so $\left(p-73\right)$ and $\left(q-73\right)$ are divisors of $5328$, which possibly are \begin{equation*} \{1,\;2,\;3,\;4,\;6,\;8,\;9,\;12,\;16,\;18,\;24,\;36,\;37,\;48,\;72,\;74,\;111,\;144,\; \end{equation*} \begin{equation*} 148,\;222,\;296,\;333,\;444,\;592,\;666,\;888,\;1332,\;1776,\;2664,\;5328\} \end{equation*} but the only prime values of $p$ such that $p-73$ is a divisor of $5328$ are \begin{equation*} p\in\{79,\;89,\;97,\;109,\;739\} \end{equation*} then, \begin{equation*} \left(p-73\right)\in\{6,\;16,\;24,\;36,\;666\} \end{equation*} with these values, $q$ cannot be prime because, \begin{equation*} \left(q-73\right)\in\{888,\;333,\;222,\;148,\;8\} \end{equation*} \begin{equation*} q\in\{961,\;406,\;295,\;221,\;81\} \end{equation*} none of them is prime.

On the other hand, here are some representations for primes $r$ up to $97$, except for $73$ \begin{equation*} \left(p,q,r\right)\in\{\left(3,5,2\right),\left(5,7,3\right),\left(7,17,5\right),\left(11,19,7\right),\left(13,71,11\right),\left(19,41,13\right),\left(29,41,17\right),\left(23,109,19\right),\left(31,89,23\right),\left(31,449,29\right),\left(37,191,31\right),\left(41,379,37\right),\left(43,881,41\right),\left(71,109,43\right),\left(71,139,47\right),\left(59,521,53\right),\left(71,349,59\right),\left(71,433,61\right),\left(89,271,67\right),\left(73,2591,71\right),\left(131,199,79\right),\left(89,1231,83\right),\left(113,419,89\right),\left(109,881,97\right)\} \end{equation*}

and about the infinity of such numbers which cannot be represented, I strongly believe they are infinite, since I found others like $73$: \begin{equation*} \{73,\;107,\;131,\;157,\;173,\;179,\;193,\;227,\;263,\;277,\;283,\;313,\;317,\;331,\;367,\;383,\;389,\;457,\;499,\;503,\;509,\;523,\;557,\;563,\;653,\;673,\;677,\;691,\;761,\;787,\;823,\;829,\;877,\;887,\;947,\;983,\;997,\;\dots\} \end{equation*}

I tested those with all combinations of primes $p<10^{6}$ and $q<10^{6}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .