Why prime factorization ?
-
harold aptroot wrote:
It doesn't have to contain prime numbers, it only has to contain only prime numbers, which is the same as saying that all numbers in it are prime, which is vacuously true.
No! It contains nothing of everything. So it contains no prime number and no not prime numbers. And that is obviously true. :rolleyes: I think we won't come to an agreement. Let's say there are differences between us, but I could agree that there are nearly nothing ;)
------------------------------ 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:
No! It contains nothing of everything. So it contains no prime number and no not prime numbers. And that is obviously true.
Yes I completely agree, I just don't see why this is an issue. This means it doesn't contain any non-primes, so it passes the test.
-
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...[^]
Mathematicians love to decompose things. The parts of a thing a usually easier to handle. When they considered the integers and the law of addition, they saw nothing interesting. Any integer larger than 2 decomposes into smaller parts: 12 decomposes into 1+11, 2+10, 3+9, 4+8, 5+7 and 6+6. This is trivial. 1 cannot be decomposed, so 1 is the only "prime" as regards addition. When they considered the integers and the law of multiplication, things got funnier: 12 decomposes into 2 x 6 and 3 x 4, 6 decomposes into 2 x 3 and 4 decomposes into 2 x 2. But 2 and 3 cannot be decomposed. So the idea of primes came quite naturally by discovering thoses numbers that cannot be decomposed. And they found much less regularity, meaning cool things to study. There is no real mystery in the decomposition: either a number cannot be decomposed, then it is called prime, or it can be decomposed, then it is called composite. You can apply the same reasoning to its parts, which are smaller. In the end, you always end up with prime factors, because decomposition is a finite process. (This is a case of infinite descent[^].) More mysterious is the fact that the decomposition is unique: whatever the way you apply the decomposition, you always end up with the same factors with the same multiplicity. Example: 12 = 2 x 6 = 2 x 2 x 3 or 12 = 3 x 4 = 3 x 2 x 2. But you easily understand that if a prime factor p appears r times in one decomposition of an integer n and s times in another (let r < s), we have a problem, as if we divide n by p^s, in the first case we will get a nonzero remainder and in the other case a zero remainder ! What makes prime numbers so attractive is that mathematicians have failed so far to find simple structures in their distribution, leading to the famous Rieman's hypothesis[^], considered a major unsolved problem in modern mathematics.
-
ihoecken wrote:
No! It contains nothing of everything. So it contains no prime number and no not prime numbers. And that is obviously true.
Yes I completely agree, I just don't see why this is an issue. This means it doesn't contain any non-primes, so it passes the test.
harold aptroot wrote:
Yes I completely agree, I just don't see why this is an issue
Well, perhaps we talked past each other. I just diagreed with that statement:
harold aptroot wrote:
an empty set contains only prime numbers
Of course I agreed with:
harold aptroot wrote:
1 is the product of { }
p is the product of { p } for p is primeSo I said nothing against the original statement of yours. I think that it's correct, I was just agaist the statement the empty set would contain only prime numbers.
harold aptroot wrote:
This means it doesn't contain any non-primes, so it passes the test.
I totally agree to that.
------------------------------ 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:
Yes I completely agree, I just don't see why this is an issue
Well, perhaps we talked past each other. I just diagreed with that statement:
harold aptroot wrote:
an empty set contains only prime numbers
Of course I agreed with:
harold aptroot wrote:
1 is the product of { }
p is the product of { p } for p is primeSo I said nothing against the original statement of yours. I think that it's correct, I was just agaist the statement the empty set would contain only prime numbers.
harold aptroot wrote:
This means it doesn't contain any non-primes, so it passes the test.
I totally agree to that.
------------------------------ 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.
Ok, now this is getting somewhere. What's the issue with "an empty set contains only prime numbers" exactly? I wrote that in part to be funny really, but to me that statement means the same as "for all x in the empty set, x is a prime number", and that would make it not only amusing but true.
-
Ok, now this is getting somewhere. What's the issue with "an empty set contains only prime numbers" exactly? I wrote that in part to be funny really, but to me that statement means the same as "for all x in the empty set, x is a prime number", and that would make it not only amusing but true.
harold aptroot wrote:
or all x in the empty set, x is a prime number
Now it's starting over from the beginning. Stating that is pointless, there is no x in the empty set, because the empty set has no elements by definition. So you can't say for all x in the empty set, x is whatever. You can say the empty set contains no not-prime number (as it containt no prime numbers), that of course is true. Nothing is not an element of anything. It's just nothing, by definition.
------------------------------ 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:
or all x in the empty set, x is a prime number
Now it's starting over from the beginning. Stating that is pointless, there is no x in the empty set, because the empty set has no elements by definition. So you can't say for all x in the empty set, x is whatever. You can say the empty set contains no not-prime number (as it containt no prime numbers), that of course is true. Nothing is not an element of anything. It's just nothing, by definition.
------------------------------ 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.
Of course you can say it, it's just a vacuous truth, and exactly equivalent to saying "there is no element in the empty set that isn't a prime number", no trouble there :confused: It's just the second case described here: http://en.wikipedia.org/wiki/Vacuous_truth[^] What you can't say is "there exists an element x in the empty set such that P(x) is true"
-
Of course you can say it, it's just a vacuous truth, and exactly equivalent to saying "there is no element in the empty set that isn't a prime number", no trouble there :confused: It's just the second case described here: http://en.wikipedia.org/wiki/Vacuous_truth[^] What you can't say is "there exists an element x in the empty set such that P(x) is true"
Forget my last posting it is trash. I didn't know what I wrote. Yes, I know what vacuous truth is. And I don't want to raise to question.
harold aptroot wrote:
clearly an empty set contains only prime numbers
That is wrong, because: any set X, the empty set 0 is a subset of X. This is equivalent to asserting that every element of 0 is an element of X, which is vacuously true since there are no elements of 0. (from your link). That doesn't mean it contains only prime numbers. That means that the empty set is part of prime numbers (as it's part of every other set), by meaning of vacuous truth. :)
------------------------------ 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.
-
Forget my last posting it is trash. I didn't know what I wrote. Yes, I know what vacuous truth is. And I don't want to raise to question.
harold aptroot wrote:
clearly an empty set contains only prime numbers
That is wrong, because: any set X, the empty set 0 is a subset of X. This is equivalent to asserting that every element of 0 is an element of X, which is vacuously true since there are no elements of 0. (from your link). That doesn't mean it contains only prime numbers. That means that the empty set is part of prime numbers (as it's part of every other set), by meaning of vacuous truth. :)
------------------------------ 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.
-
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...[^]
Vijay Sringeri wrote:
I just loved it, But sadly.. This is what I want someone to answer for me.. :thumbsup:
Here you go: Knives are useful to cut for their sharp edges :laugh:
To alcohol! The cause of, and solution to, all of life's problems - Homer Simpson ---- Our heads are round so our thoughts can change direction - Francis Picabia
-
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
-
No, (by definition). /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
ihoecken wrote:
That means that the empty set is part of prime numbers (as it's part of every other set), by meaning of vacuous truth.
Ok, obviously
ihoecken wrote:
That doesn't mean it contains only prime numbers.
Why not?
Here is another true funny one: "The set of non-primes does not contain only prime numbers" :)
-
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...[^]
What is your question? The definition of primes is that they cannot be divided (within the set of whole numbers) by any other whole number other than 1 or the number itself. Everything else you write is an immediate consequence of that definition. Ok, a bit more in detail: - Any non-prime can be expressed as product of prime factors. With the correction, this is really an immediate consequence and occasionally used as an alternate definition of what is a prime (as in: any number not expressable in that way is a prime) - Prime factors can be used to check whether a number divides "N" ( N - Integer ) Lets say that N=n1*n2*n3, where n1, n2, n3 are the prime factors of N. If a number M is divisible by N, then there is some integer K, so that
K=M/Nor:K=M/(n1*n2*n3)Now multiply both sides with (n2*n3), and you getK*n2*n3 = M/n1As you can see there is an integerK1=K*n2*n3for whichK1=M/n1, and therefore n1 is a divisor of M. The same is true for n2 and n3 - both are divisors of M. Now that you know that if N is a divisor of N, then its prime factors are also divisors, you can turn that knowledge around: You test whether M is divisable by n1! If you find out that M is not divisible by n1, it means that it cannot be divisible by N either! - Prime factors can be used to find LCM and HCF Given two numbers N and M, you may express them as a product of prime factors N=n1*n2*...*nk and M=m1*m2*...*ml. (if N or M is a prime, there will only be one number n1 or m1 respectively. But that doesn't stop the following conclusion) HCF is the product of the factors you get from intersecting the two sets of prime factors. If you multiply that number by anything else, it will either no longer be a divisor of N, or of M. LCM is pretty similar, but I'm running out of time at this point ;) In any case, this property follows from the definition as well. -
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...[^]
Vijay Sringeri wrote:
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".
There is nothing in mathematics that is not based on other proofs, assumptions and/or definitions. And there is a proof for that lemma.
-
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 ?
Because God made it so.
Vijay Sringeri wrote:
How is it possible that, any number can be expressed as product of prime factors ?
Because the big bang for this universe of all the multiverses made it so.
Vijay Sringeri wrote:
What is it, which makes these prime numbers special ?
Gaea is the answer.
Vijay Sringeri wrote:
Can someone explain me this mystery behind prime numbers
Classic logic. All of mathematics and many of the theoretical parts of sciences are based on proofs, assumptions and/or definitions. There is nothing else. You can look to basic philosophy for the answer but it will not provide one. But it might provide a better understanding of why there is no answer.
-
The complete lack of any mention of Zero in this discussion has sucked out all meaning for me, and left me inside a total vacuum. Since Zero multiplied, or divided (except of course Zero divided by Zero), by any number, natural perverted, or even fractional, will always be Zero: therefore Zero is the Prime of Primes, not to mention that Zero raised to any power remains Zero, not to mention that subtracting Zero from, or adding Zero to, any number leaves the number unchanged ! That any number divided by Zero is an infinity (whose ordinality, or Aleph, among other possible infinities: is ultimate ?) which cannot be conceptualized within linearly digital Turing/Von Neumann theoretical computational design, and must be expressed by some "place-holder" like "undefined," or "NaN," or will, on a practical level, in many circumstances crash a computer: is proof of its sacred power. Zero is the unique singularity of the transition between positive and negative numbers, thus equivalent to the Omphalos, the stone of the navel of the geo-body of the cosmos, which for the ancient Greeks was located at the shrine of the oracle at Delphi. I propose to you that the infinite set of all possible prime numbers is contained within the infinity created by Zero divided by Zero like a tiny foot in a huge shoe: lots of wiggle-room no matter what #1 does, or does not, do. best, Bill
"Takuan Sōhō died in Edo (present-day Tokyo) in December of 1645. At the moment before his death, Takuan painted the Chinese character 'meng' ("dream"), laid down his brush and died."
-
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
Actually, when I went to school, I was taught that 1 WAS a prime number because a prime number is one that can't be divided by any other number other than itself or 1. 1 was excluded from the rules defining additional prime numbers because if it wasn't, there would only be one prime number: 1. It comes in handy to remember 1 is a prime number when playing Ken-Ken. (IE 4 squares in 6X6 array multipled together is 24. That's [1,1,4,6], [1,2,2,6]), or [1,2,3,4]. You can't have any more combinations because of the rules of Ken-Ken.
-
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:
What is it, which makes these prime numbers special ?
A prime number is one that can't be divided by any other number other than itself or 1. I learned 1 was a prime, but excluded from the rules defining additional prime numbers because if it wasn't, there would only be one prime number: 1. The definition of a prime number makes it special.
Vijay Sringeri wrote:
How is it possible that, any number can be expressed as product of prime factors?
One of the prime factors is 1. 1*3 is 3. ALL prime numbers can be multiplied by 1, therefore they are a product of prime factors. The rest of the numbers are products of prime numbers. (That you can then multiply 10 billion times by 1 if you want.) Actually, not any number is a product, any INTEGER number is a product of primes. You can never get 3.14157 as a product of primes. I take it back, ONLY positive numbers can be derived from prime products. 0 is not a prime, nor is -1. You can forget about immaginary numbers too. In the lexicon of numbering systems, primes are really limited.
Vijay Sringeri wrote:
Why this unique ability for prime numbers ?
It's defined this way. (These statements also implies all the restrictions I mentioned.)
-
Actually, when I went to school, I was taught that 1 WAS a prime number because a prime number is one that can't be divided by any other number other than itself or 1. 1 was excluded from the rules defining additional prime numbers because if it wasn't, there would only be one prime number: 1. It comes in handy to remember 1 is a prime number when playing Ken-Ken. (IE 4 squares in 6X6 array multipled together is 24. That's [1,1,4,6], [1,2,2,6]), or [1,2,3,4]. You can't have any more combinations because of the rules of Ken-Ken.
See this definition[^] of a prime number. According to this[^] source, 1 was considered a prime number in pre-19th century. /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
See this definition[^] of a prime number. According to this[^] source, 1 was considered a prime number in pre-19th century. /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
In your first link it says :Many questions around prime numbers remain open, such as Goldbach's conjecture, which asserts that every even integer greater than 2 can be expressed as the sum of two primes, and the twin prime conjecture, which says that there are infinitely many pairs of primes whose difference is 2. It doesn't say all primes, but that wouldn't be true for 2. I could believe it's true for all odd prime numbers. Also, your first link is Wikipedia which is well known to have misstatements posted in it. Back to Golbach, if 1 isn't prime, his conjecture is kind of screwed with 4 and 6, no? Your second link is interesting, but the same quote that says that pre 19th century 1 was prime also lists several sources that printed 1 as a prime number up to 1956. I'd say that was post 19th century, but I don't know when it was published. If 1 isn't prime you can't reach a prime number by multiplying two numbers together, which gets back to your Wiki link which makes a point of saying natural numbers can be reached by multiplying prime numbers. Which is kind of weird because that is the definition of what IS a natural number. Like I said, I was TRAINED that 1 is a prime number, that was more than a decade after that book was printed. Of course we weren't known for being current, I don't know how many 48 star flags I saw. I remember our first 50 star flag being brought into school with teachers being really relieved to finally get a current flag. (No , I wasn't born pre 20th century. :) Almost middle.)