We present an induction proof by Zermelo for the
fundamental theorem of arithmetic.

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 $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.

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 $p<q$ and $n=qc$ where $c\in\mathbb{Z}_{+}$ and $c<n$ with $p\nmid c$. Then

$\displaystyle n_{0}\;:=\;n-pc=\begin{cases}pb-pc=p(b-c)\\ qc-pc=(q-p)c\end{cases}$ |

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.

## 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.

## Comments

## failure functions

Background: In 1988 I read the book ”one, two, three, infinity ” by George Gammow. The book had a statement to the effect that no polynomial had been found such that it generates all the prime numbers and nothing but prime numbers. This was true at the time Gammow wrote the book; however subsequently a polynomial was constructed fulfiling the condition given above. I then experimented with some polynomials and found that although one cannot generally predict the prime numbers generated by a polynomial one can predict the composite numbers generated by a polynomial. Since I was originally trying to predict the primes generated by a given polynomial (which may be called ”successes ”) but could predict the ”failures” (composite numbers) I called functions which generate failures ”failure functions ”. I presented this concept at the Ramanujan Mathematical society in May 1988. Subsequently I used this tool in proving a theorem similar to the Ramanujan Nagell theorem at the AMS-BENELUX meeting in 1996.

Abstract definition: Let $f(x)$ be a function of $x$. Then $x=g(x_{0})$ is a failure function if f(g(x_0)) is a failure in accordance with our definition of a failure.Note: $x_{0}$ is a specific value of $x$.

Examples: 1) Let our definition of a faiure be a composite number. Let $f(x)beapolynomialinxwherexbelongsto$ Z$.Then$x$=$x_0 + kf(x_0) is a failure function since these values of $x$ are such that f(x) are composite.

2) Let our definition of a failure again be a composite number. Let the function be an exponential function $a^{x}+cwhereaandxbelongtoN,cbelongstoZ$ and a and c are fixed. Then $x=x_{0}+k*Eulerphi(f(x_{0})$ is a failure function.Here also $x_{0}$ is fixed. Here k belongs to N.

3) Let our definition of a failure be a non-Carmichael number. Let the mother function be $2^{n}+49$. Then $n=5+6*k$ is a failure function. Here also $k$ belngs to $N$.

Applications: failure functions can be used for $a)$ indirect primality testing and $b)$ as a mathematical tool in proving theorems in number theory.