*Proof*.
If

is a prime then we are finished. If

is not
prime then there exists two natural numbers

and

different from

and from

such that

. If both are prime, we are done. Otherwise, we repeat the argument either for

or for

or for both; as a proper divisor of a natural number is smaller than this number, we deal here with decreasing sequences of natural numbers; as a decreasing sequence of natural numbers becomes stationary at some step, the process stops.

*Proof*.
Assume that there exist only a finite number of primes and denote them by

.
Now define the number

. The natural number

is not divisible by any of the

(if

would be divisible by any of the primes

, then

would be divisible by this prime...). Thus

is a ``new'' prime. We can repeat this process infinitely many times.