Why prime factorization ?
-
Hi, This is basically a math question, but very much applicable to many of the computer algorithms. I know the fact that, - Any integer can be expressed as product of prime factors. - Prime factors can be used to find LCM and HCF - Prime factors can be used to check whether a number divides "N" ( N - Integer ) - Etc.. Etc... My question is.. Why this unique ability for prime numbers ? How is it possible that, any number can be expressed as product of prime factors ? What is it, which makes these prime numbers special ? I just found this article on web, which was informative, but was little hard to understand. Can someone explain me this mystery behind prime numbers, any links web resources is much appreciated.
Regards, Vijay Blog : Amusement of a speculative mind...[^] Projects : Amusement of a dilettante mind...[^]
Vijay Sringeri wrote:
Why this unique ability for prime numbers ?
Which one exactly ?
Vijay Sringeri wrote:
How is it possible that, any number can be expressed as product of prime factors ?
Vijay Sringeri wrote:
What is it, which makes these prime numbers special ?
As you have pointed out, their properties can be used in a lot of algorithms. But this is the case for other "type" of numbers having other properties used in other type of algorithms. So your question is no easy to answer... It is like asking why knives are useful to cut something.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus Do not feed the troll ! - Common proverb
-
Well, if you consider a prime being the product of himself by 1, which is also prime, then you can extend it to any integer.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus Do not feed the troll ! - Common proverb
That is indeed the definition of a prime (a number with no +ive divisors other than 1 and itself). But the OP wrote "Any integer can be expressed as product of prime factors." and 1 is not a prime. /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
Well, if you consider a prime being the product of himself by 1, which is also prime, then you can extend it to any integer.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus Do not feed the troll ! - Common proverb
Rage wrote:
Well, if you consider a prime being the product of himself by 1, which is also prime, then you can extend it to any integer.
That's nitpicking. Which is of course totally in line with this forum. :)
Light moves faster than sound. That is why some people appear bright, until you hear them speak. List of common misconceptions
-
Vijay Sringeri wrote:
Any integer non-prime can be expressed as product of prime factors.
FTFY. /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
Ravi Bhavnani wrote:
Any integer non-prime natural number can be expressed as product of prime factors.
1 is the product of { } p is the product of { p } for p is prime
Positive integers > 1, actually, not all natural numbers. :) /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
Positive integers > 1, actually, not all natural numbers. :) /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
Vijay Sringeri wrote:
Any integer non-prime can be expressed as product of prime factors.
FTFY. /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
7 x 1 = 7 FTFY
Sort of a cross between Lawrence of Arabia and Dilbert.[^]
-Or-
A Dead ringer for Kate Winslett[^] -
That is indeed the definition of a prime (a number with no +ive divisors other than 1 and itself). But the OP wrote "Any integer can be expressed as product of prime factors." and 1 is not a prime. /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
Ravi Bhavnani wrote:
1 is not a prime
I remember having had to copy this 100 times back when I still was in school. And still don't remember it. Grrrrr.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus Do not feed the troll ! - Common proverb
-
Ravi Bhavnani wrote:
1 is not a prime
I remember having had to copy this 100 times back when I still was in school. And still don't remember it. Grrrrr.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus Do not feed the troll ! - Common proverb
:-D /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
harold aptroot wrote:
No, 1 too. 1 is the empty product, and clearly an empty set contains only prime numbers
No! 1 is no prime number and nothing isn't a prime number. It's called prime factorization but in the prime factorization for 1 is no prime number. The prime factorization for 1 is by definition 1 (and not the product of empty set).
------------------------------ Author of Primary ROleplaying SysTem How do I take my coffee? Black as midnight on a moonless night. War doesn't determine who's right. War determines who's left.
-
harold aptroot wrote:
No, 1 too. 1 is the empty product, and clearly an empty set contains only prime numbers
No! 1 is no prime number and nothing isn't a prime number. It's called prime factorization but in the prime factorization for 1 is no prime number. The prime factorization for 1 is by definition 1 (and not the product of empty set).
------------------------------ Author of Primary ROleplaying SysTem How do I take my coffee? Black as midnight on a moonless night. War doesn't determine who's right. War determines who's left.
ihoecken wrote:
The prime factorization for 1 is by definition 1
Yes, but he didn't say that, the question was: "can 1 be written as a product of prime numbers?" And it can be, an empty set is a perfectly valid set of prime number, it just happens to be empty.
-
Hi, This is basically a math question, but very much applicable to many of the computer algorithms. I know the fact that, - Any integer can be expressed as product of prime factors. - Prime factors can be used to find LCM and HCF - Prime factors can be used to check whether a number divides "N" ( N - Integer ) - Etc.. Etc... My question is.. Why this unique ability for prime numbers ? How is it possible that, any number can be expressed as product of prime factors ? What is it, which makes these prime numbers special ? I just found this article on web, which was informative, but was little hard to understand. Can someone explain me this mystery behind prime numbers, any links web resources is much appreciated.
Regards, Vijay Blog : Amusement of a speculative mind...[^] Projects : Amusement of a dilettante mind...[^]
Because it's there.
-
ihoecken wrote:
The prime factorization for 1 is by definition 1
Yes, but he didn't say that, the question was: "can 1 be written as a product of prime numbers?" And it can be, an empty set is a perfectly valid set of prime number, it just happens to be empty.
harold aptroot wrote:
And it can be, an empty set is a perfectly valid set of prime number, it just happens to be empty.
No! That's wrong by mathematical definitions! By definition the empty set is the unique set having no elements and the axiom of extensionality shows that there is only one empty set. So there is no empty set of prime numbers. There exists only one empty set. No prime numbers at all. :rolleyes:
------------------------------ Author of Primary ROleplaying SysTem How do I take my coffee? Black as midnight on a moonless night. War doesn't determine who's right. War determines who's left.
-
Because it's there.
-
harold aptroot wrote:
And it can be, an empty set is a perfectly valid set of prime number, it just happens to be empty.
No! That's wrong by mathematical definitions! By definition the empty set is the unique set having no elements and the axiom of extensionality shows that there is only one empty set. So there is no empty set of prime numbers. There exists only one empty set. No prime numbers at all. :rolleyes:
------------------------------ Author of Primary ROleplaying SysTem How do I take my coffee? Black as midnight on a moonless night. War doesn't determine who's right. War determines who's left.
The empty set contains 'only prime numbers' in that it doesn't contain any non-primes. If the product of an empty set is defined to be 1, and I think it is, then Harold's statement is true. We're into somewhat abstruse mathematical definition territory here, though.
-
The empty set contains 'only prime numbers' in that it doesn't contain any non-primes. If the product of an empty set is defined to be 1, and I think it is, then Harold's statement is true. We're into somewhat abstruse mathematical definition territory here, though.
BobJanova wrote:
The empty set contains 'only prime numbers' in
No, that's wrong: http://en.wikipedia.org/wiki/Empty_set[^] Quote: "the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero" http://www.proofwiki.org/wiki/Definition:Empty_Set[^] Mathematically it's not true that it contains prime numbers. The definition says: There is nothing in it. Take a look of "Axiom of empty set" it states that there is only one empty set, no matter what you want to describe. If you have a set of colours {blue, red, green}, it's the same empty set. There is only one. Containing nothing. http://en.wikipedia.org/wiki/Axiom_of_empty_set[^]
BobJanova wrote:
I think it is, then Harold's statement is true.
It's wrong. As it's not the definition of the empty set. Read it, then you see.
------------------------------ Author of Primary ROleplaying SysTem How do I take my coffee? Black as midnight on a moonless night. War doesn't determine who's right. War determines who's left.
-
BobJanova wrote:
The empty set contains 'only prime numbers' in
No, that's wrong: http://en.wikipedia.org/wiki/Empty_set[^] Quote: "the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero" http://www.proofwiki.org/wiki/Definition:Empty_Set[^] Mathematically it's not true that it contains prime numbers. The definition says: There is nothing in it. Take a look of "Axiom of empty set" it states that there is only one empty set, no matter what you want to describe. If you have a set of colours {blue, red, green}, it's the same empty set. There is only one. Containing nothing. http://en.wikipedia.org/wiki/Axiom_of_empty_set[^]
BobJanova wrote:
I think it is, then Harold's statement is true.
It's wrong. As it's not the definition of the empty set. Read it, then you see.
------------------------------ Author of Primary ROleplaying SysTem How do I take my coffee? Black as midnight on a moonless night. War doesn't determine who's right. War determines who's left.
Uh, I know what the empty set is. But the statement 'set S contains only thing X' is equivalent to 'set S has no members which are not X': in this case 'the empty set contains only primes' is equivalent to 'the empty set has no non-prime members'. And since it has no members at all, that is clearly true! The empty set also only contains blue items, non-prime items, even numbers, or any other set. Empties are weird like that, a bit like zero being divisible by everything.
-
Uh, I know what the empty set is. But the statement 'set S contains only thing X' is equivalent to 'set S has no members which are not X': in this case 'the empty set contains only primes' is equivalent to 'the empty set has no non-prime members'. And since it has no members at all, that is clearly true! The empty set also only contains blue items, non-prime items, even numbers, or any other set. Empties are weird like that, a bit like zero being divisible by everything.
BobJanova wrote:
in this case 'the empty set contains only primes' is equivalent to 'the empty set has no non-prime members'
That is logically and mathematically incorrect. This is no equivalence, because there are no members and so both statements are correct: It contains no non-prime member AND it contains no prime members. Mathematically it's wrong, you can't change it. It has nothing to do with your interpretation: empty is empty. Nothing in there. If you don't believe ask another one who studied mathematics or your professor from university, they will say the same. Edit: By the way. If you can proove, that you are right. Do it. I will make my mind up, if you can. I gave you links to the definitions that support what I said. Do the same for a real discussion.
------------------------------ Author of Primary ROleplaying SysTem How do I take my coffee? Black as midnight on a moonless night. War doesn't determine who's right. War determines who's left.
-
Ravi Bhavnani wrote:
1 is not a prime
I remember having had to copy this 100 times back when I still was in school. And still don't remember it. Grrrrr.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus Do not feed the troll ! - Common proverb
It is, I think, fairly common that the trivial object is actually TOO simple. For example, the empty space is not connected, the trivial ring is not a field, and 1 is not a prime number. The reason is an existence-uniqueness one - in this case, the prime factor representation always exists for a number, but it's not unique unless 1 is considered to not be prime.
-
Vijay Sringeri wrote:
Why this unique ability for prime numbers ?
Which one exactly ?
Vijay Sringeri wrote:
How is it possible that, any number can be expressed as product of prime factors ?
Vijay Sringeri wrote:
What is it, which makes these prime numbers special ?
As you have pointed out, their properties can be used in a lot of algorithms. But this is the case for other "type" of numbers having other properties used in other type of algorithms. So your question is no easy to answer... It is like asking why knives are useful to cut something.
~RaGE();
I think words like 'destiny' are a way of trying to find order where none exists. - Christian Graus Do not feed the troll ! - Common proverb
Hey Rage, That was a sharp, and precise reply. Thanks. The link for "Euclid's lemma" was helpful, however it builds other theorems based on the fundamental fact that " Any non prime number can be expressed as product of prime numbers". Lastly, what an explanation..
Rage wrote:
As you have pointed out, their properties can be used in a lot of algorithms. But this is the case for other "type" of numbers having other properties used in other type of algorithms. So your question is no easy to answer... It is like asking why knives are useful to cut something.
I just loved it, But sadly.. This is what I want someone to answer for me.. :thumbsup:
Regards, Vijay Blog : Amusement of a speculative mind...[^] Projects : Amusement of a dilettante mind...[^]