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$ – Dietrich Burde Feb 20 '15 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$ – Robert Israel Feb 20 '15 at 16:43
  • $\begingroup$ The answer is $73$. $\endgroup$ – Lucian Feb 20 '15 at 18:04
  • $\begingroup$ @Lucian Why is 73? $\endgroup$ – Konstantinos Gaitanas Feb 21 '15 at 12:13
  • $\begingroup$ $73=72+1=3\cdot24+1$ $\endgroup$ – Lucian Feb 21 '15 at 12:17

$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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.