# Gcd of $314159265358979323846264338$ and $271828182845904523536028747$?

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.

-
I think the Euclidean algorithm is quite effective. –  Joel Cohen Mar 19 '12 at 0:03
I know Euclidean algorithm, but the fact is there are shorter tricks and I would like to explore them –  Siddhi V Iyer Mar 19 '12 at 0:04
"The fact is there are shorter tricks." If you know for a fact that there are shorter tricks, do you know what they are? If not, then why not say "I know there are shorter tricks" (how?) and ask what they are. And if you don't know for a fact if there are shorter tricks, well, then why say you do? –  Arturo Magidin Mar 19 '12 at 0:13
van den Dries-Moschovakis, "Is the Euclidean algorithm optimal among its peers?" Bull. Symbolic Logic 10 (2004), 3, 390–418. From MathReviews: "Let $rem(a,b)$ be the remainder in the division of $a$ by $b$. Assume that $rem(x,y)$ can be provided on demand by some "oracle" in 1 "time unit". If $c(a,b)$ is the time complexity function of the Euclidean algorithm, we know that $c(a,b)\le3\log_2a$ for $a>b>1$. Conjecture. If an algorithm computes $\gcd(x,y)$ from "$rem$" with time complexity $d(x,y)$, then there is a rational $r>0$ such that for infinitely many $a>b>1$, $d(a,b)> r\log_2a$." –  Andres Caicedo Mar 19 '12 at 0:23
Are there any tricks involving the ending digits of these numbers? If the end digits are both even then there is a common factor of 2; if they are each 0 or 5 then there is a common factor of 5. Divide through and repeat. –  Henry Mar 19 '12 at 0:28

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.

-
Thank you for putting it so clearly. I thank all other people as well for emphasizing on Euclid's Algorithm. –  Siddhi V Iyer Mar 19 '12 at 0:34

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;
}

-
I am looking for a non-obvious method (something tricky and quick). –  Siddhi V Iyer Mar 19 '12 at 0:05
The Euclidean Algorithm is the quick method. Non-obvious doesn't always mean "better" or "faster". –  Arturo Magidin Mar 19 '12 at 0:08
Wikipedia has a section on "efficiency of alternative methods" with references that you might want to look at. –  MJD Mar 19 '12 at 0:13
Euclid is a lot faster than factoring the numbers into primes. –  GEdgar Mar 19 '12 at 0:21
I do know there are a lot of smart people here, so I take all your suggestions. Sorry if my comment earlier appeared too blunt. –  Siddhi V Iyer Mar 19 '12 at 0:24

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.

-

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 ;-)

-
Thank you for pseudocode and your suggestions. –  Siddhi V Iyer Mar 19 '12 at 0:39
Is line 4 computing a remainder mod 0? That sounds bad. Also, do you know a reference for this algorithm? –  Nate Eldredge Mar 19 '12 at 2:23
@NateEldredge This is of course wrong, there should be $\neq$, thanks! The only reference I have is this script by Yiannis N. Moschovakis. –  dtldarek Mar 19 '12 at 2:53