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

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.

• I can't follow your logic. $8=2\times 4$ has a prime factor, $2$, and a non-prime factor, $4$. That would be the smallest such. So what? – lulu Dec 12 '17 at 0:12
• what about p=1... – zwim Dec 12 '17 at 0:13
• That is not what you say at all, you claim to have shown that $p$, $4$ in this case, is prime which it is not. Maybe you think you are contradicting the minimality of $N$ which you are not. $4$ is not of the form you specify. Sorry, I think your proof is misconceived. I advise starting over. – lulu Dec 12 '17 at 0:35
• The proof that you wrote in the post is incorrect, for the reasons I said. Your last comment is silly...I gave you an explicit $N$! There is no contradiction to be derived from the existence of $8$. Just ask yourself, how could playing some trivial game with the factors of $8$ possibly prove something that held for all natural numbers? – lulu Dec 12 '17 at 0:38
• Sorry, I don't want to discuss this further. I have explained the flaw in your argument and provided a hint toward the standard proof. Take a look at the hint. – lulu Dec 12 '17 at 1:36

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$).

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)

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.