GCD of many numbers Given $a_1,...,a_n$
$gcd(a_1,...,a_n) = b$
I need to find $i$, so if i apply euclids algorithm to $(a_1,a_i)$, i end with $(0,b)$ or $(b,0)$.
 A: Say we have the numbers
$$
30, 20, 15, 10, 45
$$
then the greatest common divisor of all those numbers is $5$, but if you take $\gcd(a_1, a_i)$ for $2\leq i \leq 5$, you get the list
$$
10, 15, 10, 15
$$
and none of those are equal to $5$. To get the correct answer, you have to repeat the process with the new list until only one number remains (i.e. all numbers on the list, possibly one, possibly many, are equal). To get to the answer faster, though, it might be a good idea to start with not the first number in the list, but the smallest. Had we used $a_4 = 10$ in all our checks instead of $a_1 = 30$, we would've gotten
$$
10, 10, 5, 5
$$
which is a better intermediate point.
A: You can always reduce the set one number at a time:
$$\gcd(a_1,a_2,\ldots,a_{n-1},a_n) = \gcd(a_1,a_2,\ldots,\gcd(a_{n-1},a_n)).$$
There is also a well-known algorithm that does three numbers at a time.
Label the numbers $x,y,z$ so that $z$ is the smallest.
To find $\gcd(x,y,z)$, divide each of $x$ and $y$ by $z$ with remainder:
$$\begin{eqnarray}
   x &=& q_1z + r_1,\ & 0 \leq r_1 < z,\\
   y &=& q_2z + r_2,\ & 0 \leq r_2 < z.
\end{eqnarray}$$
If the remainders are both zero, $z = gcd(x,y,z)$.
Otherwise, set $x',y',z'$ to $r_1, r_2, z,$
but assign them in order so that $z'$ is smaller than $x'$ or $y'$.
Then find $\gcd(x', y', z').$
This can be extended to larger lists of numbers. At each step, always choose the
smallest number as the divisor of all the others.
