Remember the role of axioms, which another poster has explained in a different way. The issue in question (not itself an axiom but one that requires acceptance of axioms) is whether each composite (i.e. non-prime) is uniquely composed of primes.

To prove this for yourself, try assembling a composite number out of non-prime factors. Then, to make sure of your result, decompose your factors into the primes from which they were composed. Finally, restate your factorization by replacing your factors with the primes that compose them.

Example: the composite number 32 is normally factored as 2^5, i.e. four multiplications of the prime number 2. Let's say I want to falsify the idea that all positive integers are either prime or uniquely composed of primes, so I instead compose 32 using the nonprime factors 8 and 4.

Then I factor 8 and 4, and discover that their prime factors are also factors of 32 --

8 = 2^3

4 = 2^2

32 = 2^5

-- so I have proven the original thesis: all positive integers are either themselves prime or are uniquely composed of primes.

The idea I am trying to convey is that the original claim doesn't mean one cannot assemble a composite out of non-primes, only that the composite number is also representable by a unique prime factorization.

More depth here: http://en.wikipedia.org/wiki/Prime_factor

> "So this means: it has a divisor not in the initial primes (actually, I think it must have two). But why should it be prime?"

Ok, this is the heart of the issue. If the new number is a prime, all is well and good, but if the number isn't prime, why should it's divisors be?

The simple answer is: they don't have to be. If you have divisors that aren't prime, then keep dividing till you hit some that are. The definition of a prime number is one that can only be divided by itself, so for any non-prime number, you must be able to keep finding factors until they're all prime!

Let's take an example. Our list of primes is {5,7} which are nice small numbers to use. By following the rule of "multiply and add 1" we get:

    5 * 7 + 1 = 36.

Ok, so let's break 36 down. We get:

    36 = 2 * 18

Right, well, 2 isn't on our list, but let's face it: 2 isn't a real prime. None of the other primes like it. It's even. Nor is 18 on our list, but that's not prime (and that was your objection before), so let's break 18 down.

    36 = 2 * 2 * 9

Well, that's a bit better. We have another unpopular 2, but we also got a 9, and even though 9 isn't prime, it's probably primier than 2 is. Continue on:

    36 = 2 * 2 * 3 * 3

There we go. Now we actually have a proper prime number, "3", that we can add to our list.

And you see (I hope) that none of these numbers could possibly be on our original list, because all the numbers already on that list give a remainder of "1" when we divide "36". Yet we must, inevitably, hit a prime number because we just keep dividing till we do!

> I think a given divisor does not need to be prime; but it must not be divisible by an initial prime.

But that's how prime is defined -- indivisible by any other numbers except 1. If you statement is true -- that a given number "must not be divisible by an initial prime", that means the number is itself prime.

Positive integers fall into precisely two categories:

1. Not divisible by any smaller numbers except 1.

2. Divisible by one or more smaller numbers.

Those in category (1) are prime. Those in category (2) are composite. There is no third possibility.