In grade 5 you factored numbers with factor trees, and different trees for the same number always ended with the same primes. That is not an accident, and it is not obvious either. It is a theorem, and its proof rests on Bézout's identity.
The Fundamental Theorem of Arithmetic. Every integer $n > 1$ can be written as a product of primes, and this factorization is unique apart from the order of the factors. We usually group equal primes: $1260 = 2^{2} \cdot 3^{2} \cdot 5 \cdot 7$.
Why uniqueness needs proof: in the even numbers $2, 4, 6, \dots$, call an even number "even-prime" if it is not a product of two even numbers. Then $2$, $6$, $10$ and $30$ are even-prime, and $60 = 2 \cdot 30 = 6 \cdot 10$ has two different factorizations. Something special about the integers prevents this.
Euclid's lemma. If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.
Why it works
Uniqueness. If $p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m$ with all primes, then $p_1$ divides the right side, so (using the lemma again and again) $p_1$ divides some $q_j$, and since $q_j$ is prime, $p_1 = q_j$. Cancel it and repeat. Existence is easier: a number above $1$ is prime or splits into smaller factors, and the splitting must stop.
Worked example: Factoring by division
- Divide by $2$ while you can: $1260 \to 630 \to 315$. That is $2^{2}$.
- Divide by $3$: $315 \to 105 \to 35$. That is $3^{2}$.
- $35 = 5 \cdot 7$.
Answer: $1260 = 2^{2} \cdot 3^{2} \cdot 5 \cdot 7$.
Worked example: Using the exponents
- A number is a perfect square exactly when every exponent in its factorization is even. (This uses uniqueness: there is no other factorization that could have even exponents.)
- In $2^{2} \cdot 3^{2} \cdot 5 \cdot 7$ the odd exponents belong to $5$ and $7$.
- So $k = 5 \cdot 7 = 35$, and $1260 \cdot 35 = 2^{2} \cdot 3^{2} \cdot 5^{2} \cdot 7^{2} = 210^{2}$.
Answer: $k = 35$.
Worked example: The lemma at work
- $6 = 2 \cdot 3$. The factor $2$ is already supplied by $4$.
- $3$ is prime and $3 \mid 4x$ but $3 \nmid 4$, so by Euclid's lemma $3 \mid x$.
- The smallest choice is $x = 3$: $4 \cdot 3 = 12 = 6 \cdot 2$.
Answer: $x = 3$, not $6$.
Common mistake
Key idea