2
$\begingroup$

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.

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

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.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks. I cannot 100% understand all the steps. But the answer is $48$ and $84$, which $gcd(\overline{ab}, \overline{ba})$ is $12$. $\endgroup$ – Popeye Jul 30 '19 at 13:32
  • $\begingroup$ The mistake comes in the 2nd last sentence – $3\gcd(a,b)<9$ is wrong. $\endgroup$ – Gerry Myerson Jul 30 '19 at 13:36
  • $\begingroup$ 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.$? $\endgroup$ – Popeye Jul 31 '19 at 6:03
0
$\begingroup$

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.

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