18
$\begingroup$

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 olds 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?

$\endgroup$
  • 4
    $\begingroup$ @scaaahu At what point does the OP claim it is? $\endgroup$ – Wojowu Dec 22 '16 at 12:11
  • 1
    $\begingroup$ They never claim it always holds. They even give an example of $48,84$. $\endgroup$ – Wojowu Dec 22 '16 at 12:13
  • 2
    $\begingroup$ Actually, you are right. I ran a computation and 21 pairs are coprime, 24 pairs are not coprime. So the first line isn't really correct. This doesn't invalidate the question though. $\endgroup$ – Wojowu Dec 22 '16 at 12:20
  • 15
    $\begingroup$ @scaaahu Sometimes it helps to move past the first line of the question to the second line ("Obviously this is not always the case") or, if you're feeling bold, even the third line where OP considers the GCD of pairs. Your comment is at best an irrelevant nitpick. $\endgroup$ – Paul Siegel Dec 22 '16 at 12:21
  • 1
    $\begingroup$ Is your sequence in oeis.org yet? If not, add it. I'm sure Neil Sloane would like it. $\endgroup$ – Pat Devlin Dec 23 '16 at 1:09
24
$\begingroup$

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

$\endgroup$

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.