GCD — Core Theorems

Most GCD problems at JEE Advanced level don't need new ideas. They need you to recognize which of a small set of identities applies, and apply it cleanly.

This page collects those identities. Each one comes with a proof short enough to reconstruct on the spot — because if you understand why it's true, you don't need to memorize it.

---

Identity 1 — Invariance under linear shifts

$\gcd(a, b) = \gcd(a + kb,\ b) \quad \text{for any integer } k$

Proof. Common divisors of $(a, b)$ and $(a + kb, b)$ are identical: any $d$ dividing both $a$ and $b$ also divides $a + kb$, and conversely $d$ dividing $a+kb$ and $b$ divides $(a+kb) - kb = a$. $\blacksquare$

Special case. $\gcd(a, b) = \gcd(a - b, b)$. Subtract repeatedly until the Euclidean Algorithm takes over.

JEE use. When you see $\gcd(f(n), g(n))$ where $f$ and $g$ share a polynomial relationship, subtract to simplify.

Example. $\gcd(n^2 + 1, n + 1)$.

$n^2 + 1 = (n+1)(n-1) + 2$, so $\gcd(n^2+1, n+1) = \gcd(2, n+1)$.

This equals 2 if $n$ is odd, and 1 if $n$ is even.

---

Identity 2 — Scaling

$\gcd(ma, mb) = m \cdot \gcd(a, b) \quad \text{for } m > 0$

Proof. Write $a = dp$, $b = dq$, $d = \gcd(a,b)$, $\gcd(p,q) = 1$. Then $ma = mdp$, $mb = mdq$, and since $\gcd(p,q)=1$, we have $\gcd(ma,mb) = md$. $\blacksquare$

Consequence. Always divide out the GCD first: $\gcd(a/d, b/d) = 1$ where $d = \gcd(a,b)$. This coprime pair is the "skeleton" — everything about $\gcd(a,b)$ lives here.

---

Identity 3 — The power identity

$\gcd(a^n - 1,\ a^m - 1) = a^{\gcd(n,m)} - 1$

This is the GCD identity that appears most often at JEE Advanced level.

Proof. The key lemma: $a^k - 1 \mid a^n - 1 \iff k \mid n$.

Why: If $n = qk$, then $a^n - 1 = (a^k)^q - 1 = (a^k - 1)\bigl((a^k)^{q-1} + \cdots + 1\bigr)$.

Now run the Euclidean algorithm on the exponents. The step $\gcd(a^n-1, a^m-1)$ with $n > m$:

$a^n - 1 = a^{n-m}(a^m - 1) + (a^{n-m} - 1)$

So $\gcd(a^n-1, a^m-1) = \gcd(a^m-1, a^{n-m}-1)$.

The exponents reduce exactly as in $\gcd(n, m)$. The algorithm terminates at $a^{\gcd(n,m)} - 1$. $\blacksquare$

Example. $\gcd(2^{100}-1, 2^{75}-1) = 2^{\gcd(100,75)}-1 = 2^{25}-1$.

---

Identity 4 — Fibonacci GCD

$\gcd(F_n, F_m) = F_{\gcd(n,m)}$

where $F_1 = 1, F_2 = 1, F_3 = 2, \ldots$

Proof. The key lemma: $F_m \mid F_n \iff m \mid n$.

Then use the identity $F_{m+n} = F_m F_{n+1} + F_{m-1} F_n$ to show:

$\gcd(F_m, F_n) = \gcd(F_m, F_{n \bmod m})$

This is the Euclidean algorithm on Fibonacci indices. It terminates at $F_{\gcd(m,n)}$. $\blacksquare$

Example. $\gcd(F_{12}, F_8) = F_{\gcd(12,8)} = F_4 = 3$.

---

Identity 5 — Consecutive integers are coprime

$\gcd(n, n+1) = 1 \quad \text{for all integers } n$

Proof. Any common divisor $d$ satisfies $d \mid (n+1) - n = 1$. $\blacksquare$

More generally: $\gcd(n, n+k) = \gcd(n, k)$.

The consecutive case is the $k=1$ instance — and $\gcd(n, 1) = 1$ always.

---

Identity 6 — GCD of an arithmetic progression

If $a, a+d, a+2d, \ldots$ is an arithmetic progression, then:

$\gcd(\text{all terms}) = \gcd(a, d)$

Proof. Every term $a + nd$ satisfies $\gcd(a + nd, d) = \gcd(a, d)$ by Identity 1. Taking GCD over all terms gives $\gcd(a, d)$. $\blacksquare$

---

Identity 7 — LCM distributes over GCD

$\text{lcm}(a, \text{lcm}(b, c)) = \text{lcm}(\text{lcm}(a, b), c) \quad \text{(associativity)}$

$\gcd(a, \text{lcm}(b, c)) = \text{lcm}(\gcd(a, b), \gcd(a, c)) \quad \text{(distributivity)}$

These hold because both $\gcd$ and $\text{lcm}$ operate prime-by-prime: $\gcd$ takes the minimum exponent at each prime, $\text{lcm}$ takes the maximum. Min and max distribute over each other.

---

Worked problems

Problem 1. Find $\gcd(2^{100}-1, 2^{75}-1)$.

Identity 3 directly: $\gcd(100, 75) = 25$. Answer: $2^{25}-1$.

Problem 2. Find all $n$ such that $n + 1 \mid n^2 + 1$.

Identity 1: $n^2+1 = (n+1)(n-1) + 2$, so $\gcd(n^2+1, n+1) = \gcd(2, n+1)$.

For $n+1 \mid n^2+1$, we need $n+1 \mid 2$. So $n+1 \in \{-2,-1,1,2\}$, giving $n \in \{-3,-2,0,1\}$.

Problem 3. Prove $\gcd(a,b) \cdot \gcd(a,c) = \gcd(a, bc) \cdot \gcd(a, \gcd(b,c))$ when $\gcd(b,c)=1$.

When $\gcd(b,c)=1$, the right side becomes $\gcd(a, bc) \cdot 1$. So the claim reduces to $\gcd(a,b)\cdot\gcd(a,c) = \gcd(a,bc)$ — which follows from the prime-by-prime min/max structure.

Problem 4. Find $\gcd(n!+1, (n+1)!+1)$.

$(n+1)! + 1 = (n+1) \cdot n! + 1$.

$\gcd(n!+1, (n+1)!+1) = \gcd(n!+1,\ (n+1)n!+1-(n+1)(n!+1)) = \gcd(n!+1, -n)= \gcd(n!+1, n)$.

Since $n \mid n!$, we have $n! \equiv 0 \pmod n$, so $n!+1 \equiv 1 \pmod n$. Thus $\gcd(n!+1, n) = 1$.

Answer: $\gcd(n!+1, (n+1)!+1) = 1$ for all $n \geq 1$.

Problem 5. Prove: if $\gcd(a,b)=1$, then $\gcd(a+b, a^2 - ab + b^2) \in \{1, 3\}$.

Let $d = \gcd(a+b, a^2-ab+b^2)$.

Note $a^2-ab+b^2 = (a+b)^2 - 3ab$.

So $d \mid (a+b)^2 - (a^2-ab+b^2) = 3ab$.

If prime $p \mid d$ and $p \mid a$: then $p \mid a+b$ forces $p \mid b$, contradicting $\gcd(a,b)=1$.

So $\gcd(d, a) = \gcd(d, b) = 1$, hence $d \mid 3$.

Therefore $d \in \{1, 3\}$. $\blacksquare$

---

The pattern to internalize

Every identity here follows one of two moves:

1. Replace by remainder — $\gcd(a,b) = \gcd(b, a \bmod b)$, the Euclidean step.
2. Use linear combinations — $d \mid a$ and $d \mid b$ implies $d \mid ax + by$.

When a GCD problem looks hard, ask: which of these two moves simplifies it?