Why is the proof not right ? Every positive integer can be written as a product of primes?

Question

Here is my proof (not from the textbook). Please let me know if it is wrong.

PROOF:

I prove by contradiction i.e. I assume N as smallest +ve integer which has non-prime factor p and a prime factor q

N = p * q

p = N\q

from our assumptions, p is an integer, it is not prime and it is expressed as a fraction of 2 integers.

This is a contradiction (when you substitute p as the new N). Therefore, p is a prime and hence N is a product of primes.

Answer 1

The proof is incorrect because you are claiming to derive a contradiction from $p$ not being a fraction of two integers. However, $6=\frac{12}{2}$ is not prime, it has prime denominator, and it is a fraction of two integers, so this isn't actually a contradiction. (Here $p=6$, $q=2$, and $N=12$).

Answer 2

First take into account that $1$ is a positive integer that cannot be expressed as a product of primes.

Then, following that, we have that no prime number can be expressed as a product of primes, since the only way to facotr a prime $p$ is $p= p \times 1 = p \times 1 \times 1...$. It's always either a product of 1 prime o a prime and any amount of $1$'s.

So what you might want to prove is: Every positive number bigger than $1$ can be expressed as a product of 1 or more primes

This can be written as $$\forall n \in \mathbb{N}, \exists \{p_1,p_2,...,p_m\}: n = p_1 p_2 ... p_m$$ where $p_i \le p_{i+1} \ \ \ \forall 1 \le i \le m -1 $

Which is true and known as the Fundamental Theorem of Arithmetic

Also, this factorization is unique

I'll save this anwer and I'll be back in about an hour if you want me to prove this (or just look up the proof since it's everywhere)

Answer 3

The first flaw is that, by def'n, $1$ is not prime so you should state and prove that if $1<n\in \Bbb N$ then $n$ is a product of primes.

The second flaw is assuming that if $1<n\in \Bbb N$ then $n$ has a prime factor $q.$ Although this is true, it ought to be proven: Let $q$ be the smallest (positive integer) factor of $n$ that's greater than $1.$ So $n=pq$ with $p\in \Bbb N.$ Then $q$ is prime. For, if not, then $q=q'q''$ where $q',q'' \in \Bbb N$ with $q'>1<q'',$ but then $q'$ is a factor of n (because $n=q'\cdot pq''),$ but $1<q'<q,$ a contradiction.

After that part, I disagree with some of the other comments and say you are correct, although it should be presented with more detail, as follows: Suppose (by contradiction) there is a least $n\in \Bbb N$ with $n>1$ where $n$ is not prime and not a product of primes Then $n=pq$ where $1<p\in \Bbb N$ and $q$ is prime. Since $p<n,$ either $p$ is prime, or (by the minimality of $n$) $p$ is a product of primes, but in either case this makes $n=pq$ a product of primes.

You can avoid proving that if $1<n\in \Bbb N$ then $n$ has a prime factor $q,$ and obtain that as a corollary to the main result, as follows: Suppose (by ccontradiction) there is a least $n\in \Bbb N$ with $n>1$ where $n$ is not prime and $n$ is not a product of primes. Then $n=ab$ where $a,b \in \Bbb N$ and $a>1<b.$ Since $a<n>b,$ the minimality of $n$ implies that each of $a,b$ is either prime or a product of primes, but then $n=ab$ is a product of primes.