# Twin primes and divisibility

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.

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

• 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 :-) Feb 7, 2021 at 12:28
• I posted my answer, just for the sake of having an alternative approach. Will accept yours eventually. Feb 7, 2021 at 19:26

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