iohanetc

2021-02-25

Prove the Fundamental Theorem of Arithmetic. Every integer than 1 is a prime or a product of primes. This product is unique, exept for the order in which the factors appear.

timbalemX

Skilled2021-02-26Added 108 answers

The objective is to prove the Fundamental Theorem of Arithmetic, that states: “Every number greater than 1 is a prime or a product of primes. This product is unique, except for the order in which the factors appear.” To prove the existence, use induction: \(2>1\) is a prime number itself so it satisfy the statement. Now let all the integers from 1 to k, i.e. \(1k=ab\) where \(\displaystyle{1}{<}{a},{\quad\text{and}\quad}\ {b}{<}{k}\) By our asumption since both a and b are between 1 and k they both can be written as product of primes So, \(k = ab\) can be written as product of primes. Thus, by induction all integers gratee than 1 are either prime or can be written as product of primes. Now, let’s prove uniqueness of the product for that let a integer n can be expressed as a product of primes in two ways: \(\displaystyle{n}={p}_{{1}}\cdot{p}_{{2}}\cdot\ldots.\cdot{p}_{{k}},{\quad\text{and}\quad}{n}={s}_{{1}}\cdot{s}_{{2}}\cdot\ldots\cdot{s}+{m}\)

Where, \(\displaystyle{p}_{{1}},{p}_{{2}},\ldots.,{p}_{{k}}{\quad\text{and}\quad}{s}_{{1}},{s}_{{2}},\ldots,{s}_{{m}}\) are primes.

\(\displaystyle\Rightarrow{n}={p}_{{1}}\cdot{p}_{{2}}\cdot\ldots.\cdot{p}_{{k}}={s}_{{1}}\cdot{s}_{{2}}\cdot\ldots\cdot{s}_{{m}}\Rightarrow{p}_{{i}}{\mid}{s}_{{1}}\cdot{s}_{{2}}\cdot\ldots\cdot{s}_{{m}}{f}{\quad\text{or}\quad}{a}{n}{y}{1}\leq{i}{<}{k}\)

Now, by Euclid’s Lemma \(\displaystyle\exists{s}_{{j}}\) for \(\displaystyle{1}\leq{j}{<}{m}\) such that \(\displaystyle{p}_{{i}}{\mid}{s}_{{j}}\) And since both \(\displaystyle{p}_{{i}},\) and \(\displaystyle{s}_{{j}}\) are primes \(\displaystyle\Rightarrow{p}_{{i}}={s}_{{j}}\) Divide these two common factors from \(\displaystyle{p}_{{1}}\cdot{p}_{{2}}\cdot\ldots\cdot{p}_{{k}}={s}_{{1}}\cdot{s}_{{2}}\cdot\ldots\cdot{s}_{{m}}\) and repeat the process untill all common factors have been divided out. Also note that \(k = m\) unless then after repeating above process we will be left with \(\displaystyle{p}_{{{i}_{{1}}}}\cdot{p}_{{{i}_{{2}}}}\cdot\ldots\cdot{p}_{{{i}_{{r}}}}={1}{\left({\quad\text{if}\quad}{k}{>}{m}\right)}{\quad\text{or}\quad}{s}_{{{m}_{{1}}}}\cdot{s}_{{{m}_{{2}}}}\cdot\ldots\cdot{s}_{{{m}_{{n}}}}={1}{\left({\quad\text{if}\quad}{k}{<}{m}\right)}\) And, all primes are greater than 1 so both of above cases are not possible, thus, \(\displaystyle{k}={m}.\) And after repeating the process we have \(\displaystyle{p}_{{i}}={s}_{{r}}\forall{1}\leq{i}\leq{k},{\quad\text{and}\quad}{1}\leq{r}\leq{m}\) Thus, product of prime factors of a number is unique.