Gcd of $314159265358979323846264338$ and $271828182845904523536028747$?

Question

What is the short method to find gcd of large numbers such as

$$ \begin{align*} 314159265358979323846264338\\ {\text{and }}\\ 271828182845904523536028747 \end{align*} $$

I was reading through the book titled "Elementary Number Theory: Primes, Congruences, and Secrets" by William Stein and right on 20th page I find a problem that I have no clue of the shortest method to approach solving this.

However, when I did a quick search on Wolfram Alpha I got $$ \begin{align*} 314159265358979323846264338 &= 2 \times 3 \times 7 \times 13 \times 17 \times 23 \times 53 \times 27765442739383319011\\ 271828182845904523536028747 &= 13 \times 31 \times 14419 \times 48287851 \times 968760484921 \end{align*} $$ So, the gcd appears to be $13$

Are there any tricks involving the ending digits of these numbers? I am also looking at a book titled Stupid Divisibility Tricks, but so far I could'nt find any easy way yet.

Answer 1

Euclid's algorithm is very fast, running in (at worst) time proportional to the length of the input numbers, and is also simple.

To find $GCD(a,b)$, where $a>b$, you first see if $b=0$; if so, the answer is simply $a$. Otherwise divide $a$ by $b$, yielding a remainder $r$. The answer is then the same as $GCD(b, r)$, which you can calculate by the same method.

Pseudo-pseudocode:

function gcd(a, b) {
  while (b ≠ 0) {
    r = a mod b;
    a = b;
    b = r;
  }
  return a;
}

Answer 2

Given that these numbers are $\lfloor{10^{26}\pi}\rfloor$ and $\lfloor{10^{26}e}\rfloor$, there's probably not any faster trick than the Euclidean algorithm (using the continued fraction expansion of $\pi/e$ is the equivalent computation), which is probably what Stein is leading up to. When he says by any means, I think using sage or Wolfam Alpha is fair game. It is quite an impressively efficient algorithm, although there exist special implementations such as binary GCD that may or may not be more efficient, depending on your CPU.

Answer 3

The only trick involving the ending of the numbers are ones like the following:

$$\begin{align} \gcd(1234567, 3210987) &= \gcd(1234567, 3210987 - 1234567) \\&= \gcd(1234567, 1976420) \\&= \gcd(1234567, 197642) \\&= \gcd(1234567, 98821) \end{align}$$

The last two steps take advantage of the fact the first term isn't divisible by 10 or by 2, so I could cancel them out of the second term. Computer implementations often use this trick to pull off the factors of 2 after each step. (Factors of 10 are not useful to the computer, and for a human to make use of it, he either has to get lucky or do extra work to force a 0 to appear)

Examples of forcing a 0 in would be something like

$$\begin{align} \gcd(1234567, 98821) &= \gcd(1234567 - 7 \cdot 98821, 98821) \\ &= \gcd(542820, 98821) \\ &= \gcd(54282, 98821) \\ &= \gcd(27141, 98821) \\ &= \gcd(27141, 71680) \\ &= \gcd(27141, 7168) \\ &= \gcd(4 \cdot 27141 - 3 \cdot 7168, 1 \cdot 27141 - 1 \cdot 7168) \qquad \qquad (*) \\ &= \gcd(87060, 19973) \\ &= \gcd(8706, 19973) \end{align}$$

The step (*) needs elaboration: several steps of adding/subtracting one from the other were combined into a single matrix operation $$ \left( \begin{matrix} 4 & -3 \\ 1 & -1 \end{matrix} \right) \left(\begin{matrix} 27141 \\ 7168 \end{matrix} \right) $$ The main thing is that the determinant is $\pm 1$, so that it really is just a combination of adding / subtracting one row from the other and swapping them. I picked $(4,-3)$ just to have smallish numbers that produced a $0$ at the end. One could try something more systematic....

This trick is also used in computer implementations for sufficiently large numbers, but usually they trick is applied to the left end rather than the right end (Lehmer's algorithm). And as is often the case, ways to make things easier on the computer don't always translate into ways to make things easier on humans, so I can't guarantee you'll actually find this useful.

There are other tricks like splitting the two numbers into left and right halves (the "half-GCD" algorithm), but you're trading large GCD's for large multiplies, and will almost surely not be useful for a human.

---

Really, the only "tricks" of the sort I think you have in mind are eyeballing special forms that won't work for general computation. e.g. to compute

$$ \gcd(100000100101, 1001) $$

You might left shift 1001 up to cancel off the first 1, then add in another shifted copy to cancel the -1:

$$\begin{array}{r} 100000100101 \\ - 100100000000 \\ + 100100000 \\\hline \\ = 200101\end{array}$$

and so

$$ \begin{align}\gcd(100000100101, 1001) &= \gcd(200101, 1001) \\ &= \gcd(100001, 1001) \end{align} $$

And do it again (but also left shift 100001 so we have room: $$\begin{array}{r} \\ 1000010 \\ - 1001000 \\ + 1001 \\\hline \\ = 11\end{array}$$

and so to continue the computation:

$$ \cdots = \gcd(11, 1001) = \gcd(11, 11) = 11$$

Or other cases where you can quickly spot something you can do to let you multiply or divide things very quickly, or cancel things out to simply stuff.

Answer 4

I have no idea why you don't like the standard gcd algorithm, there's Stein's algorithm that is really fast too, but nevertheless here you have some jewel (attributed to Pratt) in pseudocode:

gcd(a, b) = nuclid(a, b, a, b)

nuclid(a, b, m, n) = 
    if (n != 0) then nuclid(a, b, n, choose(a, b, m) % n)
    else if (a % m != 0) then nuclid(a, b, m, a % m)
    else if (b % m != 0) then nuclid(a, b, m, b % m)
    else m

choose(a, b, m) = a
choose(a, b, m) = b
choose(a, b, m) = m

The percent sign $\%$ denotes modulo operation and choose is a non-deterministic function that returns each of its inputs with probability $\frac{1}{3}$. I hope that this fulfills your requirements for, as you stated it, non-obvious and tricky. Please, before you use it, prove that it does return the greatest common divisor of $a$ and $b$ and that it stops--both are rather easy and very nice exercises ;-)