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

[ILikeToLearn]

Hi all,

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/

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.

 

[chiro]

Hi all,

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/

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.

Hello ILikeToLearn and welcome to the forums.

Primes by definition can only be divided (without any remainder) by themselves and 1.

In your example 3 is a prime because if you try to divide 3 by 2, you get a remainder. The idea is that if you try to divide a whole number > 1 by every number between 2 and n - 1 where n is the number and you get a remainder for every time you try, then the number is prime.

The fundamental theorem of arithmetic says every number > 1 that is a whole number has prime(s) as its factors. If the number is prime, then it can only have one prime factor and that is itself.

If you think about a number that is not prime, that means that some number between 2 and n - 1 divides the number and has no remainder. If you call that number q that means you can say n = q x k.

The idea is that you can keep doing this for every factor until you end up with a prime number since at some point, you will keep factoring the number until you get one factor that has only 1 and itself as factors. You collect the factors together and since they end up all being prime, then you end up being able to take any number and write them as multiplication of prime numbers.

 

[checkitagain]

CHAPTER 2. THE WELL ORDERING PRINCIPLE

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

It should state that "Every natural number greater than one can be factored
as a product of primes," as one isn't prime (or composite).

 

[micromass]

It should state that "Every natural number greater than one can be factored
as a product of primes," as one isn't prime (or composite).

1 can be seen a the empty product of primes. Some books do that.

 

[ILikeToLearn]

Thanks for the replies so far.

I certainly understand that a prime can only be divided by 1 and itself without a remainder. But how is a prime a product of primeS?

"If the number is prime, then it can only have one prime factor and that is itself." I completely agree. So if 3 is a product of 3 and 1, and we know 3 is a prime and 1 is NOT a prime, then 3 is a product of a prime and a non-prime - NOT a product of primes. Where am I going wrong here?

 

[conquest]

In your example 3 is a prime because if you try to divide 3 by 2, you get a remainder. The idea is that if you try to divide a whole number > 1 by every number between 2 and n - 1 where n is the number and you get a remainder for every time you try, then the number is prime.

Hi,

@chiro actually you don't have to check all the way up to n-1, but only from 2 up until √n.

@ILikeToLearn
basically you should see a 'product' as if you have an ordered set of letters (or numbers) S which is a subset of the integers. Then take the product first with 1 and then with all the other stuff in the set. Then if there is only the number n in the set 1n=n. the length of the product is now the cardinality of the set. also by this definition the product of length 0 is 1.

If you go into more abstract algebras where you have rings. Then you also have the product of primes theorem but it says every letter is the product of primes up to unities. in the integers the only unity being 1 (since for all the other numbers the inverse w.r.t. multiplication is not an integer but a fraction). so you don't count 1 basically, the reason for this is that 1*1*1*1*1*1*1*1*...*1*n=n (where * means multiply). So it's silly to accoutn for this because you can put however many 1's in front of any number and it doesn't do anything.

I hope this helps.