Find the greatest common divisor of $123456$ and $654321$.

Step 1: Let's check for small prime divisors using standard divisibility rules:

• Sum of digits of $123456=1+2+3+4+5+6=21$. Since $21$ is divisible by $3$ but not by $9$, $123456$ is divisible by $3$ but not by $9$.

• Sum of digits of $654321=6+5+4+3+2+1=21$. Similarly, $654321$ is divisible by $3$ but not by $9$.

Step 2: Since $123456$ is even and $654321$ is odd, the greatest common divisor cannot be even.

Step 3: Use the Euclidean Algorithm or division to find $\gcd (654321,123456)$:

• $654321=5\times 123456+37041$

• $123456=3\times 37041+12333$

• $37041=3\times 12333+42$

• $12333=293\times 42+27$

• $42=1\times 27+15$

• $27=1\times 15+12$

• $15=1\times 12+3$

• $12=4\times 3+0$

Step 4: The last non-zero remainder is $3$, so the greatest common divisor is $3$.