6
$\begingroup$

Let $p$ and $q$ be a pair of twin primes. Find the smallest possible value of $a+b$ where $a$ and $b$ are positive integers such that $p\;|\;(a+qb)$ and $q\;|\;(a+pb)$.


This puzzle is my own invention, a more difficult version of a problem I found elsewhere.

$\endgroup$

2 Answers 2

7
$\begingroup$

(After I saw Rand's solution, it seemed to me that there ought to be a way of streamlining mine a bit. So I've done that. The original version of mine is preserved below in case anyone feels that the improved one is "polluted" by my having seen OP's own answer.)

The smallest possible $a+b$ is

$\frac{5(p+q)}4-2$.

First of all, notice that

$a=-(p+q)b$ has the right divisibility properties. Any other choice of $a$ will satisfy them if, and only if, it differs from this number by something that's a multiple of $p$ (to get the first property right) and also of $q$ (to get the second property right); that is, by a multiple of $pq$. Hence, given a choice of $b$, $a$ is good iff $a=mpq-(p+q)b$ for some integer $m$.

Let's

write $p=2t-1,q=2t+1$; here $t$ is an integer since twin primes are always odd. Our criterion now takes the form $a=(4t^2-1)m-4tb$. Noting that our minimal choice of $m$ to make this positive increases (at least for smallish $b$) when $b$ crosses a multiple of $t$, we write $b=kt-l$ with $0<l\leqt$, so now $a=(4t^2-1)m-4t^2k+4tl=4t^2(m-k)+(4tl-m)$. The second term is always smaller than $4t^2$, so we must have $m\geq k$; if we take $m=k$ then the second term is positive unless $k\geq4t$ which we shall see can't be the case when $a+b$ is minimal. So to minimize $a+b$ we will take $m=k$, and then $a=4tl-k$. (By way of reminder, $b=kt-l$.)

Now

$a+b=(4tl-k)+(kt-l)=(4t-1)l+(t-1)k$, which is smallest when $k,l$ are as small as possible, namely 1; so $k=l=m=1$ and we have $a=4t-1,b=t-1,a+b=5t-2$.

There is one loose end:

I claimed that we can't have $k\geq4t$ for a best-possible choice of $a,b$. Well, if $k\geq4t$ then $a+b>b=kt-l\geq4t^2-t$ and therefore $a+b>4t^2-t$. Thte solution above has $a+b=5t-2$; and $4t^2-t>5t-2$ is equivalent to $4t^2-6t+2>0$ or $2(2t-1)(t-1)>0$, which is true because the smallest possible value of $t$ is $2$, making both those factors positive.


Original solution

First of all, notice that

$a=-(p+q)b$ has the right divisibility properties. Any other choice of $a$ will satisfy them if, and only if, it differs from this number by something that's a multiple of $p$ (to get the first property right) and also of $q$ (to get the second property right); that is, by a multiple of $pq$. Hence, given a choice of $b$, $a$ is good iff $a=mpq-(p+q)b$ for some integer $m$; and if we choose $a$ to minimize $a+b$ (given our choice of $b$), this means taking $m$ as small as possible while making $a$ positive, which means $m=\left\lfloor\frac{(p+q)b}{pq}\right\rfloor+1$. (Another way to say this: $a$ is the distance from $(p+q)b$ to the next strictly larger multiple of $pq$.) So $a+b=\left(\left\lfloor\frac{(p+q)b}{pq}\right\rfloor+1\right)pq-(p+q-1)b$, which decreases when we increase $b$ unless the thing inside $\lceil\cdots\rceil$ reaches or crosses an integer.

Now

write $p=2t-1,q=2t+1$; then $p+q=4t$ and $pq=4t^2-1$. So $\frac{(p+q)b}{pq}=\frac{4tb}{4t^2-1}=\frac bt+\frac{b}{(4t^2-1)t}$, and as long as $0<b<4t^2-1$ the floor of this is the same as that of $b/t$. As we'll see, the choice of $b$ we end up with makes $a+b<pq=4t^2-1$, so we can assume this is true. This means that in order to minimize $a+b$ we must take $b$ to be of the form $kt-1$, because otherwise we can always replace $b$ with $b+1$ without changing $m$, thus decreasing $a+b$. And then $\left\lfloor\frac{(p+q)b}{pq}\right\rfloor=k-1$, so $a+b=kpq-(p+q-1)(kt-1)=k(4t^2-1)-(4t-1)(kt-1)=(t-1)k+4t-1$, so we want to take $k$ as small as possible, namely 1.

So we end up with

$b=t-1=\frac{p+q}4-1$ and $a=pq-(p+q)b=pq-\left(\frac{p+q}4-1\right)(p+q)=p+q-\frac{(p-q)^2}4$ or, in terms of $t=\frac{p+1}2=\frac{q-1}2$, we have $b=t-1$ and $a=4t^2-1-4t(t-1)=4t-1$; and then $a+b=5t-2$ or, in terms of $p,q$, $a+b=\frac{5(p+q)}4-2$.

Note that as promised

$a+b<4t^2-1$, unless $5t-2\geq4t^2-1$ or equivalently $4t^2-5t+1\leq0$, or equivalently $(4t-1)(t-1)\leq0$, or equivalently $t$ lies between 1/4 and 1 inclusive. But $t=\frac{p+q}4$ so this would mean $p+q\leq4$, which never happens: the first pair of twin primes is {3,5} with $t=2$.

It might be worth working through a concrete example, so let's do that.

We'll take $p,q=11,13$ so $t=6$. We need $a=mpq-(p+q)b$ or, concretely, $a=143m-24b$. So e.g. if $b=1$ then we need to take $m\geq1$ (and so will take exactly $m=1$) leading to $a=119,b=1$; we can verify that $a+bq=119+13=132$ is a multiple of $p=11$ and that $a+bp=119+11=130$ is a multiple of $q=13$, as will always happen when we choose $a$ as directed above.
Now, if we successively take $b=1,2,3,4,5=t-1$ then the $24b$ term is, successively, $24,48,72,96,120$, all of which are still $<143$, so we can continue to use $m=1$ for all of these; and as we do so, the sum $a+b$ decreases each time. At $b=5=t-1$ we get $a=143-120=23$.
Double-checking our divisibility conditions, we need $11|23+5\cdot13=88$ and $13|23+5\cdot11=78$, both of which are true.
I'm claiming that this is not only the best we can do with $b<t$ but the absolute best. Let's see why.
Continuing to increase $b$, as soon as we reach $b=6=t$ we need a larger value of $m$, namely $m=2$; this choice of $m$ works for $b=t=6,7,8,9,10,11=2t-1$ and again the best of these is the last: $b=11,a=22$.
But comparing with the best in the $0\ldots5$ range, we see that $b$ is larger by $6$ and $a$ is smaller only by $1$. (In terms of the calculations above: increasing $b$ by $t$ increases $m$ by $1$, so $a$ changes by $pq-t(p+q)=4t^2-1-4t^2=-1$, and so $a+b$ increases by $t-1$.)
The same will happen again if we move on to the $b=2t=12\ldots17=3t-1$ range, and so on until we get to $b=142=pq-1$, which is considerably larger than the value of $a+b$ we have already obtained with $b=5$, namely $28$.

$\endgroup$
2
  • $\begingroup$ Correct answer, +1. I'll read through your full argument when I have time; I think my method is a bit shorter, but that might just be because I didn't write it up formally - maybe if it graduates from scribblings on scrap paper it'd be longer than I thought :-) $\endgroup$ Feb 7, 2021 at 12:28
  • $\begingroup$ I posted my answer, just for the sake of having an alternative approach. Will accept yours eventually. $\endgroup$ Feb 7, 2021 at 19:26
0
$\begingroup$

Gareth's answer is correct. Here's the proof I found before posting:

WLOG, since they're twin primes, say $q=p+2$. Then $p\;|\;(a+qb)$ and $q\;|\;(a+pb)$ means that $p\;|\;(a+2b)$ and $q\;|\;(a-2b)$; let's say $a-2b=k_1q$ and $a+2b=k_2p$. Then we have $$a=\frac{k_2p+k_1q}{2},\quad b=\frac{k_2p-k_1q}{4},$$ which means $k_2p>k_1q$ and $k_2p>-k_1q$, so $k_2>|k_1|$. We also observe, since $p,q$ are both odd and in different congruence classes modulo 4, that $k_1,k_2$ are congruent to one of $\{1,3\},\{3,1\},\{2,2\},\{0,0\}$ modulo 4. Given the above inequality, this means $k_2\geq k_1+2$ if $k_1$ is positive, and $k_2\geq|k_1|+4$ if $k_1$ is negative.

Now,

$k_2p>k_1q$ implies $a>k_1q$, so the best way to minimise $a$ should be by minimising $k_1$. We try $k_1=1$, therefore $k_2\geq3$. Putting $k_1=1,k_2=3$ gives $$a=\frac{3p+q}{2}=2p+1,\quad b=\frac{3p-q}{4}=\frac{p-1}{2},\quad a+b=\frac{5p+1}{2}.$$

Is this optimal?

We have $a+b=\frac{3}{4}k_2p+\frac{1}{4}k_1q$. If $k_1>1$, then $k_2>3$, and we've gone above the solution already found. If $k_1\leq0$, then $k_2\geq-k_1+4$, so $a+b\geq 3p-\frac{k_1}{4}(3p-q)\geq3p$ (for any twin primes $p,q$ we must have $3p>q$), and we've gone above the solution already found.

Therefore, yes, the solution found above is optimal, and the final answer is

$a+b=\frac{5p+1}{2}=\frac{5(p+q)-8}{4}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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