Posted on 04/11/2006 3:08:56 PM PDT by LibWhacker
Sure, 5:46 is happy hour. ;-)
One isn't prime.
It should be 2x3x5, which equals 30, but of course 5 is disregarded, because it won't multiply to equal 42.
You sure 1 isn't prime? It can only be divided by itself and, well, 1.
The ancient Greeks regarded 1 as a prime.
Today it is not.
Mainly because a lot of important theorems would be false
if 1 were a prime.
I'll buy that.
Huh?
How would showing that the relative error in the approximation
pi(x) = Li(x) + error
(where pi(x) is # primes <=x and Li (x) is the integral from 0 to x of dt / ln(t) )
is O(sqrt(x)ln (x)) rather than some larger function, break any codes?
To crack the RSA system, you need a way to factor numbers that are hundreds, if not thousands, of digits long. AFAIK, the RH does not provide a factoring algorithm.
Yeah, one's not prime.
A prime number, by definition, is a number that can only be divided by two numerals, itself, and one. One can only be divided by one, which means that there aren't two digits, so it falls out.
I find this definition especially irritating, because "prime" is a derivate from Latin meaning "one" or "first". So it's aesthetically displeasing, from a linguistic standpoint, that the number 1 should NOT be "prime". But it's not, according to the definition.
The more modern way of classifying integers is
0 additive identity
+/- 1 units
primes
composites
When you get into algebraic number theory, you deal with things like the so-called Gausian integers, which are complex numbers whose real and imaginary parts are both integers.
Then the classification is
0
+/-1, +/-i
primes
composites
The real reason 1 isn't counted as prime is that would make the unique factorization theorem more complicated:
every integer is the product of a unit and a bunch of primes, and in one way only (except for the order of the factors)
as opposed to
every integer is the product of a bunch of primes, and in one way only (except for the order of the factors, and the fact that any number of 1's can be multiplied in, and any even number of -1's)
ping
I based my statement on this article.
http://www.finextra.com/fullstory.asp?id=12452
The article presumes
that the extra knowledge
that would enable us to prove the R.H.
also would enable us to factor composite numbers.
Not unreasonable, but not established.
Take it with a grain of salt. I think the authors are confusing factorizing with primality testing and proving.
Search the web for Miller-Rabin test (there are a number of good references)
Roughly speaking, there is an algorithm for testing for compositeness. Given N, and another number a, it can return either "N is composite", or "can't say whether N is prime or composite."
It can be proved that if N is in fact composite, then the odds are 3/4 that the algorithm will return "N is composite". So if we run the algorithm x times with x different values of a, and it reurns "can't say" each time, the odds that N is not prime are (1/4)^x; if x is large enough, people will call N a "probable prime".
The trick is actually proving that N is prime using this test. It can be proved that if every value of a less that the square root of N is tried, and the algorithm never says "N is composite", then N is in fact prime. But this is impractical for N's with hundreds of digits.
If the extended RH is true, then you only need to use values of a less than 2(ln N)^2, which is much more practical.
What this means is that if you can find a number that is composite, but passes the Miller-Rabin test for all values of a less than 2(ln N)^2, then you have disproved the ERH.
If the test comes back and says N is composite, this is true but it gives no hint as to what its prime factors are
I don't even think it's that reasonable. The RH (and GRH and ERH) are analytical or statistical statements, and lead to conclusions like "there must be a prime in this interval", or "there must be a quadratic non residue in that interval mod N", and so on and so forth.
I'd love to see a really fast factoring algorithm, but I just don't see how proving the RH or any of its variants is likely to lead to it.
This all is very vague
but one can conceive of a theorem
stating that any prime factor must lie in a certain specified interval or intervals.
Intuitively
it seems that a proof of the RH must involve an enormous new insight
into the distribution of prime numbers
and the consequences will be stupendous.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.