Math Core

Factoring $2873$ and $1547$ to find their GCD is slow. The Euclidean algorithm finds it in a few subtractions, with no factoring at all. More importantly for the AMC, the same idea handles GCDs of expressions: $\gcd(n^2 + 5, n + 3)$ , $\gcd(2^{36} - 1, 2^{24} - 1)$ , or when a fraction like $\dfrac{n^2 + 2}{n + 4}$ can be reduced.

The key fact

If $d$ divides both $a$ and $b$ , then $d$ divides $a - b$ , and more generally $a - kb$ for any integer $k$ . The reverse is true too. So $a, b$ and $a - kb, b$ have exactly the same common divisors, and therefore the same GCD.

The Euclidean algorithm

For any integers $a$ , $b$ , $k$ :

$\gcd(a, b) = \gcd(a - kb,\ b).$

Choosing $k$ to make $a - kb$ the remainder $a \bmod b$ gives $\gcd(a, b) = \gcd(b,\ a \bmod b)$ . Repeat until the remainder is $0$ ; the last nonzero remainder is the GCD.

For $\gcd(1071, 462)$ :

\begin{aligned} 1071 &= 2 \cdot 462 + 147 \\ 462 &= 3 \cdot 147 + 21 \\ 147 &= 7 \cdot 21 + 0 \end{aligned}

So $\gcd(1071, 462) = 21$ .

GCDs of expressions

The same move works when $a$ and $b$ are expressions in $n$ : subtract a multiple of one from the other to kill the variable. What remains is a constant $c$ , and then $\gcd$ must divide $c$ .

For $\gcd(n^2 + 3,\ n + 2)$ : subtract $(n - 2)(n + 2) = n^2 - 4$ from $n^2 + 3$ to get $7$ . So $\gcd(n^2 + 3, n + 2) = \gcd(7, n + 2)$ , which is $7$ when $n \equiv 5 \pmod 7$ and $1$ otherwise. (Shortcut: $n \equiv -2 \pmod{n+2}$ , so $n^2 + 3 \equiv 4 + 3 = 7$ .)

Powers and Fibonacci numbers

Since $2^{36} - 1 = 2^{12}(2^{24} - 1) + (2^{12} - 1)$ , a step of the algorithm on $2^a - 1$ and $2^b - 1$ looks exactly like a step on the exponents $a$ and $b$ . So

$\gcd(x^a - 1,\ x^b - 1) = x^{\gcd(a, b)} - 1$

for any integer $x \ge 2$ . The Fibonacci numbers ( $F_1 = F_2 = 1$ , $F_{n+1} = F_n + F_{n-1}$ ) have the same property: $\gcd(F_a, F_b) = F_{\gcd(a, b)}$ .

Running it backward: Bézout

Each remainder in the algorithm is a combination of the two original numbers. Substituting back up the chain writes $\gcd(a, b)$ as $ax + by$ for some integers $x, y$ . This is Bézout's identity, and it is why $ax + by = c$ is solvable whenever $\gcd(a, b) \mid c$ . When $\gcd(a, m) = 1$ , it also finds the inverse of $a$ modulo $m$ .

Worked example: Plain Euclid

Find $\gcd(2873, 1547)$ .

\begin{aligned} 2873 &= 1 \cdot 1547 + 1326 \\ 1547 &= 1 \cdot 1326 + 221 \\ 1326 &= 6 \cdot 221 + 0 \end{aligned}

The GCD is $221$ . (Indeed $2873 = 13 \cdot 221$ and $1547 = 7 \cdot 221$ .)

Worked example: A GCD of expressions

As $n$ ranges over the positive integers, what is the largest possible value of $\gcd(n^2 + 5,\ n + 3)$ ?

$n^2 + 5 - (n - 3)(n + 3) = n^2 + 5 - n^2 + 9 = 14$ . So $\gcd(n^2 + 5, n + 3) = \gcd(14, n + 3)$ , which is at most $14$ . It equals $14$ when $14 \mid n + 3$ , for example $n = 11$ : $\gcd(126, 14) = 14$ . The answer is $14$ .

Worked example: Differences of powers

Find $\gcd(2^{36} - 1,\ 2^{24} - 1)$ .

$\gcd(36, 24) = 12$ , so the GCD is $2^{12} - 1 = 4095$ .

Worked example: An inverse by back-substitution

Find the integer $x$ with $0 \le x \lt 100$ and $37x \equiv 1 \pmod{100}$ .

Run the algorithm:

\begin{aligned} 100 &= 2 \cdot 37 + 26 \\ 37 &= 1 \cdot 26 + 11 \\ 26 &= 2 \cdot 11 + 4 \\ 11 &= 2 \cdot 4 + 3 \\ 4 &= 1 \cdot 3 + 1 \end{aligned}

Back-substitute, keeping everything in terms of $100$ and $37$ :

\begin{aligned} 1 &= 4 - 3 = 4 - (11 - 2 \cdot 4) = 3 \cdot 4 - 11 \\ &= 3(26 - 2 \cdot 11) - 11 = 3 \cdot 26 - 7 \cdot 11 \\ &= 3 \cdot 26 - 7(37 - 26) = 10 \cdot 26 - 7 \cdot 37 \\ &= 10(100 - 2 \cdot 37) - 7 \cdot 37 = 10 \cdot 100 - 27 \cdot 37. \end{aligned}

So $-27 \cdot 37 \equiv 1 \pmod{100}$ and $x = 100 - 27 = 73$ . Check: $37 \cdot 73 = 2701$ .

Common mistake

When you reduce $\gcd(f(n), g(n))$ to $\gcd(c, g(n))$ , the GCD divides $c$ , but it doesn't have to equal $c$ . Always check that some $n$ actually reaches the value you claim, and watch out for a step where you multiplied one expression by a constant: that can introduce extra factors (see the practice problem about $\gcd(n^2 + 7, 2n + 1)$ ).

Practice

Practice 1

What is $\gcd(3^{20} - 1,\ 3^{12} - 1)$ ?

Practice 2

What is $\gcd(4199, 3094)$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 3

For how many integers $n$ with $1 \le n \le 100$ is $\gcd(n + 7,\ 2n + 1) \gt 1$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 4

What is the smallest positive integer $x$ such that $17x - 1$ is divisible by $60$ ?

Practice 5

The Fibonacci numbers are $F_1 = F_2 = 1$ and $F_{n+1} = F_n + F_{n-1}$ . What is $\gcd(F_{60}, F_{45})$ ?

Practice 6

As $n$ ranges over the positive integers, what is the largest possible value of $\gcd(n^2 + 7,\ 2n + 1)$ ?

Practice 7

For how many positive integers $n \le 1000$ is the fraction $\dfrac{n^2 + 2}{n + 4}$ not in lowest terms?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Real contest practice

2025 AMC 10A, Problem 17: find a common divisor quickly with the Euclidean algorithm.
1985 AIME, Problem 13: the largest GCD of consecutive terms of $100 + n^2$ (a stretch beyond the AMC).