# The max Greatest Common Divisor of 2 digit decimal numbers

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.

• You should mention that $a$ and $b$ can't be equal. (Otherwise $a=b=9$ gives a GCD of $99$.) – TonyK Jul 30 '19 at 9:34
• Shouldn't your $35$ be $36$? – TonyK Jul 30 '19 at 9:36
• @TonyK Yes, 1+2+3+..+8 should be 36. I fixed it. – Popeye Jul 30 '19 at 9:40

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.

• Thanks. I cannot 100% understand all the steps. But the answer is $48$ and $84$, which $gcd(\overline{ab}, \overline{ba})$ is $12$. – Popeye Jul 30 '19 at 13:32
• The mistake comes in the 2nd last sentence – $3\gcd(a,b)<9$ is wrong. – Gerry Myerson Jul 30 '19 at 13:36
• I don't understand how can $\gcd(a,b)\mid D\mid \gcd(9,a+b)\gcd(a,b).$ be obtained from $3,4,5.$？ – Popeye Jul 31 '19 at 6:03

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.