Difference between revisions of "Prime factorization is unique"
(Created page with "'''Prime factorization is unique''' is, in the context of the integers, part of the fundamental theorem of arithmetic. But the claim can be proven more generally in the context of abstract algebra. The uniqueness here refers to uniqueness except for multiplication with a unit. In the case of the integers the units are <math>1</math> and <math>-1</math>, so <math>6=2\cdot 3 = (-2)\cdot (-3)</math> is considered a unique factorization even though <math>-2, -3</math> als...") |
m (slight restructuring) |
||
| Line 1: | Line 1: | ||
'''Prime factorization is unique''' is, in the context of the integers, part of the fundamental theorem of arithmetic. But the claim can be proven more generally in the context of abstract algebra | '''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== | ==Proof== | ||
===Integers=== | ===Integers=== | ||
Let <math>a</math> be an integer and | Let <math>a</math> be an integer and | ||
<math>a= p_1\cdot\text{ . . . }\cdot p_r = \left(-1\right)^l q_1\cdot\text{ . . . }\cdot q_s </math> | <math>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>a</math>. | two prime factorizations of <math>a</math> where <math>k\text{, } l</math> are either <math>0</math> or <math>1</math>. | ||
The prime factor <math>p_1</math> on the left divides the product | The prime factor <math>p_1</math> on the left divides the product | ||
<math>\left(-1\right)^l q_1\cdot\text{ . . . }\cdot q_s </math> | <math>\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]]) | on the right, so according to Euclid's lemma ([[If a prime divides a product it divides one of the factors]]) | ||
<math>p_1</math> divides one of the factors <math>q_i</math> | <math>p_1</math> divides one of the factors <math>q_i</math> | ||
(no prime divides <math>\pm 1</math>). | (no prime divides <math>\pm 1</math>). | ||
So <math>p_1 = | So <math>p_1 = q_i</math> . | ||
If we change the order of the <math>q_1\text{, . . . , }q_s</math> | If we change the order of the <math>q_1\text{, . . . , }q_s</math> | ||
we can assume <math>p_1 = q_1</math> | we can assume <math>p_1 = q_1</math> | ||
and after | and after dividing by <math>p_1</math> on both sides we get | ||
<math>p_2\cdot\text{ . . . }\cdot p_r = \left(-1\right)^{l | <math>\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>r=s</math> and that, after reordering, <math>p_1= | By repeating this procedure we can see that <math>r=s</math>, <math>k=l</math> and that, after reordering, <math>p_1= q_1\text{, . . . , }p_r= q_r</math>. | ||
===Integral domains=== | ===Integral domains=== | ||
The same proof as above also works generaly for an integral domain with a few tweaks. | The same proof as above also works generaly for an integral domain with a few tweaks. | ||
property [[If a prime divides a product it divides one of the factors]] | 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>1</math> and <math>-1</math>, | |||
so <math>6=2\cdot 3 = (-2)\cdot (-3)</math> is still considered a unique prime factorization | |||
even though <math>-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>ax=ay\Rightarrow ax-ay=0\Rightarrow a(x-y)=0\Rightarrow x=y</math> if <math>a\neq 0</math>, since there can be no zero-divisors in an integral domain apart from <math>0</math> itself. | |||
{{Claim | {{Claim | ||
Latest revision as of 18:48, 24 January 2022
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.
| Statement of the claim | Prime factorization is unique |
| Level of certainty | Proven |
| Nature | Theoretical |
| Counterclaim | |
| Dependent on | |
| Dependency of |
|