induction proof of fundamental theorem of arithmetic
We present an induction^{} proof by Zermelo for the
fundamental theorem of arithmetic^{} (http://planetmath.org/FundamentalTheoremOfArithmetic).
Part 1. Every positive integer $n$ is a product^{} of prime numbers^{}.
Proof. If $n=1$, it is the empty product of primes, and if $n=2$, it is a prime number.
Let then $n>2$. Make the induction hypothesis that all positive
integers $m$ with $$ are products of prime numbers.
If $n$ is a prime number, the thing is ready. Else, $n$ is a
product of smaller numbers; these are, by the induction hypothesis,
products of prime numbers. The proof is complete^{}.
Part 2. For any positive integer $n$, its representation as product of prime numbers is unique up to the order of the prime factors.
Proof. The assertion is clear in the case that $n$ is a prime number, especially when $n=2$.
Let then $n>2$ and suppose that the assertion is true for all positive integers less than $n$.
If now $n$ is a prime, we are ready. Therefore let it be a composite number^{}. There is a least nontrivial factor $p$ of $n$. This $p$ must be a prime. Put $n=pb$ where b is a positive integer. By the induction hypothesis, $b$ has a unique prime factor decomposition. Thus $n$ has a unique prime decomposition containing the prime factor $p$.
Now we will show that $n$ cannot have other prime decompositions. Make the antithesis that $n$ has a different prime decomposition; let $q$ be the least prime factor in it. Now we have $$ and $n=qc$ where $c\in {\mathbb{Z}}_{+}$ and $$ with $p\nmid c$. Then
${n}_{0}:=n-pc=\{\begin{array}{cc}pb-pc=p(b-c)\hfill & \\ qc-pc=(q-p)c\hfill & \end{array}$ |
is a positive integer less than $n$. Since $p\mid {n}_{0}$, the induction hypothesis implies that the prime $p$ is in the prime decomposition of $(q-p)c$ and thus also at least of $q-p$ or $c$. But we know that $p\nmid c$, whence $p\mid q-p$. Thus we would get $p\mid q-p+p=q$. Because both $p$ and $q$ are primes, it would follow that $p=q$. This contradicts the fact that $$. Consequently, our antithesis is wrong. Accordingly, $n$ has only one prime decomposition, and the induction proof is complete.
References
- 1 Esa V. Vesalainen: “Zermelo ja aritmetiikan peruslause”. $-$ Solmu 1 (2014).
- 2 Ernst Zermelo: Elementare Betrachtungen zur Theorie der Primzahlen. $-$ Wissenschaftliche Gesellschaft zu Göttingen (1934). English translation in:
- 3 H.-D. Ebbinghaus & A. Kanamori (eds.): Ernst Zermelo. Collected Works. Volume I. Set Theory^{}, Miscellanea, Springer (2010). Ernst Zermelo: “Elementary considerations concerning the theory of prime numbers” 576$-$581.
Title | induction proof of fundamental theorem of arithmetic |
---|---|
Canonical name | InductionProofOfFundamentalTheoremOfArithmetic |
Date of creation | 2015-04-08 7:32:53 |
Last modified on | 2015-04-08 7:32:53 |
Owner | pahio (2872) |
Last modified by | pahio (2872) |
Numerical id | 10 |
Author | pahio (2872) |
Entry type | Proof |