GCD and LCM — Problem Set

Each problem below names the tool it uses. If a problem is hard, go back to that page first.

---

Level 1 — Direct

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

Tool: Power Identity

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

---

P2. If $\gcd(a,b) = 12$ and $\text{lcm}(a,b) = 1800$, find all pairs $(a,b)$ with $a \leq b$.

Tool: Fundamental Relation

Write $a = 12p$, $b = 12q$ with $\gcd(p,q)=1$ and $pq = 1800/12 = 150 = 2 \times 3 \times 5^2$.

Coprime factor pairs of 150 with $p \leq q$:

$(p,q)$	$\gcd$?	Valid?
$(1, 150)$	1	✓
$(2, 75)$	1	✓
$(3, 50)$	1	✓
$(6, 25)$	1	✓
$(10, 15)$	5	✗

Pairs $(a,b)$: $(12, 1800)$, $(24, 900)$, $(36, 600)$, $(72, 300)$.

---

P3. How many integers in $\{1, \ldots, 1000\}$ are coprime to 1000?

Tool: Euler's Totient

$\phi(1000) = 1000 \times (1-\tfrac{1}{2})(1-\tfrac{1}{5}) = 400$.

---

P4. Find $\gcd(F_{18}, F_{12})$ where $F_n$ is the $n$-th Fibonacci number.

Tool: Fibonacci GCD

$\gcd(F_{18}, F_{12}) = F_{\gcd(18,12)} = F_6 = 8$.

---

Level 2 — JEE Pattern

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

Tool: Invariance under shifts

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

Thus $n+1 \in \{-2,-1,1,2\}$, giving $\boxed{n \in \{-3,-2,0,1\}}$.

---

P6. Find all positive integer solutions to $12x + 8y = 100$.

Tool: Linear Diophantine Equations

$d = \gcd(12,8) = 4$ and $4 \mid 100$. ✓ Divide: $3x + 2y = 25$.

Particular: $(x_0, y_0) = (1, 11)$. General: $x = 1+2k$, $y = 11-3k$.

Positive constraints: $k \geq 0$ and $k \leq 3$.

4 solutions: $(1,11), (3,8), (5,5), (7,2)$.

---

P7. Prove: $\gcd(n^2+1, n+1) \in \{1, 2\}$ for all integers $n$.

Tool: Invariance

$\gcd(n^2+1, n+1) = \gcd(2, n+1)$, which is 2 if $n$ is odd, 1 if $n$ is even. $\blacksquare$

---

P8. Find the number of ordered pairs $(a,b)$ of positive integers such that $\text{lcm}(a,b) = 2^3 \times 3^2 \times 5$.

Tool: Prime-by-prime LCM counting

For $\text{lcm}(a,b) = p_1^{e_1} \cdots p_k^{e_k}$, the count of ordered pairs is $\prod (2e_i + 1)$.

$(2\times3+1)(2\times2+1)(2\times1+1) = 7 \times 5 \times 3 = 105$.

---

P9. Find $\gcd(n!+1, (n+1)!+1)$ for all $n \geq 1$.

Tool: Reduction to remainder

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

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

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

Answer: always 1.

---

P10. Solve the system: $x \equiv 3 \pmod 4$, $x \equiv 5 \pmod 6$, $x \equiv 2 \pmod 7$.

Tool: Chinese Remainder Theorem

Note: $\gcd(4,6) = 2 \neq 1$, so CRT doesn't directly apply. Check compatibility:

$x \equiv 3 \pmod 4 \implies x$ is odd. $x \equiv 5 \pmod 6 \implies x$ is odd (since $5$ is odd). ✓

Combine first two: $x \equiv 3 \pmod 4$ and $x \equiv 5 \pmod 6$.

$x = 4j+3$. Then $4j+3 \equiv 5 \pmod 6 \implies 4j \equiv 2 \pmod 6 \implies 2j \equiv 1 \pmod 3 \implies j \equiv 2 \pmod 3$.

So $j = 3m+2$, $x = 4(3m+2)+3 = 12m+11$. Thus $x \equiv 11 \pmod{12}$.

Now combine $x \equiv 11 \pmod{12}$ and $x \equiv 2 \pmod 7$. Here $\gcd(12,7)=1$. ✓

$x = 12n+11$. Then $12n+11 \equiv 2 \pmod 7 \implies 5n \equiv -9 \equiv 5 \pmod 7 \implies n \equiv 1 \pmod 7$.

$n = 7t+1$, $x = 12(7t+1)+11 = 84t+23$.

Answer: $x \equiv 23 \pmod{84}$.

---

Level 3 — Advanced

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

Tool: Bezout + Euclid's Lemma

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

Since $a^2-ab+b^2 = (a+b)^2 - 3ab$, we get $d \mid 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$.

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

Both values are achieved: $a=1, b=1$ gives $d=1$; $a=1, b=2$ gives $\gcd(3,3)=3$.

---

P12. Find all positive integer solutions to $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n}$ for fixed positive integer $n$.

Tool: Diophantine + divisor counting

Rearranging: $ny + nx = xy \implies xy - nx - ny = 0 \implies (x-n)(y-n) = n^2$.

Each factorization $n^2 = d_1 d_2$ with $d_1, d_2 > 0$ gives a solution: $x = n + d_1$, $y = n + d_2$.

Number of ordered solutions = $\tau(n^2)$, the number of positive divisors of $n^2$.

Example. $n = 6$: $n^2 = 36$ has $\tau(36) = 9$ divisors. 9 ordered pairs $(x,y)$.

---

P13. Prove: $\text{lcm}(1, 2, \ldots, 2n) \geq \dfrac{4^n}{2n+1}$.

Tool: LCM and combinatorics

The central binomial coefficient $\binom{2n}{n}$ is an integer. Its denominator in lowest terms divides $\text{lcm}(1, 2, \ldots, 2n)$ — in fact, $\text{lcm}(1,\ldots,2n) / \binom{2n}{n}$ is an integer.

Wait — more directly: since $\binom{2n}{n}$ is an integer, and $\binom{2n}{n} = \frac{(2n)!}{(n!)^2}$, the value $\text{lcm}(1,\ldots,2n) \cdot \frac{1}{n!^2}$ is... let me state the cleaner path.

From $(1+1)^{2n} = \sum_{k=0}^{2n}\binom{2n}{k}$ and all terms are positive: $\binom{2n}{n} \leq 4^n$.

Also the sum has $2n+1$ terms all at most $\binom{2n}{n}$, so $4^n \leq (2n+1)\binom{2n}{n}$, giving $\binom{2n}{n} \geq \frac{4^n}{2n+1}$.

Now observe: $\text{lcm}(1,2,\ldots,2n)$ is divisible by $\binom{2n}{n}$ (each $\binom{2n}{k}$ is an integer; the LCM of denominators... actually use: $\binom{2n}{n} \cdot \text{something} = \frac{\text{lcm}(1,\ldots,2n) \cdot \text{lcm}(1,\ldots,n)^2}{(2n)!/(2n)! }$...

The cleanest path: $\binom{2n}{n} \mid \text{lcm}(1,\ldots,2n)$ because $\text{lcm}(1,\ldots,2n) / \binom{2n}{n} = \frac{\text{lcm}(1,\ldots,2n) \cdot (n!)^2}{(2n)!}$ is the product over primes of certain prime power ratios that are always integers.

Therefore $\text{lcm}(1,\ldots,2n) \geq \binom{2n}{n} \geq \dfrac{4^n}{2n+1}$. $\blacksquare$

---

P14. (Construction) Show that for any integer $n \geq 2$, there exist $n$ consecutive integers each having a prime factor not dividing any of the others.

This uses the Chinese Remainder Theorem to construct a starting point, combined with the Fundamental Theorem of Arithmetic. The proof is existential — CRT guarantees the starting integer exists.

Left as an exercise — reconstruct the CRT-based construction using the CRT page.

---

Quick reference

Goal	Tool
Compute $\gcd$	Euclidean Algorithm
Write $\gcd$ as a combination	Bezout / Extended Euclidean
Prove $d \mid \gcd(a,b)$	Bezout: $\gcd = ax+by$
Show $a \mid c$ given $a\mid bc$, $\gcd(a,b)=1$	Euclid's Lemma
Solve $ax+by=c$	Bezout + general solution
Solve $ax \equiv b \pmod m$	Reduce by $d$, then invert
$\gcd(a^n-1, a^m-1)$	Power Identity
$\gcd(F_n, F_m)$	Fibonacci GCD Identity
Count coprime integers	Euler's Totient
Simplify $\gcd(f(n), g(n))$	Replace by remainder (shift identity)
Count pairs with given LCM	$\prod(2e_i+1)$ over prime factorization
Simultaneous congruences	CRT (requires pairwise coprimality)