I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
Definition. An integer $p$ is a prime if and only if $p\neq \pm 1$, $p\neq 0$, and, whenever $p|ab$, either $p|a$ or $p|b$. Definition. An integer $n$ is irreducible if and only if $n\neq \pm 1$ and, if $n=ab$ with $a$ and $b$ integers, then either $a=\pm 1$ or $b\pm 1$. Lemma. If $a$ and $b$ are integers, then $a$ and $b$ have a greatest common divisor that can be written as $\alpha a + \beta b$ for some integers $\alpha$ and $\beta$. Proof. Consider the set $I=\{\alpha a + \beta b \mid \alpha,\beta\in\mathbb{Z}\}$. If this set equals $\{0\}$, then $a=b=0$, $\gcd(0,0)=0$, and we can take $\alpha=\beta=1$. If the set is not equal to $0$, then it contains a smallest positive member $d$; if $n$ is any element of the set, then dividing $n$ by $d$ with remainder we have $n = qd + r$, $0\leq r \lt d$. But $qd\in I$, and if $n$ and $qd$ are both in $I$, then so is $n-qd$; hence $r\in I$; by minimality of $d$, we conclude that $r=0$, so $n$ is a multiple of $d$. That is, $I$ is exactly all multiples of $d$. Since $a,b\in I$, then $d|a$ and $d|b$; if $c$ is any integer that divides both $a$ and $b$, then $c$ divides every element of $I$, hence divides $d$. Thus, $d$ is a gcd of $a$ and $b$. $\Box$ Lemma. If $n$ is irreducible, then for every integer $a$, either $\gcd(n,a) = n$, or $\gcd(n,a)=1$. Proof. Let $d=\gcd(n,a)$. Then $d|n$, hence $n=dm$ for some integer $m$; since $n$ is irreducible, either $d=\pm 1$, or else $m=\pm 1$ (in which case $d=\pm n$). $\Box$ Theorem. (Euclid's Lemma) Irreducible integers are prime and prime integers are irreducible. Proof. Assume $p$ is prime, and $p=ab$. Then $p|ab$, hence $p|a$ or $p|b$; if $p|a$, then we can write $a=pr$, so $p=ab = prb$; since $p\neq 0$, we get $rb=1$, hence $b=\pm 1$; symmetrically, if $p|b$, then $b=ps$, so $p=ab=asp$ and we conclude $as=1$ so $a=\pm 1$. Thus, if $p$ is prime, then $p$ is irreducible. Now assume that $p$ is irreducible; then note that $p\neq 0$, since $0=0\times 2$ and neither $0$ nor $2$ are equal to $1$ or $-1$. Now assume that $p|ab$; we need to show that $p|a$ or that $p|b$. Since $p$ is irreducible, either $\gcd(p,a)=p$, in which case $p|a$ and we are done, or else $\gcd(p,a)=1$; then we can write $1=\alpha a + \beta p$; multiplying through by $b$ we get $b = \alpha ab + \beta b p$. Since $p|ab$, then $p|(\alpha ab+\beta bp) = b$, so $p|b$. $\Box$ The usual proof that factorizations exist is by strong induction: Theorem. (Euclid) For every positive integer $n$, if $n\gt 1$, then $n$ can be written as a product of prime numbers. Proof. Assume that every number strictly smaller than $n$ is either equal to $1$, or can be written as a product of prime numbers. We prove that the same holds for $n$. If $n=1$, we are done. If $n$ is prime, then we can express $n$ as $n=n$, a product of primes, and we are done. If $n$ is not prime, then it is not irreducible, so we can write $n=ab$ with $a$ and $b$ integers, neither equal to $1$; since $n\gt 0$, we may (changing signs if necessary) assume that $a$ and $b$ are both positive, hence $1\lt a \lt n$ and $1\lt b \lt n$. By the induction hypothesis, both $a$ and $b$ can be written as products of primes, $a= p_1\cdots p_r$ and $b=q_1\cdots q_s$; therefore, $n = ab = p_1\cdots p_rq_1\cdots q_s$, so $n$ can be written as a product of primes. This proves the result for all positive integers, by induction. $\Box$ The key to uniqueness is Euclid's Lemma: Theorem. (Gauss) The factorization of positive integers into primes is unique. That is, if $x$ is a positive integer, $x\gt 1$, and $$x = p_1^{a_1}\cdots p_r^{a_r} = q_1^{b_1}\cdots q_s^{b_s}$$ where $p_1\lt\cdots\lt p_r$, $q_1\lt\cdots\lt q_s$ are primes, and $a_i,b_j$ are positive integers for all $i$ and $j$, then $r=s$, $p_i=q_i$, and $a_i=b_i$ for all $i$. Proof. We may assume that $a_1+\cdots+a_r\leq b_1+\cdots +b_s$ by exchanging the two factorizations if necessary. We proceed by induction on $n=a_1+\cdots+a_r$. If $n=1$, then $x=p_1$ is a prime; thus, $p_1 = q_1^{b_1}\cdots q_s^{b_s}$. Since primes are irreducible, all factors in $q_1^{b_1}\cdots q_s^{b_s}$ except one must be equal to $1$ or $-1$; since all factors are prime, $s=1$ and $b_1=1$. Thus, we have uniqueness. Assume the result holds if $n=k$, and that the factorization of $x$ has $k+1$ factors. Since $p_1|x$, then $p_1|q_1^{b_1}\cdots q_s^{b_s}$. Since $p_1$ is prime, it divides some $q_j$, $p_1|q_j$. Since $q_j$ is prime, it is irreducible, so we must have $p_1=q_j$. Cancelling $p_1$ and $q_j$ from $$x = p_1^{a_1}\cdots p_r^{a_r} = q_1^{b_1}\cdots q_s^{b_s}$$ we obtain $$y = p_1^{a_1-1}\cdots p_r^{a_r} = q_1^{b_1}\cdots q_{j-1}^{b_{j-1}}q_j^{b_j-1}q_{j+1}^{b_{j+1}}\cdots q_s^{b_s}.$$ The number of prime factors of $y$ is $n$; by the induction hypothesis, the two remaining factorizations are identical. I claim we cannot have exactly one of $a_1$ and $b_j$ equal to $1$. If $a_1\gt 1$ and $b_j=1$, then by the induction hypothesis we either have $j\gt 1$, in which case $q_1=p_1$, which contradicts $p_1=q_1\lt q_j=p_1$; or $j=1$, in which case we would again get the contradiction that the equality of the two factorizations for $y$ give $p_1 = q_2\gt q_1 = p_1$. If $a_1=1$ and $b_j\gt 1$, then either $j\gt 1$, in which case we get a contradiction that $p_1 = q_j \gt q_1 = p_2 \gt p_1$; or $j=1$, in which case we get a contradiction that $p_1\lt p_2 = q_1 = p_1$. Thus, either $a_1=b_j=1$, or else $a_1\gt 1$, $b_j\gt 1$. If $a_1\gt 1$, $b_j\gt 1$, then since both factorizations for $y$ are identical, $p_1=q_1$, so $j=1$; $r=s$, $p_i=q_i$ for $i=1,\ldots,r$, $a_i=b_i$ for $i=2,\ldots,r$; and $a_1-1=b_1-1$, hence $a_1=b_1$, so the two factorizations of $x$ are identical. If $a_1=b_j=1$, since both factorizations of $y$ are identical, if $j\gt 1$ we have $p_2 = q_1\lt q_j = p_1 \lt p_2$; this is impossible so $j=1$, and so $r-1=s-1$ (so $r=s$), $p_i=q_i$ for $i=2,\ldots,r$ (and we already have $p_1=q_1$); $a_j=b_j$ for $j=2,\ldots,r$, and we also have $a_1=b_1=1$. So the two factorizations for $x$ are identical. $\Box$ |
|||
|
|
|
Below is a direct elementary proof of the Fundamental Theorem of Arithmetic from first principles, based on ideas going back to Zermelo (1901). THEOREM $\ $ Every natural $\rm\:n \ge 1\:$ has a prime factorization, unique up to order of factors. Proof $\ \ $ By induction on $\rm\:n. $ $\rm\:n = 1\:$ is an empty product of primes. Let $\rm\:n>1\:.\:$ Suppose that the theorem is true for all naturals $\rm < n.\:$ Let $\rm\:p\:$ be the least factor $\ne 1\:$ of $\rm\:n.$ $\rm\:p\:$ has no smaller factors $\rm\:q\ne 1,\:$ else $\rm\:q\:|\:p\:|\:n,\:$ contra leastness of $\rm\:p.\:$ Thus $\rm\:p\:$ is prime. By induction $\rm\:n/p\:$ has a unique prime factorization which, appended to $\rm\:p,\:$ yields a prime factorization of $\rm\:n.\:$ We show it unique. Consider a second prime factorization of $\rm\:n.\:$ It has at least one prime $\rm\:q\:$ since $\rm\:n > 1\:.\:$ Hence $\rm\ n = q\ q_2\cdots\:q_k = q\:Q\ $ for $\rm\: q_i\:$ primes. If $\rm\:p\:$ equals one of the $\rm\:q$'s then deleting $\rm\:p\:$ from the second factorization must leave said unique factorization of $\rm\:n/p\:.\:$ Thus both factorizations of $\rm\:n\:$ are the same up to order. Hence if $\rm\:p = q\:$ then the proof is complete. Otherwise, it suffices to show $\rm\:p\:$ equals one of the $\rm\:q_i.\:$ By leastness of $\rm\:p,\:$ $\rm\ p\ne q\ \Rightarrow\ p < q\:,\:$ so $\rm\ \bar n\: =\: n - p\:Q\: =\: (q - p)\:Q\ $ is $\rm\ 0 < \bar n < n\:.\: $ $\rm\:p\:|\:n\ \Rightarrow\ p\:|\:\bar n,\:$ so by induction $\rm\ \bar n/p\ $ has a prime factorization which, appended to $\rm\:p,\:$ gives a prime factorization of $\rm\:\bar n\:.\:$ By induction $\rm\:q-p\:$ has a prime factorization which, appended to $\rm\:Q = q_2\cdots q_k$ is a second factorization of $\rm\:\bar n.\:$ By induction both factorizations of $\rm\:\bar n\:$ are equal up to order, thus $\rm\:p\:$ occurs in said factorization of $\rm\:(q-p)\:Q,\:$ but not in that of $\rm\:q -p\:,\:$ else $\rm\:p\ |\ q-p\:$ $\Rightarrow$ $\rm\:p\:|\:q\:,\:$ contra $\rm p\ne q\:.$ Thus $\rm\:p\:$ must occur in the factorization $\rm\:Q = q_2\cdots\:q_k.\:$ Hence, indeed, $\rm\:p\:$ equals one of the $\rm\:q_i.\ \ $ QED |
|||
|
|
Besides the Wikipedia article mentioned by M Turgeon above, there is a very nice explanation by Tim Gowers here. |
|||
|
|
|
Here is a simple self-contained conceptual proof of uniqueness of prime factorizations of integers. $\:$ It employs Euclid's Lemma to prove that if a prime divides a product then it divides some factor. It proves Euclid's Lemma by exploiting the structure of the set of possible denominators of a fraction: it is closed under subtraction hence it is closed under gcd. Therefore a fraction representable with coprime denominators $\rm\:p,q\:$ is representable with denominator $\rm\:gcd(p,q)= 1,\:$ so it is an integer. For more on the innate algebraic structure see my posts on denominator ideals.) Theorem $\ $ Prime factorizations of an integer $\rm\:n>1\:$ are unique up to order. Proof $\ $ Suppose $\rm\:n\:$ has prime factorizations $\rm\:p\: p_2\cdots p_j = q\:q_2\cdots q_k.$ Note $\rm\:j,k \ge 1\:$ by $\rm\:n > 1.\:$ Inductively applying Euclid's Lemma (below) yields that $\rm\:p\:$ divides one of the $\rm\:q$'s, say $\rm\:p\ |\ q,\:$ so $\rm\:p = q.\:$ Canceling $\rm\:p\:$ from both factorizations yields factorizations of $\rm n/p.\:$ By induction, they are unique up to order. Hence so too are the above factorizations, obtained by appending $\rm\:p.\ \ $ QED Euclid's Lemma $\rm\ \ a,b\:$ coprime, $\rm\ a\: |\: b\:c\ \Rightarrow\ a\: |\: c\ \: $ for all naturals $\rm\: a,b,c > 0\:.$ Proof $\ $ For some $\rm\: d \in \mathbb N,\ a\:d\: =\: b\:c\: \Rightarrow\: \dfrac{c}a \: =\: \dfrac{d}b.\:$ Below Theorem $\rm\Rightarrow\: \dfrac{c}a\in\mathbb Z\ \ \ $ QED Theorem $\ \:$ If the rational number $\rm\ r\: =\: \dfrac{c}a\: =\: \dfrac{d}b\ $ for coprime $\rm\:a, b\in \mathbb N\:$ then $\rm\: r\:$ is an integer. Proof $\ $ By the symmetry of the hypotheses, we may suppose the notation is chosen so $\rm\: b \ge a\:.\ $ First, we prove that if $\rm\ b > a\ $ then there is such a representation of $\rm\:r\:$ with smaller value of $\rm\:b\:.\:$ View the fractions as vectors $\rm\:(a,c),\ (b,d)\:$ of slope $\rm\:r.\:$ Subtracting the smallest vector from the largest vector we deduce that $\rm\ r\: =\: \dfrac{c}a\: =\: \dfrac{d-c}{b-a}.\ \:.\phantom{\dfrac{.}{\dfrac{.}.}}\!\!\!\!\!\!\!\!\!\phantom{\dfrac{\dfrac{.}.}{.}}\!\!\!\!\!\!\!\!\!$ This is smaller since both $\rm\:a,\: b-a < b,\:$ and $\rm a,\:b-a\:$ are coprime: $\rm\: c\ |\ a,b\!-\!a\: \Rightarrow\: c\ |\ a+(b\!-\!a) = b\: \Rightarrow\: c\: |\: a,b\:$ so $\rm\: c\: |\: 1\: $ by $\rm\:a,b\:$ coprime. Of all such representations of $\rm\:r\:$ satisfying the hypotheses, consider one with the least value of $\rm\:b\:.\:$ Necessarily, $\rm\ b\: =\: a\ $ (else $\rm\:b > a,\:$ so, by above, there is a representation with smaller value of $\rm\:b$). Therefore $\rm\ a,b\: =\: a,a\ $ coprime $\rm\:\Rightarrow\ a = 1\:.\:$ Hence $\rm\ r\: =\: c/a\: =\: c/1\: =\: c\:$ is an integer. $\ $ QED |
||||
|
To give you some intuition, which is sometimes better than a formal proof, think about the following: By definition, primes are natural numbers greater than 1, that are indivisible (other than by itself and one). So suppose you have a natural number greater than 1, you can either divide it and write it as a product of two numbers (a*b) or not. You can then divide a and b further if they are not primes and finally you will arrive at a product which is composed of all primes. Suppose you arrived at the prime factorization of n = a*a*b*c, and you claimed that there exists another prime factorization n = d*a*b*c, so n = a*a*b*c = d*a*b*c, here lies a contradiction because you can cancel out a,b,c and arrive at a = d. |
|||||||
|
