Prime factorization is unique

From arguably.io
Jump to navigation Jump to search

Prime factorization is unique is, in the context of the integers, part of the fundamental theorem of arithmetic. But the claim can also be proven more generally in the context of abstract algebra.

Proof

Integers

Let [math]\displaystyle{ a }[/math] be an integer and [math]\displaystyle{ a=\left(-1\right)^k\cdot p_1\cdot\text{ . . . }\cdot p_r = \left(-1\right)^l\cdot q_1\cdot\text{ . . . }\cdot q_s }[/math] two prime factorizations of [math]\displaystyle{ a }[/math] where [math]\displaystyle{ k\text{, } l }[/math] are either [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math]. The prime factor [math]\displaystyle{ p_1 }[/math] on the left divides the product [math]\displaystyle{ \left(-1\right)^l\cdot q_1\cdot\text{ . . . }\cdot q_s }[/math] on the right, so according to Euclid's lemma (If a prime divides a product it divides one of the factors) [math]\displaystyle{ p_1 }[/math] divides one of the factors [math]\displaystyle{ q_i }[/math] (no prime divides [math]\displaystyle{ \pm 1 }[/math]). So [math]\displaystyle{ p_1 = q_i }[/math] . If we change the order of the [math]\displaystyle{ q_1\text{, . . . , }q_s }[/math] we can assume [math]\displaystyle{ p_1 = q_1 }[/math] and after dividing by [math]\displaystyle{ p_1 }[/math] on both sides we get [math]\displaystyle{ \left(-1\right)^{k}\cdot p_2\cdot\text{ . . . }\cdot p_r = \left(-1\right)^{l}\cdot q_2\cdot\text{ . . . }\cdot q_s }[/math].

By repeating this procedure we can see that [math]\displaystyle{ r=s }[/math], [math]\displaystyle{ k=l }[/math] and that, after reordering, [math]\displaystyle{ p_1= q_1\text{, . . . , }p_r= q_r }[/math].

Integral domains

The same proof as above also works generaly for an integral domain with a few tweaks. But the uniqueness here refers only to uniqueness except for multiplication with a unit, because in the general case prime elements are just defined by the property If a prime divides a product it divides one of the factors. In the case of the integers for example the units are [math]\displaystyle{ 1 }[/math] and [math]\displaystyle{ -1 }[/math], so [math]\displaystyle{ 6=2\cdot 3 = (-2)\cdot (-3) }[/math] is still considered a unique prime factorization even though [math]\displaystyle{ -2, -3 }[/math] would also be prime elements according to this more general definition. (For integers this relative uniqueness is turned into real uniqueness by requiring prime numbers to be positive). Even though there is generally no division operation available in an integral domain one can still "divide" both sides of an equation in the sense that

[math]\displaystyle{ ax=ay\Rightarrow ax-ay=0\Rightarrow a(x-y)=0\Rightarrow x=y }[/math] if [math]\displaystyle{ a\neq 0 }[/math], since there can be no zero-divisors in an integral domain apart from [math]\displaystyle{ 0 }[/math] itself.
Claim
Statement of the claim Prime factorization is unique
Level of certainty Proven
Nature Theoretical
Counterclaim
Dependent on

If a prime divides a product it divides one of the factors

Dependency of


References