Prove that prime factors cannot hide inside a product

Try

The number 180 can be split as 18·10 or 12·15, but both paths lead to 2²·3²·5. This agreement is a theorem, not an accident of small numbers. First separate existence from uniqueness. Strong induction supplies a product of primes for every integer greater than one. To show that different splitting paths lead to the same prime multiset, we need a prime-divisibility argument.

Predict

Predict why the statement “a divides bc, so a divides b or c” is false for composite a. Six divides 2·3 but divides neither factor. A prime has only two positive divisors, and that restriction connects to Bézout. If prime p does not divide b, then gcd(p, b)=1, allowing cancellation from p|bc to p|c. This is Euclid’s lemma.

Experiment

Use prime exponents to compare products.

Number	Exponent of 2	Exponent of 3	Exponent of 5
12	2	1	0
15	0	1	1
180	2	2	1

The exponents add under multiplication. Use the same table idea to find gcd(12, 18) by minimum exponents and lcm(12, 18) by maximum exponents, then verify their product is 12·18.

Understand

For uniqueness, suppose two prime products represent the same positive integer. The first prime on one side divides the entire product on the other. Repeated Euclid’s lemma shows it divides some prime there, so the two primes are equal. Cancel that factor and repeat, with induction supplying a formal termination argument. For negative integers include a sign; units ±1 are not primes. Define v_p(n) for nonzero n as the exponent of p in its factorization. Then v_p(ab)=v_p(a)+v_p(b), divisibility corresponds to componentwise exponent inequalities, and gcd/lcm use minima/maxima. These consequences now follow from proved uniqueness rather than being smuggled into its proof.

Prove the coordinate rules, rather than just reading a table

For positive integers 72=2³·3² and 90=2·3²·5, a common divisor can use at most one factor of two, two factors of three and no factor of five. Thus gcd=18. A common multiple must supply at least three twos, two threes and one five, giving lcm=360. Check 18·360=72·90.

For a nonempty finite family of positive integers, let vₚ(n) denote the exponent of prime p in n. Unique factorization proves d divides n exactly when every prime exponent of d is at most the corresponding exponent of n. Set the gcd coordinates to the minima over the family. The constructed integer divides every operand, and every common divisor divides it. These are the two defining properties of the greatest common divisor. Similarly, coordinatewise maxima construct a common multiple that divides every common multiple, proving the least-common-multiple rule. Only finitely many coordinates are nonzero. For two operands, min(x,y)+max(x,y)=x+y proves gcd(a,b)·lcm(a,b)=ab. Do not assert this two-operand product identity unchanged for three operands.

Which identities survive a change of base?

Before changing the case, predict whether the base can divide a product or least common multiple without dividing either operand. Compare its prime-coordinate requirements.

Operand and base case Ordinary prime coordinatesComposite base splits across factorsComposite prime power has a carryTwo constraints in base twelveUnit boundary Reset

a=72, b=90; gcd=18, lcm=360. The chosen divisibility base is 3.

Prime p	vₚ(a)	vₚ(b)	vₚ(gcd)	vₚ(lcm)	Exponent in base
2	3	1	1	3	0
3	2	2	2	2	1
5	0	1	0	1	0

Whole powers of base 3 dividing a and b: 2 and 2. The count for their product is 4, versus the proposed sum 4.

For their gcd: 2, equal to the minimum 2. For their lcm: 2, versus the proposed maximum 2.

One equality in a selected example does not prove a general identity. Explain the bottleneck coordinate, then use the proofs below. These five positive-integer cases are temporary exploration, not evidence of independently demonstrated understanding.

A composite base has several bottlenecks

For an integer base B greater than one, define w_B(n) as the greatest nonnegative integer k for which Bᵏ divides the positive integer n. If B has prime factorization ∏pᵉ, then Bᵏ divides n exactly when ke is at most vₚ(n) for each prime dividing B. Therefore w_B(n) is the minimum of floor(vₚ(n)/e) over those primes. The floor is the greatest integer no larger than its argument.

This formula explains two distinct failures. For B=6, a=2 and b=3, each operand has w=0 but their product and lcm both have w=1: different operands supply different missing coordinates. For B=4 and a=b=2, the product again has w=1 although both counts are zero, now because two leftover prime factors combine into a whole base. In this second example the lcm remains 2, with w=0. A counterexample to additivity need not also refute the lcm rule.

However, w_B(gcd(a,b))=min(w_B(a),w_B(b)) remains true for every B. For any k, Bᵏ divides the gcd exactly when it divides both operands, so the admissible k run from zero through the smaller of the two maxima. The same argument works for every nonempty finite positive family. Prime bases retain both product additivity and the lcm maximum law because there is a single coordinate and no division/flooring.

Repair the zero and infinite-family boundaries

Every power of a prime divides zero, so no greatest finite exponent exists there. One may explicitly define vₚ(0)=∞ and use gcd(0,n)=n and lcm(0,n)=0, with gcd(0,0)=lcm(0,0)=0. Minima/maxima then give the corresponding extended coordinates. This is a declared convention; the finite positive-integer inspector does not silently accept zero.

A nonempty infinite family of positive integers still has a gcd: choose one operand a. All common divisors belong to the finite divisor set of a. Equivalently, coordinate minima exist and their nonzero support is contained in the finite support of a. An integer common multiple exists only if the coordinate suprema are finite and nonzero for only finitely many primes; then their product is the lcm. Necessity follows because a common multiple would bound every coordinate and contain every occurring prime. Sufficiency follows by constructing that finite product. The family 2, 4, 8, … fails because its two-exponents are unbounded. The family of all primes has bounded exponents in each coordinate but infinitely many nonzero coordinates, so it also has no positive integer lcm. An unrestricted “take maxima and multiply” argument misses this second obstruction.

Apply

Euclid’s infinitude argument assumes a finite complete list p₁,…, p_k and forms N=p₁⋯p_k+1. N need not be prime. Any prime divisor q of N is absent from the list because a listed divisor would also divide N−p₁⋯p_k=1. A related construction proves infinitely many primes congruent to three modulo four: N=4p₁⋯p_k−1 has that residue, and its odd prime factorization must contain a prime with residue three modulo four an odd number of times. No listed prime divides N. This is a special progression argument, not a proof of the general theorem on primes in every coprime arithmetic progression.

Continue

Prime factorizations are powerful certificates once supplied, but finding them efficiently for a huge integer is a different computational problem. Trial division needs only primes up to the square root to certify primality, since a composite number has a factor no larger than its square root. That elementary bound does not make trial division practical at arbitrary size. Next, gcd information will classify all integer solutions of a linear equation, including the cases where no solution exists.

Return to the number theory unit to choose a targeted retry. Continue with find every integer solution, not just one.