Introducing gcd: sacrifice one variable to gain tight constraints

In problems with two (or more) integer variables it’s often profitable to factor out their gcd: let $$$d=\gcd(x,y)$$$, then write $$$x=a d,\ y=b d$$$ with $$$\gcd(a,b)=1$$$. Sure, you’ve added one more variable ($$$d$$$), but in exchange you get the coprimality of $$$a,b$$$, which sharply restricts the search space, makes divisibility statements “split” into clean factors, and simplifies the final casework/estimates.

How to apply (6-step template)

1. Normalize. Handle zeros/signs first (e.g., consider the cases $$$x=0\leftrightarrow y=0$$$, $$$x,y \gt 0$$$, etc.).
2. Introduce gcd. Put $$$d=\gcd(x,y)$$$, set $$$x=a d,\ y=b d$$$ with $$$\gcd(a,b)=1$$$.
3. Cancel powers of $$$d$$$. Divide the original equation/divisibility by the maximal power of $$$d$$$.
4. Split divisibility. Any statement like $$$U(a,b)\mid V(a,b)$$$ with coprime pieces often forces a “big” factor to divide one rigid component.
5. Finish with tiny gcd-lemmas. Standard 1–3 line facts (by Euclid) you’ll use repeatedly:

• $$$\gcd(a^2+b^2,\ ab)=1$$$ when $$$\gcd(a,b)=1$$$.
• $$$\gcd(a+b,\ a^2+ab+b^2)=1$$$ when $$$\gcd(a,b)=1$$$.
• $$$\gcd(a^m-b^m,\ ab)=1$$$ when $$$\gcd(a,b)=1$$$.

1. Wrap up by checking a short list of cases/divisors. After Step 4 you typically reduce to a finite set (often divisors of a prime/nearly prime number) that’s easy to brute-check.

Four illustrative sketches

1) BMO 2017 P1

Find all positive integer pairs $$$(x,y)$$$ such that

Move: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Then

Hence

But $$$\gcd\big(ab,\ a^2-ab+b^2\big)=1$$$ (see lemmas), so $$$a^2-ab+b^2\mid 43$$$. Thus $$$a^2-ab+b^2\in{1,43}$$$ — finish by a short brute force (squares grow fast).

2) JBMO SL 2019 N3

Find all primes $$$p$$$ and non-negative integers $$$x\neq y$$$ such that

Move: $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. Then

By the lemmas, $$$\gcd\big((a+b)(a^2+b^2),\ a^2+ab+b^2\big)=1$$$. Hence $$$(a+b)(a^2+b^2)\mid p$$$, impossible for a prime $$$p$$$ when $$$a,b \gt 0$$$. Conclusion: one of $$$x,y$$$ is zero $$$\Rightarrow (x,y)=(0,p),(p,0)$$$.

3) JBMO SL 2021 N5

Find all integer solutions of $$$x^2+5y^2=2021y$$$.

Move: first note $$$x=0\iff y=0$$$. Then assume $$$x \gt 0\Rightarrow y \gt 0$$$. Put $$$x=ad,\ y=bd,\ \gcd(a,b)=1$$$. We get

Since $$$\gcd(a^2+5b^2,\ b)=1$$$, it follows that $$$a^2+5b^2\mid 2021$$$. (Factor 2021 and finish with a short divisor check.)

4) JBMO 2018 P1

Find all integers $$$m,n$$$ with $$$m^5-n^5=16mn$$$.

Move: $$$m=0\iff n=0$$$. For $$$mn\neq0$$$: $$$m=ad,\ n=bd,\ \gcd(a,b)=1$$$.

By the lemma $$$\gcd(a^5-b^5,\ ab)=1$$$, hence $$$a^5-b^5\mid16$$$. Finish by checking the divisors of 16.

When this gcd-trick almost surely shines

• Symmetric polynomials in $$$x,y$$$ with the “classic” blocks $$$a^2\pm ab+b^2$$$, $$$a^m\pm b^m$$$.
• Equations/divisibilities where, after canceling $$$d$$$, a rigid coprime factor appears.
• gcd/lcm couplings (“given gcd and lcm”, “gcd divides/is multiple of …”, etc.).
• “Optimize distance with fixed $$$\gcd$$$”: $$$A=G\cdot u$$$, $$$B=G\cdot v$$$, $$$\gcd(u,v)=1$$$.

Mini-lemma library (all 1–3 lines via Euclid)

• $$$\gcd(a^2+b^2,\ ab)=\gcd(a^2-b^2,\ ab)=1$$$ for $$$\gcd(a,b)=1$$$.
• $$$\gcd(a+b,\ a^2-ab+b^2)=\gcd(a+b,\ 3ab)$$$. With $$$\gcd(a,b)=1$$$ and $$$a+b$$$ not divisible by $$$a$$$ or $$$b$$$, this equals 1 or 3.
• $$$\gcd(a^m-b^m,\ a)=\gcd(b^m,\ a)=1$$$ for all $$$m$$$ when $$$\gcd(a,b)=1$$$; similarly for $$$b$$$.

CP tasks where “factor out the gcd” fits naturally

Codeforces

• 1967B1 — Reverse Card (Easy): condition “ $$$a+b$$$ is a multiple of $$$b\cdot\gcd(a,b)$$$”. Set $$$a=du,\ b=dv,\ \gcd(u,v)=1$$$ and reduce to divisors/constraints on $$$u,v$$$. (Codeforces)
• 1967B2 — Reverse Card (Hard): same structure with inverted divisibility; technique is the same, but watch the bounds. (Codeforces)
• 992B — Nastya and an Array of GCDs (count pairs with given $$$\gcd$$$ and $$$\mathrm{lcm}$$$): write $$$a=gx,\ b=gy$$$, $$$\gcd(x,y)=1$$$, with $$$xy=\frac{\mathrm{lcm}}{g}$$$. Then enumerate divisors. (Codeforces)
• 1617B — GCD Problem (find $$$a,b,c$$$ with $$$\gcd(a,b)=c$$$ and $$$a+b+c=n$$$): take $$$a=cu,\ b=cv$$$, $$$\gcd(u,v)=1$$$, reduce to $$$n-c=c(u+v)+c$$$. (Codeforces)
• 2043D — GCD Distance (maximize $$$|A-B|$$$ with $$$\gcd(A,B)=G$$$ and $$$A,B\in[l,r]$$$): set $$$A=G u,\ B=G v,\ \gcd(u,v)=1$$$ and work on $$$u,v$$$ within the rescaled interval. (Codeforces)

AtCoder

• ABC177 E — Coprime: checking pairwise/setwise coprimality via gcd and prime sieve (nice warm-up for the lemmas). (AtCoder)
• ARC124 C — LCM of GCDs: careful $$$\gcd/\mathrm{lcm}$$$ juggling over buckets; keep factoring out shared gcds and normalizing. (AtCoder)

Complexity note. After normalizing to $$$\gcd(a,b)=1$$$, the enumeration typically runs over divisors of a single integer (or a pair whose product is fixed), so it’s ~$$$O(\tau(n))$$$ or $$$O(\sqrt n)$$$. This is far faster than naive iteration over $$$x,y$$$.