A surprising conjecture about twin primes

Question

Just for fun, I began to play with numbers of two distinct ciphers. I noticed that most of the cases if you consider the numbers $AB$ and $BA$ (written in base $10$), these have few common divisors: for example $13$ and $31$ are coprime, $47$ and $74$ are coprime. Obviously this is not always the case, because one can take non-coprime ciphers, however I realized that, for $0 \le a<b \le 9$, the quantity $$\gcd (10a+b, 10b+a)$$ is never too big. Using brute force I computed $$\max \{ \gcd (10a+b, 10b+a) : 0 \le a<b \le 9\} = \gcd (48,84)=12$$

After that, I passed to an arbitrary base $n \ge 2$, and considered $$f(n)= \max \{ \gcd (an+b, bn+a) : 0 \le a<b \le n-1 \}$$ For example $f(2)=1$ and $f(3)=2$.

Considering $n \ge 4$, I noticed that, picking $a=2, b=n-3$ we have $$2n+(n-3) = 3(n-1)$$ $$(n-3)n+2 = (n-2)(n-1)$$ so that $f(n)$ has a trivial lower bound $$(n-1) \le \gcd (2n+(n-3), (n-3)n+2) \le f(n) $$ (which holds for $n=2,3$ as well).

A second remark is $$\gcd (0n+b, bn+0) = b \le n-1$$ so that we can restrict ourselves to the case $a \neq 0$: in other words $$f(n)=\max \{ \gcd (an+b, bn+a) : 1 \le a<b \le n-1 \}$$

I wrote a very simple program which computes the value of $f(n)$ for $n \le 400$, selecting those numbers such that $f(n)=n-1$. Surprisingly, I found out that many numbers appeared: $$4, 6, 12, 18, 30, 42, 60, 72, 102, 108, 138, 150, 180, 192, 198, 228, 240, 270, 282, 312, 348$$

More surprisingly these turned out to be the numbers between couples of twin primes! What is going on here?

Answer 1

Suppose $n-1$ and $n+1$ are both primes.

$\gcd(an+b,bn+a)$ divides $an+b - (bn+a) = (a-b)(n-1)$.

There are two cases. If $n-1$ divides $\gcd(an+b,bn+a)$ then $b=n-1-a$ so $an+b= (n-1) (a+1)$ and $bn+a=(n-1)(b+1)$, so $\gcd(an+b,bn+a) = (n-1)\gcd(a+1,b+1)$.

$(a+1)+(b+1)=n+1$. Because $n+1$ is prime, two numbers that sum to it must be relatively prime (any common prime factor would be a prime factor of $n+1$, so woul be $n+1$, but $a+1$ and $b+1$ are both less than $n+1$.) So in this case $\gcd(an+b,bn+a) = n-1$.

On the other hand, because $n-1$ is prime, if $n-1$ does not divide $\gcd(an+b,bn+a)$ then $\gcd(an+b,bn+a)$ divides $a-b$ and so is at most $n-2$.

So in this case the maximum value is $n-1$, attained whenever $a+b=n-1$.

If $n+1$ is not prime you can get greater than $n-1$ in the first case by taking a prime $\ell$ dividing $n+1$, setting $a=\ell-1$, $b=n-\ell$ for a gcd of $\ell (n-1)$.

If $n-1$ is not prime but instead $n-1= cd$ with $c \leq d$, you can set $a=d+1$, $b=(c-1)(d+1) \leq cd <n$ so that $an+b= (d+1) (cd+1) + (c-1)(d+1) = c d^2 +2cd + c= c(d+1)^2$ and $(b-a)(n-1)=(c-2) (d+1) cd$ are both divisible by $c (d+1) > n-1$, so the gcd is divisible by $c(d+1)$ and hence greater than $n-1$.