jmc

By the Euclidean Algorithm, $$\begin{array}{rl}\text{gcd}(654321,543210)& =\text{gcd}(654321-543210,543210)\\ & =\text{gcd}(111111,543210)\\ & =\text{gcd}(5\cdot 111111-543210,111111)\\ & =\text{gcd}(12345,111111)\\ & =\text{gcd}(12345,12345\cdot 10-111111)\\ & =\text{gcd}(12345,12339)\\ & =\text{gcd}(12345-12339,12339)\\ & =\text{gcd}(6,12339).\end{array}$$We notice that $3|12339$ as $3|1+2+3+3+9=18$, but $12339$ is odd and thus not divisible by $6$. The answer is $\boxed{3}$.