Number TheoryDifficulty 15-75133 tagged problems

GCD and LCM

GCD and LCM is the habit of using greatest common divisors and least common multiples to organize integer constraints. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b \quad (a, b > 0)$$

The greatest common divisor and least common multiple of two positive integers multiply to the product of the numbers themselves.

Why It Works

1
Write the prime factorizations of $a$ and $b$, allowing exponent $0$ for primes that are missing.
2
For each prime $p$, the gcd takes the minimum exponent $\min(e_p, f_p)$ and the lcm takes the maximum $\max(e_p, f_p)$.
3
For every prime, $\min(e_p, f_p) + \max(e_p, f_p) = e_p + f_p$.
4
Multiplying over all primes, the exponents in $\gcd(a,b)\cdot\operatorname{lcm}(a,b)$ match those in $a \cdot b$, so the two products are equal.

Worked Examples

Example 1

Two positive integers have $\gcd 6$ and $\operatorname{lcm} 180$. If one of them is $36$, find the other.

1
Use $\gcd \cdot \operatorname{lcm} = a \cdot b$, so $6 \cdot 180 = 36 \cdot b$.
2
Compute the left side: $6 \cdot 180 = 1080$.
3
Then $b = 1080 / 36 = 30$.
4
Check: $\gcd(36, 30) = 6$ and $\operatorname{lcm}(36, 30) = 180$, as required.

Answer:

$30$

Warm-up

How many ordered pairs of positive integers $(a, b)$ satisfy $\gcd(a, b) = 5$ and $\operatorname{lcm}(a, b) = 50$?

1
Write $a = 5x$, $b = 5y$ with $\gcd(x, y) = 1$. Then $\operatorname{lcm}(a,b) = 5xy = 50$, so $xy = 10$.
2
We need coprime ordered pairs $(x, y)$ with $xy = 10 = 2 \cdot 5$.
3
Coprimality forces each prime power to go ENTIRELY to $x$ or entirely to $y$ (a prime split between them would be a common factor). With $\omega(10) = 2$ distinct primes ($2$ and $5$) and $2$ choices each, there are $2^2 = 4$ ordered coprime pairs: $(x,y) \in \{(1,10),(2,5),(5,2),(10,1)\}$.
4
So there are $4$ pairs: $(5,50),(10,25),(25,10),(50,5)$.

Answer:

$4$

Contest level

How many ordered pairs of positive integers $(a, b)$ satisfy $\gcd(a, b) = 10$ and $\operatorname{lcm}(a, b) = 1000$?

1
Factor $10 = 2 \cdot 5$ and $1000 = 2^3 \cdot 5^3$. Work prime by prime: write $a = 2^{x_1}5^{y_1}$, $b = 2^{x_2}5^{y_2}$.
2
Prime $2$: $\min(x_1, x_2) = 1$ and $\max(x_1, x_2) = 3$. So $\{x_1, x_2\} = \{1, 3\}$ as a set, giving $2$ ordered assignments.
3
Prime $5$: $\min(y_1,y_2) = 1$, $\max(y_1,y_2) = 3$, so $\{y_1, y_2\} = \{1, 3\}$, another $2$ ordered assignments.
4
The prime choices are independent, so the count is $2 \cdot 2 = 4$. (For example $(a,b) = (2\cdot5^3,\ 2^3\cdot5) = (250, 40)$ is one such pair.)

Answer:

$4$

Olympiad / Challenge

Prove that $\gcd(2^a - 1,\ 2^b - 1) = 2^{\gcd(a,b)} - 1$ for positive integers $a, b$.

1
Assume WLOG $a \ge b$ and run the Euclidean algorithm on the exponents. Key identity: $2^a - 1 = 2^{a-b}(2^b - 1) + (2^{a-b} - 1)$, so $(2^a - 1) \bmod (2^b - 1) = 2^{a \bmod b} - 1$.
2
This mirrors the Euclidean step exactly: $\gcd(2^a - 1, 2^b - 1) = \gcd(2^b - 1,\ 2^{a \bmod b} - 1)$, replacing the exponent pair $(a,b)$ by $(b, a \bmod b)$.
3
Iterating, the exponents follow the ordinary Euclidean algorithm on $(a, b)$, terminating when one exponent reaches $\gcd(a, b)$ and the other reaches $0$ (with $2^0 - 1 = 0$).
4
The last nonzero value is $2^{\gcd(a,b)} - 1$, which is therefore the gcd.

Answer:

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

Going Deeper

Generalization: prime by prime, $\gcd$ takes the minimum exponent and $\operatorname{lcm}$ the maximum, and $\min + \max = $ sum gives $\gcd \cdot \operatorname{lcm} = ab$ (for positive $a,b$). The substitution $a = g x$, $b = g y$ with $g = \gcd(a,b)$ and $\gcd(x,y) = 1$ turns most gcd/lcm problems into a coprime counting problem.
Where it appears: counting pairs with prescribed gcd and lcm, simplifying $\gcd(a^m - 1, a^n - 1) = a^{\gcd(m,n)} - 1$ (and the analogous Fibonacci/Mersenne identities), and reducing fractions to lowest terms in algebra.
Pitfall: the identity $\gcd \cdot \operatorname{lcm} = ab$ holds for two numbers only — it FAILS for three or more (for $a,b,c$ you need an inclusion–exclusion of pairwise gcds). Also it requires $a, b > 0$; sign conventions break it for negatives.

Spot the Signal

Look for problems where the key step is using greatest common divisors and least common multiples to organize integer constraints.
You can describe the hard part as using greatest common divisors and least common multiples to organize integer constraints, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for gcd and lcm, then rewrite the givens around it.
Name the relation that makes GCD and LCM legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use GCD and LCM just because the surface looks familiar; verify the required condition first.
Applying GCD and LCM because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let gcd and lcm reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using greatest common divisors and least common multiples to organize integer constraints.