# 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>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$.↵
* If $m$ is odd, then $\gcd(a^m-b^m,\ ab)=1$ when $\gcd(a,b)=1$.↵
6. **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↵
↵
$$↵
x^3+y^3=x^2+42xy+y^2.↵
$$↵
↵
**Move:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Then↵
↵
$$↵
d(a+b)(a^2-ab+b^2)=a^2+42ab+b^2.↵
$$↵
↵
Hence $(a^2+42ab+b^2)\mid d(a+b)(a^2-ab+b^2)$, and by coprimality we get↵
↵
$$↵
a^2+42ab+b^2\mid a^2-ab+b^2 \ \Rightarrow\ 43ab\mid a^2-ab+b^2.↵
$$↵
↵
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↵
↵
$$↵
x^4-y^4=p\,(x^3-y^3).↵
$$↵
↵
**Move:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Then↵
↵
$$↵
d(a+b)(a^2+b^2)=p\,(a^2-+ab+b^2).↵
$$↵
↵
By the lemmas, $\gcd\!\big((a+b)(a^2+b^2),\ a^2-+ab+b^2\big)=1$. Hence $p\mid(a+b)(a^2+b^2)$, impossible for a prime $p$ when $a,b>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>0\Rightarrow y>0$. Put $x=ad,\ y=bd,\ \gcd(a,b)=1$. We get↵
↵
$$↵
d\,(a^2+5b^2)=2021\,b.↵
$$↵
↵
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$.↵
↵
$$↵
d^3\,(a^5-b^5)=16ab.↵
$$↵
↵
By the lemma $\gcd(a^5-b^5,\ ab)=1$ (odd power and $\gcd(a,b)=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,\ 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 odd $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][1])↵
* **1967B2 — Reverse Card (Hard):** same structure with inverted divisibility; technique is the same, but watch the bounds. ([Codeforces][2])↵
* **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][3])↵
* **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][4])↵
* **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][5])↵
↵
**AtCoder**↵
↵
* **ABC177 E — Coprime:** checking pairwise/setwise coprimality via gcd and prime sieve (nice warm-up for the lemmas). ([AtCoder][6])↵
* **ARC124 C — LCM of GCDs:** careful $\gcd/\mathrm{lcm}$ juggling over buckets; keep factoring out shared gcds and normalizing. ([AtCoder][7])↵
↵
**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$.↵
↵
[1]: https://mirror.codeforces.com/problemset/problem/1967/B1↵
[2]: https://mirror.codeforces.com/problemset/problem/1967/B2↵
[3]: https://mirror.codeforces.com/problemset/problem/992/B↵
[4]: https://mirror.codeforces.com/problemset/problem/1617/B↵
[5]: https://mirror.codeforces.com/problemset/problem/2043/D↵
[6]: https://atcoder.jp/contests/abc177/tasks/abc177_e↵
[7]: https://atcoder.jp/contests/arc124/tasks/arc124_c
↵
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>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
* If $m$ is odd, then $\gcd(a^m-b^m,\ ab)=1$ when $\gcd(a,b)=1$.↵
6. **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↵
↵
$$↵
x^3+y^3=x^2+42xy+y^2.↵
$$↵
↵
**Move:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Then↵
↵
$$↵
d(a+b)(a^2-ab+b^2)=a^2+42ab+b^2.↵
$$↵
↵
Hence $(a^2+42ab+b^2)\mid d(a+b)(a^2-ab+b^2)$, and by coprimality we get↵
↵
$$↵
a^2+42ab+b^2\mid a^2-ab+b^2 \ \Rightarrow\ 43ab\mid a^2-ab+b^2.↵
$$↵
↵
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↵
↵
$$↵
x^4-y^4=p\,(x^3-y^3).↵
$$↵
↵
**Move:** $x=ad,\ y=bd,\ \gcd(a,b)=1$. Then↵
↵
$$↵
d(a+b)(a^2+b^2)=p\,(a^2
$$↵
↵
By the lemmas, $\gcd\!\big((a+b)(a^2+b^2),\ a^2
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>0\Rightarrow y>0$. Put $x=ad,\ y=bd,\ \gcd(a,b)=1$. We get↵
↵
$$↵
d\,(a^2+5b^2)=2021\,b.↵
$$↵
↵
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$.↵
↵
$$↵
d^3\,(a^5-b^5)=16ab.↵
$$↵
↵
By the lemma $\gcd(a^5-b^5,\ ab)=1$ (odd power and $\gcd(a,b)=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,\ 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 odd $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][1])↵
* **1967B2 — Reverse Card (Hard):** same structure with inverted divisibility; technique is the same, but watch the bounds. ([Codeforces][2])↵
* **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][3])↵
* **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][4])↵
* **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][5])↵
↵
**AtCoder**↵
↵
* **ABC177 E — Coprime:** checking pairwise/setwise coprimality via gcd and prime sieve (nice warm-up for the lemmas). ([AtCoder][6])↵
* **ARC124 C — LCM of GCDs:** careful $\gcd/\mathrm{lcm}$ juggling over buckets; keep factoring out shared gcds and normalizing. ([AtCoder][7])↵
↵
**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$.↵
↵
[1]: https://mirror.codeforces.com/problemset/problem/1967/B1↵
[2]: https://mirror.codeforces.com/problemset/problem/1967/B2↵
[3]: https://mirror.codeforces.com/problemset/problem/992/B↵
[4]: https://mirror.codeforces.com/problemset/problem/1617/B↵
[5]: https://mirror.codeforces.com/problemset/problem/2043/D↵
[6]: https://atcoder.jp/contests/abc177/tasks/abc177_e↵
[7]: https://atcoder.jp/contests/arc124/tasks/arc124_c
