Fork me on GitHub
Math for the people, by the people.

User login

induction proof of fundamental theorem of arithmetic

% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these

% need this for including graphics (\includegraphics)
% for neatly defining theorems and propositions

% making logically defined graphics
% used for TeXing text within eps files

% there are many more packages, add them here as you need them

% define commands here

We present an induction proof by Zermelo for the 
\PMlinkname{fundamental theorem of arithmetic}{FundamentalTheoremOfArithmetic}.\\

\textbf{Part 1.}\, Every positive integer $n$ is a product of prime numbers.

{\it 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\, $1 < m < n$\, 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.\\

\textbf{Part 2.}\, For any positive integer $n$, its representation 
as product of prime numbers is unique up to the order of the 
prime factors.
{\it 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\, $p < q$\, 
and\, $n = qc$\, where\, $c \in \mathbb{Z}_+$\, and\, $c < n$\, 
with\, $p \nmid c$.\, Then
n_0 \;:=\; n-pc = 
      pb-pc = p(b-c)\\
      qc-pc = (q-p)c  
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\, $p < q$.\, Consequently, our 
antithesis is wrong.\, Accordingly, $n$ has only one prime 
decomposition, and the induction proof is complete.

\bibitem{vesa}{\sc Esa V. Vesalainen}: ``Zermelo ja aritmetiikan 
peruslause''. $-$ {\it Solmu} \textbf{1} (2014).
\bibitem{zermelo}{\sc Ernst Zermelo}: {\it Elementare
Betrachtungen zur Theorie der Primzahlen}.\, $-$ Wissenschaftliche Gesellschaft zu 
G\"ottingen (1934). English translation in:
\bibitem{z} H.-D. Ebbinghaus \& A. Kanamori (eds.): {\it Ernst Zermelo. Collected
Works. Volume I. Set Theory}, Miscellanea, Springer (2010).  Ernst Zermelo: ``Elementary 
considerations concerning the theory of prime numbers'' 576$-$581.