Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Assume $a$ and $b$ are different one digit positive integer, both within range $[1,9]$. Then what is the possible maximum Greatest Common Divisor of two digits numbers $\overline{ab} ,\overline{ba}.$ ( $\overline{ab}$ means $a$ is the tens digit, $b$ is the ones digit. So $\overline{ab}=10a+b$).
A iterative way to iterate through $1-9$ of $a,b$ for 36 times can find the answer, I want to know any better mathematical way to solve the question. Thanks.
Let $D=\gcd(\overline{ab},\overline{ba})$. We have $$\tag1 D\mid \overline{ab}-\overline{ba}=9(a-b),$$ $$\tag2 D\mid a\cdot \overline{ba}-b\cdot \overline{ab}=a^2-b^2=(a+b)(a-b),$$ $$\tag3 D\mid 10\cdot\overline{ab}-\overline{ba}=99a.$$ $$\tag4 D\mid 10\cdot\overline{ba}-\overline{ab}=99b,$$ $$\tag5 D\mid \overline{ab}+\overline{ba}=11(a+b).$$ From $(1)$, $D$ cannot be difvisible by any prime $>7$ (provided $a\ne b$), hence we can cast out $11$ in $(3)$, $(4)$, $(5)$, and combine these into $$\gcd(a,b)\mid D\mid \gcd(9,a+b)\gcd(a,b). $$ Also from $(5)$, $D<18$ and in particular $27\nmid D$. Then the power of $3$ occuring in $D$ is the same as that in $a+b$ (by the digit sum rules for divisibility by $3$ and $9$). We conclude $$ D=\frac{\gcd(a,b)\gcd(a+b,9)}{\gcd(a,b,9)}.$$
In order to maximize, we can make $a+b$ a multiple of $9$ only by making $a+b=9$. Then $\gcd(a,b)\mid 9$ and $D=\gcd(a+b,9)=9$. Or we can make $a+b$ a multiple of $3$, but $3\nmid a,b$. Then $D=3\gcd(a,b)<9$. So the maximal gcd is $9$ and happens with $18$ and $81$, $27$ and $72$, etc.
Let a prime number $p \mid \overline{ab}=(10a+b)$ and $ p \mid \overline{ba}=(10b+a)$. Then $$\tag1 p\mid \overline{ab}-\overline{ba}=9(a-b),$$ So either $p \mid 9$ or $p \mid (a-b)$. And $a-b\leq8$. So $$\tag2 p=3,2,5,7.$$ For $p\neq3$, $p\mid (a-b).$ $$p\mid(a-b)+(10a+b)=11a.$$ And because of $(2)$, $$\tag3 p\mid a$$ $$\tag4 p\mid a-(a-b)=b$$ Since $a$ and $b$ are distinct numbers and with the range $[1,9]$, It is impossible to get both $p\mid a$ and $p\mid b$ when $p=5$ and $p=7$. So $$\tag5 p=2,3.$$ And $$\tag6 g = \gcd(\overline{ab},\overline{ba}) \textrm{ must be the product of the powers of } 2 \textrm{ and } 3\ .$$
$$\tag7 g\mid \overline{ab}+\overline{ba}=11(a+b).$$ Because of $(6)$, $$\tag8 g\mid (a+b)\leq 17$$ Because of $(6)$, the max values of $g$ are $16$,$12$. For $16$, $$\gcd(97,79)=1 .$$ For $12$, $$\gcd(39,93)=3$$ $$\gcd(48,84)=12$$ $$\gcd(57,75)=3$$
So the answer is $$a=8,b=4,\textrm{ which yields } \gcd(48,84)=12.$$ The solution is refined based on the solution here.
