What is $\gcd(12345,54321)$? 
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.
 A: Hint: Look at the sum of the digits of $12345$ and $54321$ , it's divisible by $3$. So $\ldots$
A: 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.
A: 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.
A: $\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.
$$
