Hi all,(adsbygoogle = window.adsbygoogle || []).push({});

I am spending some time learning discrete mathematics on my own using the MIT OpenCourseWare materials.

On page the second to last page of the Chapter 2 notes from here: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2010/readings/ [Broken]

it states

CHAPTER 2. THE WELL ORDERING PRINCIPLE

Theorem 2.4.1. Every natural number can be factored as a product of primes.

Proof. The proof is by Well Ordering.

Let C be the set of all integers greater than one that cannot be factored as a product of primes. We assume C is not empty and derive a contradiction.

If C is not empty, there is a least element, n ∈ C, by Well Ordering.The n can’t be prime, because a prime by itself is considered a (length one) product of primes and no such products are in C.

So n must be a product of two integers a and b where 1 < a,b < n. Since a and b are smaller than the smallest element in C, we know that a,b /∈ C. In other words, a can be written as a product of primes p1p2 ··· pk and b as a product of primes q1 ··· ql. Therefore, n = p1 ··· pkq1 ··· ql can be written as a product of primes, contradicting the claim that n ∈ C. Our assumption that C ≠ ∅ must therefore be false.

(the notation may be unclear, so it may be easier to read from the link)

Could someone explain this concept a bit further? I couldn't figure out this proof because I would have never made this assertion. How is a prime considered a length one product of primes? Say I have a prime, 3, what primes is this a product of?

Thanks in advance. All help is appreciated.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# A prime by itself is considered a (length one) product of primes?

Loading...

Similar Threads for prime itself considered |
---|

I Bijective function from naturals to primes |

**Physics Forums | Science Articles, Homework Help, Discussion**