What is $\gcd(12345,54321)$?
I noticed that after trying $\gcd(12,21),\gcd(123,321),$ and $\gcd(1234,4321)$ that they are all less then or equal to $3$. That leads me to question if there is an easy way to calculate such greatest common divisors.
$\endgroup$ 74 Answers
$\begingroup$When $54321$ is divided by $12345$, the quotient is $4$ and the remainder is $4941$: $$ 54321 = (4\times12345) + 4941. $$ Therefore (as Euclid taught us), $$ \gcd(12345,54321) = \gcd(12345,4941). $$ When $12345$ is divided by $4941$, the quotient is $2$ and the remainder is $2463$: $$ 12345 = (2\times4941) + 2463. $$ Therefore $$ \gcd(12345,4941) = \gcd(2463,4941). $$ And so on. Keep going until you're done. (The numbers keep getting smaller, so it can't go on forever.) And you'll find in this case it doesn't take much longer.
$\endgroup$ $\begingroup$Hint: Look at the sum of the digits of $12345$ and $54321$ , it's divisible by $3$. So $\ldots$
$\endgroup$ $\begingroup$In order to generalize this cleanly to values greater than $9$ digits, we should probably think of $54321$ as $\sum_{k=1}^n k\cdot 10^{k-1}$ for $n=5$, so when $n=11$ we get $120987654321$ instead of, say, $110987654321$.
Similarly for $12345$ can be generalized to $\sum_{k=1}^{n} (n-k+1) \cdot 10^{k-1}$. When $n=11$ this is $12345679011$, not $1234567891011$: we trade off the idea of "writing it backwards" for a lot greater algebraic simplicity.
The closed forms of these two sums are $\frac1{81} (9n\cdot 10^n - 10^n + 1)$ and $\frac1{81} (10^{n+1} - 9n - 10)$, respectively. So if we denote their GCD by $g$, then:
$$81g = (9n\cdot 10^n - 10^n + 1, 10^{n+1} - 9n - 10).$$
Let's try to bound this. The left term is not divisible by $10$: if we multiply it by $10$, then the gcd will increase by a factor of $(n,10)$, so
$$(n,10)\cdot81g = (9n\cdot 10^{n+1} - 10^{n+1} + 10, 10^{n+1} - 9n - 10) \\ = (9n\cdot 10^{n+1} - 10^{n+1} + 10 - (9n-1)\cdot(10^{n+1} - 9n - 10), 10^{n+1} - 9n - 10) \\ = (81n^2 + 81n, 10^{n+1} - 9n - 10).$$
So in particular $g \le n(n+1)/(n,10)$, which is reasonably small compared to the sizes of numbers here. Nevertheless, it does get much larger than $3$ or $9$ in practice: for $n=44$ it's as high as $99$, and for $n=110$ it's $1221$, just meeting the upper bound!
I think you might be able to reduce the GCD expression further using binomial expansion on $(1+9)^{n+1}$, but it gets kind of hairy.
$\endgroup$ $\begingroup$$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ $$ \left\lbrace\begin{array}{rcrcrl} 54324 & = & 4\times 12345 & + & 4944 & \\ 12345 & = & 2\times 4944 & + & 2457 & \\ 4944 & = & 2\times 2457 & + & 30& \\ 2457 & = & 81\times 30 & + & 27& \\ 30 & = & 1\times 27 & + & \color{#f00}{\large 3} & \color{#f00}{\large\Leftarrow} \\ 27 & = & 9\times 3 & + & 0 & \end{array}\right. $$
$\endgroup$
