gcd and lcm via Prime Factorization

How can we find the greatest common divisor of two large numbers? We want to do this without listing all their divisors. Suppose we want gcd⁡(2520,1782)\gcd(2520, 1782). Trial division through dozens of candidates is slow and error-prone. Yet the Fundamental Theorem of Arithmetic hands us a shortcut. Every integer decomposes uniquely into primes. Divisibility is completely governed by comparing prime exponents. This turns a search problem into simple arithmetic on exponents. We take minimums for the gcd, maximums for the lcm. This idea matters because it converts an apparently combinatorial question. That question is: "what numbers divide both aa and bb?" It becomes a coordinate-wise comparison instead. This is much like comparing vectors of exponents in a lattice. It reveals gcd and lcm not as ad hoc constructions. Instead they are the meet and join operations of a natural order structure. This structure exists on the positive integers, where a∣ba \mid b plays the role of a≤ba \le b. This perspective anticipates later structures in algebra. These include lattices and partially ordered sets, as well as number theory. The big picture is that prime factorization is the "Rosetta Stone" of multiplicative number theory. Once a number is written as ∏pep\prod p^{e_p}, almost every multiplicative question about it becomes simpler. This includes number of divisors, sum of divisors, gcd, lcm, and eventually Euler's Totient Function. Each becomes a formula in the exponents. The gcd and lcm identities developed here are the first instance of this philosophy. They are also the cleanest instance of it. This article delivers a rigorous definition of gcd and lcm via prime exponents. It gives a complete proof that this matches the classical divisor-based definitions. It also proves the fundamental product identity gcd⁡(a,b)⋅lcm⁡(a,b)=ab\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab. The article includes worked numerical examples. It offers a counterexample showing why the identity needs exactly two arguments. Finally, it discusses where these ideas resurface in modern mathematics and computing.

Key takeaways
  • Every positive integer factors uniquely as a product of prime powers (Fundamental Theorem of Arithmetic).
  • Writing a=∏pepa = \prod p^{e_p}, b=∏pfpb = \prod p^{f_p}, the gcd takes min⁡(ep,fp)\min(e_p,f_p) and the lcm takes max⁡(ep,fp)\max(e_p,f_p) at each prime.
  • This exponent recipe is proven equivalent to the classical "largest common divisor" / "smallest common multiple" definitions.
  • The identity gcd⁡(a,b)⋅lcm⁡(a,b)=ab\gcd(a,b)\cdot\operatorname{lcm}(a,b) = ab follows because min⁡(x,y)+max⁡(x,y)=x+y\min(x,y)+\max(x,y) = x+y for all reals.
  • The identity fails for three or more numbers in the naive generalization — a genuine trap worth checking carefully.
  • Key idea: divisibility is a coordinate-wise order on exponent vectors, and gcd/lcm are literally the min and max in that order.

Where this lives today

The exponent-vector viewpoint on gcd and lcm reappears throughout mathematics and its applications. In algebra, it is the prototype example of a lattice: the positive integers under divisibility form a lattice where gcd is the meet and lcm is the join, a structure generalized in ring theory to greatest common divisor domains and unique factorization domains. In combinatorics and computer science, lcm computations underlie scheduling problems (finding when repeating events next coincide) and modular arithmetic routines used in hashing and error-correcting codes. In cryptography, understanding gcd/lcm and coprimality via prime structure is conceptually prerequisite to RSA key generation, where lcm⁡(p−1,q−1)\operatorname{lcm}(p-1,q-1) (the Carmichael function) refines Euler's totient in exponent computations — directly foreshadowing Euler's Totient Function, whose formula φ(n)=n∏p∣n(1−1/p)\varphi(n) = n\prod_{p\mid n}(1-1/p) is proven by exactly the same exponent-counting technique used here. In numerical software, the exponent-based formulas are used symbolically (e.g., in computer algebra systems) whenever exact factorizations are already available, while the Euclidean algorithm remains the default for raw numerical gcd computation because it avoids the cost of factoring.

Ask the tutor: How does this exponent method extend to prove the formula for the number and sum of divisors of nn, and eventually Euler's totient function?

Definitiongcd and lcm from prime factorizations

Let a,ba, b be positive integers. By the Fundamental Theorem of Arithmetic, write

a=∏ppep,b=∏ppfp,a = \prod_{p} p^{e_p}, \qquad b = \prod_{p} p^{f_p},

where the product ranges over all primes pp, and ep,fp≥0e_p, f_p \ge 0 are integers, all but finitely many equal to zero (so the products are finite). Define

gcd⁡(a,b):=∏ppmin⁡(ep,fp),lcm⁡(a,b):=∏ppmax⁡(ep,fp).\gcd(a,b) := \prod_{p} p^{\min(e_p, f_p)}, \qquad \operatorname{lcm}(a,b) := \prod_{p} p^{\max(e_p, f_p)}.

More generally, for finitely many positive integers a1,…,ana_1, \dots, a_n with ai=∏ppei,pa_i = \prod_p p^{e_{i,p}},

gcd⁡(a1,…,an):=∏ppmin⁡iei,p,lcm⁡(a1,…,an):=∏ppmax⁡iei,p.\gcd(a_1,\dots,a_n) := \prod_p p^{\min_i e_{i,p}}, \qquad \operatorname{lcm}(a_1,\dots,a_n) := \prod_p p^{\max_i e_{i,p}}.

(By convention gcd⁡(0,0)\gcd(0,0) and similar degenerate cases involving 00 are treated separately and are not covered by this exponent formula, which applies to positive integers.)

Intuition

Think of each positive integer as an infinite vector of exponents, one coordinate per prime, with all but finitely many coordinates equal to 00. For instance 2520=23⋅32⋅51⋅712520 = 2^3\cdot 3^2\cdot 5^1\cdot 7^1 corresponds to the vector (3,2,1,1,0,0,… )(3,2,1,1,0,0,\dots) indexed by the primes 2,3,5,7,11,…2,3,5,7,11,\dots. Divisibility a∣ba \mid b means precisely that every coordinate of aa's vector is ≤\le the corresponding coordinate of bb's vector — this is exactly The Greatest Common Divisor reformulated as a partial order. Once divisibility becomes "coordinate-wise ≤\le," the gcd is the largest vector that is ≤\le both aa and bb in every coordinate — which is obviously the coordinate-wise minimum. Symmetrically the lcm, being the smallest common multiple, is the coordinate-wise maximum. This is the same logic as taking the meet and join of two points in a grid ordered by coordinates: the meet drops down to the lower envelope, the join rises to the upper envelope.

Figure
Exponent vectors for 2520=23⋅32⋅5⋅72520 = 2^3\cdot3^2\cdot5\cdot7 and 1782=2⋅34⋅111782 = 2\cdot3^4\cdot11, showing min/max per prime
Prime exponent comparison a = 2520 = 2^3 · 3^2 · 5^1 · 7^1 b = 1782 = 2^1 · 3^4 · 5^0 · 7^0 · 11^1 p=2 p=3 p=5 p=7 p=11 min=1,max=3 min=2,max=4 min=0,max=1 min=0,max=1 min=0,max=1 blue = exponent in a orange = exponent in b

Worked examples (below) will confirm numerically that this picture gives gcd⁡=2⋅32=18\gcd = 2\cdot3^2 = 18 and lcm⁡=23⋅34⋅5⋅7⋅11=249480\operatorname{lcm} = 2^3\cdot3^4\cdot5\cdot7\cdot11 = 249480, and that their product equals 2520×17822520 \times 1782.

TheoremEquivalence of definitions, and the gcd–lcm product identity

Let a,ba,b be positive integers with prime factorizations a=∏ppepa = \prod_p p^{e_p}, b=∏ppfpb = \prod_p p^{f_p} (finitely many nonzero exponents).

(1) Equivalence. The number d:=∏ppmin⁡(ep,fp)d := \prod_p p^{\min(e_p,f_p)} is the greatest common divisor of a,ba,b in the classical sense: d∣ad \mid a, d∣bd \mid b, and every common divisor of a,ba,b divides dd. The number m:=∏ppmax⁡(ep,fp)m := \prod_p p^{\max(e_p,f_p)} is the least common multiple of a,ba,b in the classical sense: a∣ma \mid m, b∣mb \mid m, and mm divides every common multiple of a,ba,b.

(2) Product identity. For all positive integers a,ba,b,

gcd⁡(a,b)⋅lcm⁡(a,b)=ab.\gcd(a,b)\cdot \operatorname{lcm}(a,b) = ab.
Proof

We use the technique of reduction to prime exponents via unique factorization, together with the elementary fact that for any two integers x,yx,y,

min⁡(x,y)+max⁡(x,y)=x+y.(∗)\min(x,y) + \max(x,y) = x+y. \tag{$\ast$}

This identity is immediate: if x≤yx \le y then min⁡(x,y)=x\min(x,y)=x, max⁡(x,y)=y\max(x,y)=y, and the sum is x+yx+y; if y≤xy \le x the roles swap but the sum is unchanged.

Step 0 (Divisibility in terms of exponents). First we establish: for positive integers n=∏ppgpn = \prod_p p^{g_p} and k=∏pphpk = \prod_p p^{h_p},

k∣n  ⟺  hp≤gp for every prime p.k \mid n \iff h_p \le g_p \text{ for every prime } p.

(⇐\Leftarrow) If hp≤gph_p \le g_p for all pp, then n/k:=∏ppgp−hpn/k := \prod_p p^{g_p - h_p} is a positive integer (all exponents ≥0\ge 0), and k⋅(n/k)=∏pphp+(gp−hp)=∏ppgp=nk \cdot (n/k) = \prod_p p^{h_p + (g_p-h_p)} = \prod_p p^{g_p} = n, so k∣nk \mid n. (⇒\Rightarrow) Suppose k∣nk \mid n, say n=kqn = k q for a positive integer qq. Write q=∏ppipq = \prod_p p^{i_p} by unique factorization (existence part of the Fundamental Theorem of Arithmetic). Then n=kq=∏pphp+ipn = kq = \prod_p p^{h_p + i_p}. But also n=∏ppgpn = \prod_p p^{g_p}. By the uniqueness part of the Fundamental Theorem of Arithmetic, the exponent of each prime in a factorization of nn is uniquely determined, so gp=hp+ipg_p = h_p + i_p for every pp. Since ip≥0i_p \ge 0, we get hp≤gph_p \le g_p for every pp. This proves Step 0.

Step 1 (d∣ad \mid a and d∣bd \mid b). By definition d=∏ppmin⁡(ep,fp)d = \prod_p p^{\min(e_p,f_p)}. Since min⁡(ep,fp)≤ep\min(e_p,f_p) \le e_p for every pp, Step 0 gives d∣ad \mid a. Since min⁡(ep,fp)≤fp\min(e_p,f_p) \le f_p for every pp, Step 0 gives d∣bd \mid b. So dd is a common divisor of aa and bb.

Step 2 (Maximality of dd among common divisors). Let cc be any common divisor of aa and bb, and write c=∏ppcpc = \prod_p p^{c_p}. By Step 0, c∣ac \mid a forces cp≤epc_p \le e_p for all pp, and c∣bc \mid b forces cp≤fpc_p \le f_p for all pp. Hence cp≤min⁡(ep,fp)c_p \le \min(e_p,f_p) for all pp. By Step 0 again (applied in the other direction), this means c∣dc \mid d. In particular c≤dc \le d (a divisor of a positive integer does not exceed it), so dd is indeed the greatest common divisor, and moreover every common divisor divides dd. This proves d=gcd⁡(a,b)d = \gcd(a,b) in the classical sense.

Step 3 (lcm, symmetric argument). By definition m=∏ppmax⁡(ep,fp)m = \prod_p p^{\max(e_p,f_p)}. Since ep≤max⁡(ep,fp)e_p \le \max(e_p,f_p), Step 0 gives a∣ma \mid m; similarly b∣mb \mid m, so mm is a common multiple of aa and bb. Now let MM be any common multiple of a,ba,b, with M=∏ppMpM = \prod_p p^{M_p}. By Step 0, a∣Ma \mid M forces ep≤Mpe_p \le M_p for all pp, and b∣Mb \mid M forces fp≤Mpf_p \le M_p for all pp, hence max⁡(ep,fp)≤Mp\max(e_p,f_p) \le M_p for all pp. By Step 0 again, m∣Mm \mid M. Thus mm divides every common multiple, and in particular m≤Mm \le M for every positive common multiple MM, so mm is the least common multiple. This proves m=lcm⁡(a,b)m = \operatorname{lcm}(a,b) in the classical sense, completing the proof of part (1).

Step 4 (Product identity). Using the definitions and part (1),

gcd⁡(a,b)⋅lcm⁡(a,b)=(∏ppmin⁡(ep,fp))(∏ppmax⁡(ep,fp))=∏ppmin⁡(ep,fp)+max⁡(ep,fp).\gcd(a,b)\cdot \operatorname{lcm}(a,b) = \left(\prod_p p^{\min(e_p,f_p)}\right)\left(\prod_p p^{\max(e_p,f_p)}\right) = \prod_p p^{\min(e_p,f_p) + \max(e_p,f_p)}.

By (∗)(\ast), applied prime by prime, min⁡(ep,fp)+max⁡(ep,fp)=ep+fp\min(e_p,f_p) + \max(e_p,f_p) = e_p + f_p for every pp. Hence

gcd⁡(a,b)⋅lcm⁡(a,b)=∏ppep+fp=(∏ppep)(∏ppfp)=ab.\gcd(a,b)\cdot \operatorname{lcm}(a,b) = \prod_p p^{e_p+f_p} = \left(\prod_p p^{e_p}\right)\left(\prod_p p^{f_p}\right) = ab.

This is a finite product (all but finitely many exponents on both sides vanish), so all manipulations are legitimate operations on finite products of integers. ■\blacksquare

∎

Worked examples

Example 1: gcd⁡\gcd and lcm⁡\operatorname{lcm} of 25202520 and 17821782 (asymmetric, multi-prime). First factor both numbers completely.

2520=23⋅32⋅5⋅7,1782=2⋅34⋅11.2520 = 2^3 \cdot 3^2 \cdot 5 \cdot 7, \qquad 1782 = 2 \cdot 3^4 \cdot 11.

(Check: 23⋅32⋅5⋅7=8⋅9⋅35=8⋅315=25202^3\cdot3^2\cdot5\cdot7 = 8\cdot9\cdot35 = 8\cdot315 = 2520. And 2⋅34⋅11=2⋅81⋅11=2⋅891=17822\cdot3^4\cdot11 = 2\cdot81\cdot11 = 2\cdot891=1782.) List every prime appearing in either factorization: 2,3,5,7,112,3,5,7,11. Their exponents:

primeexponent in 25202520exponent in 17821782min⁡\minmax⁡\max
2233111133
3322442244
5511000011
7711000011
111100110011

By the theorem,

gcd⁡(2520,1782)=21⋅32=2⋅9=18,\gcd(2520,1782) = 2^1\cdot3^2 = 2\cdot9 = 18,
lcm⁡(2520,1782)=23⋅34⋅51⋅71⋅111=8⋅81⋅5⋅7⋅11.\operatorname{lcm}(2520,1782) = 2^3\cdot3^4\cdot5^1\cdot7^1\cdot11^1 = 8\cdot81\cdot5\cdot7\cdot11.

Compute step by step: 8⋅81=6488\cdot81 = 648; 648⋅5=3240648\cdot5=3240; 3240⋅7=226803240\cdot7 = 22680; 22680⋅11=24948022680\cdot11 = 249480. So lcm⁡(2520,1782)=249480\operatorname{lcm}(2520,1782) = 249480. Check the product identity: 2520⋅1782=4 490 6402520 \cdot 1782 = 4\,490\,640 (since 2520⋅1782=2520⋅1800−2520⋅18=4 536 000−45 360=4 490 6402520\cdot1782 = 2520\cdot1800 - 2520\cdot18 = 4\,536\,000 - 45\,360 = 4\,490\,640). And gcd⁡⋅lcm⁡=18⋅249480\gcd \cdot \operatorname{lcm} = 18 \cdot 249480. Compute 18⋅249480=249480⋅18=249480⋅20−249480⋅2=4 989 600−498 960=4 490 64018\cdot249480 = 249480\cdot18 = 249480\cdot20 - 249480\cdot2 = 4\,989\,600 - 498\,960 = 4\,490\,640. The two match exactly, confirming both the factorizations and the identity.

Example 2: three numbers, and why gcd⁡⋅lcm⁡≠\gcd\cdot\operatorname{lcm}\ne product in general. Let a=22⋅3=12a = 2^2\cdot 3 = 12, b=2⋅32=18b = 2\cdot 3^2 = 18, c=23⋅33=216c = 2^3\cdot 3^3 = 216. Exponents at p=2p=2: 2,1,32,1,3; at p=3p=3: 1,2,31,2,3.

gcd⁡(a,b,c)=2min⁡(2,1,3)⋅3min⁡(1,2,3)=21⋅31=6,\gcd(a,b,c) = 2^{\min(2,1,3)}\cdot 3^{\min(1,2,3)} = 2^1\cdot3^1 = 6,
lcm⁡(a,b,c)=2max⁡(2,1,3)⋅3max⁡(1,2,3)=23⋅33=216.\operatorname{lcm}(a,b,c) = 2^{\max(2,1,3)}\cdot3^{\max(1,2,3)} = 2^3\cdot3^3 = 216.

Now gcd⁡(a,b,c)⋅lcm⁡(a,b,c)=6⋅216=1296\gcd(a,b,c)\cdot\operatorname{lcm}(a,b,c) = 6\cdot216 = 1296, while abc=12⋅18⋅216=46656abc = 12\cdot18\cdot216 = 46656. These are not equal — confirming that the clean two-variable identity genuinely requires exactly two arguments (see the counterexample below for the underlying reason). As a sanity check on pairwise gcd/lcm computations feeding into this: gcd⁡(a,b)=gcd⁡(12,18)\gcd(a,b) = \gcd(12,18). Exponents at 22: 2,1⇒min⁡=12,1\Rightarrow\min=1; at 33: 1,2⇒min⁡=11,2\Rightarrow\min=1. So gcd⁡(12,18)=2⋅3=6\gcd(12,18)=2\cdot3=6, matching direct computation (12=2⋅6,18=3⋅612=2\cdot6, 18=3\cdot6, and gcd⁡(2,3)=1\gcd(2,3)=1). Good, consistent.

Counterexamplewhy the identity needs exactly two arguments

The theorem's product identity gcd⁡(a,b)⋅lcm⁡(a,b)=ab\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab uses the single-variable algebraic fact (∗)(\ast): min⁡(x,y)+max⁡(x,y)=x+y\min(x,y)+\max(x,y) = x+y. This is special to two numbers. For three or more numbers there is no identity u1+u2+u3=min⁡(u1,u2,u3)+max⁡(u1,u2,u3)u_1+u_2+u_3 = \min(u_1,u_2,u_3)+\max(u_1,u_2,u_3) in general — the "middle" value is lost. Concretely, take u1=1,u2=2,u3=3u_1=1, u_2=2, u_3=3 (exponents of a single prime across three numbers). Then min⁡=1\min = 1, max⁡=3\max = 3, and min⁡+max⁡=4\min+\max = 4, but u1+u2+u3=6≠4u_1+u_2+u_3 = 6 \ne 4. This is exactly the phenomenon behind Example 2 above: dropping the hypothesis "exactly two integers" and naively asking whether

gcd⁡(a1,…,an)⋅lcm⁡(a1,…,an)=a1a2⋯an\gcd(a_1,\dots,a_n)\cdot\operatorname{lcm}(a_1,\dots,a_n) = a_1a_2\cdots a_n

holds for n≥3n \ge 3 produces a false statement, witnessed by a=12, b=18, c=216a=12,\ b=18,\ c=216 above (1296≠466561296 \ne 46656). The correct three-variable relationship instead requires inclusion–exclusion over all pairwise and triple gcd's (e.g. gcd⁡(a,b,c)⋅lcm⁡(a,b)⋅lcm⁡(b,c)⋅lcm⁡(a,c)⋅ abc=lcm⁡(a,b,c)⋅gcd⁡(a,b)gcd⁡(b,c)gcd⁡(a,c)⋅abc\gcd(a,b,c)\cdot\operatorname{lcm}(a,b)\cdot\operatorname{lcm}(b,c)\cdot\operatorname{lcm}(a,c) \cdot \, abc= \operatorname{lcm}(a,b,c)\cdot \gcd(a,b)\gcd(b,c)\gcd(a,c)\cdot abc-type identities, which are considerably more delicate), and is genuinely a different, more advanced statement — not covered by this theorem.

Scope, edge cases & common traps

SituationWhat happensWhy
n≥3n \ge 3 numbersgcd⁡⋅lcm⁡≠\gcd\cdot\operatorname{lcm} \ne product, in generalmin⁡+max⁡≠\min+\max\ne sum for ≥3\ge 3 values (see counterexample)
One argument is 00Formula needs separate convention: gcd⁡(a,0)=a\gcd(a,0)=a, lcm⁡(a,0)=0\operatorname{lcm}(a,0)=0Prime factorization is defined only for positive integers; 00 has no factorization
a=ba=bgcd⁡(a,a)=a=lcm⁡(a,a)\gcd(a,a)=a=\operatorname{lcm}(a,a)min⁡(ep,ep)=max⁡(ep,ep)=ep\min(e_p,e_p)=\max(e_p,e_p)=e_p
gcd⁡(a,b)=1\gcd(a,b)=1 (coprime)lcm⁡(a,b)=ab\operatorname{lcm}(a,b)=ab exactlyNo shared primes, so min⁡\min is always 00, forcing product identity to read 1⋅lcm⁡=ab1\cdot\operatorname{lcm}=ab
Negative integersUsually define gcd⁡(a,b):=gcd⁡(∣a∣,∣b∣)\gcd(a,b):=\gcd(|a|,|b|)Factorization theorem stated for positive integers; sign is handled separately by convention

The mathematician behind it

Origins · 1 minCarl Friedrich Gauss and how this was discovered
CF
Carl Friedrich Gauss
1777–1855 · Göttingen, foundational work in number theory

Gauss did not invent gcd or lcm — Euclid's algorithm for the gcd predates him by two millennia — but his 1801 treatise Disquisitiones Arithmeticae gave the Fundamental Theorem of Arithmetic its first fully rigorous proof and organized divisibility theory into the systematic, modular framework still used today. The exponent-based viewpoint on gcd and lcm presented here is a direct, modern consequence of the unique factorization theorem that Gauss placed on rigorous footing, turning what Euclid handled via subtraction algorithms into an algebraic statement about prime exponents.

History
- c. 300 BCE — Euclid's Elements (Book VII) gives the subtractive algorithm for computing the greatest common divisor, without reference to prime factorization.
- 1801 — Gauss's Disquisitiones Arithmeticae gives a rigorous proof of unique factorization, providing the theoretical basis for the exponent-vector viewpoint on gcd/lcm.
- 1830s–1840s — number theorists including Dirichlet formalize multiplicative functions of divisors, of which gcd/lcm-via-exponents is a foundational instance.
- 20th century — the exponent-vector and lattice-theoretic view of divisibility becomes standard in algebraic number theory and abstract algebra (divisibility as a partial order, gcd/lcm as meet/join).
- 1960s onward — the Euclidean algorithm (not factorization) becomes the computational method of choice for large integers, since factoring is far more expensive than Euclid's method — an important practical counterpoint to the elegant but computationally costly exponent approach.
Why does min⁡\min correspond to gcd and not max⁡\max?

Because the gcd must divide both numbers, and by the exponent-divisibility criterion (Step 0 in the proof), a prime power pkp^k divides n=∏pgpn=\prod p^{g_p} exactly when k≤gpk \le g_p. To divide both aa and bb, the exponent of each prime in the candidate divisor must be ≤\le both epe_p and fpf_p simultaneously — that is, ≤min⁡(ep,fp)\le \min(e_p,f_p). Taking the exponent equal to this minimum, for every prime, gives the largest number satisfying that constraint, which is precisely the greatest common divisor. Using max⁡\max instead would generally fail to divide one of the two numbers.

Why does max⁡\max correspond to lcm and not min⁡\min?

The lcm must be a multiple of both aa and bb, so its exponent at each prime must be ≥\ge both epe_p and fpf_p, i.e. ≥max⁡(ep,fp)\ge \max(e_p,f_p). The smallest number meeting this requirement at every prime uses exactly the maximum exponent at each prime — any smaller exponent at some prime would fail to be a multiple of whichever number has that larger exponent. Hence lcm is built from componentwise maxima, the mirror image of the gcd construction.

Does the product identity generalize to gcd⁡(a,b,c)⋅lcm⁡(a,b,c)=abc\gcd(a,b,c)\cdot \operatorname{lcm}(a,b,c) = abc for three numbers?

No, and this is a very common error. The proof of the two-variable identity relies on the algebraic fact min⁡(x,y)+max⁡(x,y)=x+y\min(x,y)+\max(x,y)=x+y, which is false in general for three numbers: e.g. exponents 1,2,31,2,3 give min⁡+max⁡=1+3=4≠6=1+2+3\min+\max = 1+3=4 \ne 6 = 1+2+3. A concrete numeric counterexample is a=12, b=18, c=216a=12,\,b=18,\,c=216, where gcd⁡⋅lcm⁡=1296\gcd\cdot\operatorname{lcm}=1296 but abc=46656abc=46656. The correct multi-variable relationships require more elaborate inclusion–exclusion formulas over subsets of the numbers.

How does this relate to the Euclidean algorithm for computing gcd?

The Euclidean algorithm computes gcd⁡(a,b)\gcd(a,b) via repeated division without ever factoring aa or bb, and is far more efficient for large numbers since factoring is computationally expensive (no known polynomial-time algorithm factors arbitrary integers efficiently on classical computers). The prime-exponent method described here is conceptually illuminating — it explains why gcd and lcm behave the way they do — but is a poor practical algorithm for large inputs. In practice, one uses Euclid's algorithm to compute gcd⁡(a,b)\gcd(a,b) and then recovers lcm⁡(a,b)\operatorname{lcm}(a,b) from the identity lcm⁡(a,b)=ab/gcd⁡(a,b)\operatorname{lcm}(a,b)=ab/\gcd(a,b), avoiding factorization entirely.

What happens if one of the numbers is 00?

Prime factorization is defined only for positive integers, so the exponent formulas in this article do not directly apply when an argument is 00. By convention, gcd⁡(a,0)=a\gcd(a,0) = a for any positive integer aa (since every integer divides 00, and the largest common divisor of aa and 00 is aa itself), while lcm⁡(a,0)\operatorname{lcm}(a,0) is usually defined as 00 (or left undefined, depending on convention), since 00 is the only common multiple that is itself a multiple of 00. These edge cases are handled separately from the theorem stated here, which assumes a,ba,b positive.

Is this exponent-based view related to lattice theory?

Yes. The positive integers under the divisibility relation ∣\mid form a partially ordered set, and in fact a lattice: any two elements a,ba,b have a well-defined meet (gcd⁡(a,b)\gcd(a,b), the greatest lower bound under divisibility) and join (lcm⁡(a,b)\operatorname{lcm}(a,b), the least upper bound). The exponent-vector representation makes this concrete: divisibility becomes coordinate-wise ≤\le on vectors, and meet/join become coordinate-wise min/max, exactly mirroring the lattice structure on Z≥0(∞)\mathbb{Z}_{\ge 0}^{(\infty)} (finitely supported sequences of non-negative integers). This lattice viewpoint generalizes to ideals in more general rings.

Why is uniqueness of factorization essential to this proof, not just existence?

Existence of a factorization lets us write aa and bb as products of primes, but the proof of Step 0 (divisibility   ⟺  \iff exponent comparison) crucially uses uniqueness: when we factor n=kqn = kq into ∏php+ip\prod p^{h_p+i_p}, we need to know that this is the factorization of nn, matching ∏pgp\prod p^{g_p} exponent-by-exponent. Without uniqueness, a number could have two different factorizations with different exponents, and comparing "the" exponents of nn would be meaningless — the whole coordinate-wise comparison breaks down. This is precisely why the Fundamental Theorem of Arithmetic, not merely "existence of factorizations," is the load-bearing prerequisite.

Before this