# Prove that every integer n > 1 is either prime or can be expressed as a product of primes. (Is proof valid?)

I have this theorem to prove:

Every integer n > 1 is either prime or can be expressed as a product of primes.


I want to know if my proof is sound and if not, in what way?

My attempt:

Note: Negation of XOR is the biconditional

Theorem in other words:

If n is an element of integers and n > 1, then n is prime XOR n can be expressed as a product of primes.


Assume: If n is an element of integers and n > 1, then n is prime <=> n can be expressed as a product of integers.

I try to prove, n is prime <=> n can be expressed as a product of primes, is always false as follows:

n is prime =>n is divisible by 1 and itself only =>n cannot be expressed as a product of primes.

n can be expressed as a product of primes =>n is not divisible only by 1 and itself. =>n is not prime.

Therefore the bi-conditional statement is always false, hence we have a contradiction.

Thus the theorem holds.

Q.E.D

• You should explicit define what "can be expressed as a product of primes" means. $2$ can be expressed as a product of primes! – dcolazin Jul 12 at 18:32
• I mean product of only primes. – rert588 Jul 12 at 18:43
• But $2$ is a product of only primes! And also "a product of several primes" can be interpreted badly ($4 = 2^2$). Better be formal and say $n$ is prime or $n = p_1^{e_1}\ldots p_k^{e_k}$ where $p_i$ are primes and $\sum e_i > 1$. – dcolazin Jul 13 at 9:13

What you ask follows from the Fundamental Theorem of Arithmetic, which states that every positive integer great than $$1$$ has a unique prime factorization (up to arrangement of the prime factors).
Hence, it follows that every integer $$n > 1$$ is either prime or a product of primes.