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:
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.)
-
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.)
You make several good points. I was also born close to the middle of the 20th century and was taught that 1 wasn't a prime number. I leave it to the mathematicians to cast the deciding vote. /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
Math is broken.
ihoecken wrote:
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.
Why is that a problem? That's just the result of a vacuous truth. ∀x∈X:P(x) and ∀x∈X:¬P(x) can both be true, that just implies that X is the empty set. No problems there. And the equivalence ∀x∈X:P(x) = ¬∃x∈X:¬P(x) is a real thing. So there you go, the statements are equivalent, but that means that an empty set can be typed (because a type is just a predicate as well - the elements of the empty set are of all types simultaneously but lets not get hung up on that, they don't exist anyway), and thus math is broken. QED.
harold aptroot wrote:
and thus math is broken
yes, we know math is broken since the russell paradox.
harold aptroot wrote:
but that means that an empty set can be typed (because a type is just a predicate as well - the elements of the empty set are of all types simultaneously
you really want to get on the Principia mathematica? we both know that Kurt Gödel was the only one crazy enough to ready and understand it all.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
I don't get any of these arguments. There is nothing in it, yes, so what? "The nothing" can, so far, still be "zero prime numbers". Or zero of anything else for that matter because the same vacuous truth of "all elements are of type t" is true for all t. The definition of the empty set doesn't say anything about that.
ihoecken wrote:
Mathematically it's not true that it contains prime numbers. The definition says: There is nothing in it.
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.
harold aptroot wrote:
because the same vacuous truth of "all elements are of type t" is true for all t.
yes, but that statement only holds true if there is an element. the empty se contains none.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
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?
harold aptroot wrote:
ihoecken wrote:
That doesn't mean it contains only prime numbers.
Why not?
I'm no mathematician, but i guess it's because the empty set is also a subset of the set of all prime numbers. The thing is: as the empty set contains no elements, you can't proof nothing about the type of it's elements. This is one of the problems the Principia Mathematica had, that led Kurt Gödel to state that mathematica is incomplete.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
Vijay Sringeri wrote:
Why this unique ability for prime numbers ?
It is not a unique ability for prime numbers, it is just that these numbers can not be sub-divided any further. You can find the LCM and HCF using any numbers, but they will always be a combination of prime factorials, so using prime numbers is far easier.
Vijay Sringeri wrote:
How is it possible that, any number can be expressed as product of prime factors ?
Essentially because a prime number can not be divided and a non prime number can be. Any number n that is not prime has at least two divisors that are not 1 and n. These divisors are either prime or non prime. If they are non prime then by definition they follow the same rule as n. These numbers are smaller then n, so repeating this rule will always result in only prime divisors.
Vijay Sringeri wrote:
What is it, which makes these prime numbers special ?
The fact that they are prime and can not be divided.
Member 2053006 wrote:
Any number n that is not prime has at least two divisors that are not 1 and n.
what about 4 ? AFAIK, for has only one divisor thats not 1 or 4, and it's 2...
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
harold aptroot wrote:
and thus math is broken
yes, we know math is broken since the russell paradox.
harold aptroot wrote:
but that means that an empty set can be typed (because a type is just a predicate as well - the elements of the empty set are of all types simultaneously
you really want to get on the Principia mathematica? we both know that Kurt Gödel was the only one crazy enough to ready and understand it all.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
BillWoodruff wrote:
That any number divided by Zero is an infinity
Normal mathematics defines that as undefined, not infinity. A divisor that approaches an infinitely small value produces a value that approaches infinity.
I think he was talking about Lim(1/0), that is infinity. for any other operation, 1/0 is undefined, just because no one can think what would be the result.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
Because the "secret" factors A*B = C, with A prime and B prime, are the holy grail to break RSA, the asymmetric keys algorithm used world while to enforce security, with SSL, HTTPS, VPNs... Ruffly speaking, in RSA itself, C is "the public key" and its factorization, A and B "the private key". It is straightforward to find the factors for small numbers, but it happens that it is very hard to find such factors for large numbers (indeed - you need to extensively search for them). To date it has been possible to break up to a 768 bit RSA key (C is 768 bits long) by using a cluster of many hundred servers. Larger keys (1024, 2048 bits) are still considered secure (needed hundred years of cluster computing time for one single key) - and they will, until some strong improvement will be performed in number theory.
-
I think he was talking about Lim(1/0), that is infinity. for any other operation, 1/0 is undefined, just because no one can think what would be the result.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
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.
I don't think those statements are equivalent, hence the issue. This is somewhat tangential to my favorite mind-bender: you're in a room with an angel, a devil and two doors, one leading to heaven, the other to hell. You don't know which being is the angel or devil, nor do you know which door leads the way. The angel will always tell the truth, and the devil will always lie. You can ask one being one question in order to save your soul; what do you ask? The answer to this question is similar to the issue of asserting those two statements are equal.
-
Limit(lim) is still a convergence sequence. Which is the same as what I said. And equating it to infinity is a misrepresentation of what it means mathematically.
yes, you are right, i couldn't remember of the correct simbol to use, so i used equals, as that was what my mathematical analysis (that's how it's called in my universsity) used.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
-
harold aptroot wrote:
because the same vacuous truth of "all elements are of type t" is true for all t.
yes, but that statement only holds true if there is an element. the empty se contains none.
I'm brazilian and english (well, human languages in general) aren't my best skill, so, sorry by my english. (if you want we can speak in C# or VB.Net =p)
It is no more wrong to say that ∀x∈0:x∈T than it is to say that "all Leprechauns are Irish". There is no claim that ∃x∈0:x∈T ("there exists an Irish leprechaun"). The negation of my claim is that ¬∀x∈0:x∈T ("not all leprechauns are Irish") which would have to be proven by showing that ∃x∈0:x∈T ("there exists a non-Irish leprechaun"). The (minority) mathematical faction of Constructivism holds that proof by negation is invalid; the obvious falsity of the negation is insufficient to proove the proposition. There seem to be more constructivists in this thread than have ever gathered before in one place. An argument Harold already posed is relevent to address this stance: The empty set is a proper subset of every other set. If an argument references a typed set, 0 must inherit the type. If it were allowed to not be of the referenced type, it could not have been a subset of the typed set. Harold is correct is typing 0 as exclusively prime...remembering that is can also be exclusively type as non-prime in another argument on another day! Cheers! [Sorry to bump so late in the game. I was dead-set against Harold and Bob (almost angry with them for their obstinance!) for a full hour of parsing this thread before their arguments convinced me that my intuitive distaste for their proposition was wrong.]