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$
  • 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 Jul 12 at 18:32
  • 1
    $\begingroup$ I mean product of only primes. $\endgroup$ – rert588 Jul 12 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 Jul 13 at 9:13
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.