0
$\begingroup$

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.

Proof by contradiction:

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

$\endgroup$
3
  • 1
    $\begingroup$ You should explicit define what "can be expressed as a product of primes" means. $2$ can be expressed as a product of primes! $\endgroup$
    – dcolazin
    Commented Jul 12, 2019 at 18:32
  • 1
    $\begingroup$ I mean product of only primes. $\endgroup$
    – rert588
    Commented Jul 12, 2019 at 18:43
  • $\begingroup$ 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$. $\endgroup$
    – dcolazin
    Commented Jul 13, 2019 at 9:13

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .