Twin primes and divisibility

Question

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

Answer 1

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

Answer 2

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