current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 11 down vote favorite
5

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?

share|cite|improve this question
    
12 and 21 are not coprime. – scaaahu 18 hours ago
1  
@scaaahu At what point does the OP claim it is? – Wojowu 18 hours ago
    
He said in most of the cases. The first one I consider breaks. – scaaahu 18 hours ago
1  
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. – Wojowu 17 hours ago
10  
@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. – Paul Siegel 17 hours ago
up vote 19 down vote accepted

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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