[somehat sloppy but (hopefully)intelligible proof]
Odd positive whole integer powers of 3 will leave a remainder of 2 when divided by 3 (wish I knew how to make a congruence sign here).
proof:
2[sup]3[/sup] = 8 ,which is equal to a number(x=6) that is divisible by 3 plus 2 or x+2=2[sup]3[/sup]. Let’s also say 3=a
The next power of 2, and even one (4), is equal to 2(x+2)=2[sup]a+1[/sup].
Factored out we get 2x+4=2[sup]a+1[/sup].
Therefore this power is divisible by 3 with a remainder of 1 since 2x is obviously divisible by 3 and 4 =3+1.
The next power of 2, and odd one (5), is equal to
2[sup]a+2[/sup]=2[sup]2/sup
2[sup]a+2[/sup]=2[sup]2[/sup] x +2[sup]3[/sup]
2[sup]a+2[/sup]=2[sup]2[/sup] x +(x+2)
2[sup]a+2[/sup]=(2[sup]2[/sup] +1) x +2
since x is divisible by 3, 2[sup]2[sup]a+2[/sup][/sup] divisible by 3 with a remainder of 2. So we can now express this number as y+2=2[sup]b[/sup] where y is divisible by 3 and b=a+2. We can repeat this process with y and b just like we did with x and a. Every other power alternates either 2 or 1 remainders with odds having 2 and evens 1.
Finally ,2[sup]13466917[/sup] has a remainder of 2 divided by three since its an odd power.
2[sup]13466917[/sup]=x+2
2[sup]13466917[/sup]+13=x+2+13
2[sup]13466917[/sup]+13=x+15
since x and 15 are both divisible by 3 ,2[sup]13466917[/sup]+13 is divisible by 3
[/somehat sloppy but (hopefully)intelligible proof]
Boy I feel like a nerd.
I would like to point out that the numbers used in cryptography are much much much higher than the prime asked for in the OP, and much much much lower than the highest known prime. The larger number linked to by Jabba has, by my count, 256 digits when expressed in hex. 2[sup]13466917[/sup] -1 has, by my count, 11 Million digits in hex.
The test for primality of numbers of the form 2^p-1 where p is prime (candidates for Mersenne primes) is quite simple and, even better, is very amenable to binary arithmetic on computers. The original test I believe is due to Lucas. A few other similar forms also have known simple tests so it has not always been the case that the largest known prime is a Mersenne prime.
Such tests exploit the particular form of the number (and special properties about the associated algebras) so they do not work on any similar sized number in general. Hence they have no bearing on the OP.
Len Adelman and friends have come up with the fastest known deterministic tests for primality in general. If you want random tests then you’ll need to start with Gary Miller’s PhD thesis work. (Some of which is related to the extended Rieman hypothesis.) If you use random algorithms (which cryptographic systems use) you can either have: a very large candidate with an extremely high probablity of being prime or assurance of primality in a time that is random but highly likely reasonable. But of course they do not test all numbers up to the candidate.
Note that there are almost 3*10^29 primes of a hundred bits or less. This number is “infinite for all practical purposes”. No conceivable computer could be built to list all such primes in one person’s lifetime. A table of all such primes for the purposes of breaking RSA cryptography is totally out of the question. (Hence ScarletSteve’s notion in completely undoable and then some.) Since RSA-type systems recommend primes that are thousands of bits long, to factor/list such primes by brute force is on a scale of impracticality that cannot be described.
just wondering… if you took 2 prime numbers other than 2, multiplied them together, multiplied 2 to the result, and added 1, would you get a new prime? i was playing around with the concept in my head and it seems to work for the lower numbers. any thoughts?
In an attempt to redeem my shattered self esteem, can I say that if it turns out that High Deity is the greatest mathematician to post to this list, I should have a tiny fraction of his reflected glory for validating his theorum for 3 and 5, and for 3 and 11.
Okay, I guess college was a total loss, because I screwed up the proof.
M+1 must be either a prime, or divisible by primes not already in the set, therefore the set is incomplete. Adding M+1 or its prime factors to the set allows for the generation of a new M+1, ad infinitum.
And I evidently dozed off in university, too, because I forgot that large primes are useful in cryptography.
Sorry for the slow response - I had the hamsters counting to 30031. The point is, that if 2,3,5,7,11 and 13 are the only primes, then 30031, is prime, since it is divisible by none of them. Hence a contracidction, since it is a prime that is none of the above.
Of course, if 2,3,5,7,11 and 13 are the only primes you can deduce anything (eg. I am Bertrand Russel and the Pope) since a false statement implies anything (in normal logic).
As an aside, there are arbitrarily long sequences of consecutive integers which are not prime. The interval [(n + 1)! + 2, (n + 1)! + n + 1] contains no primes. Additionally, the sum over the reciprocals of all primes is a divergent series.
You got me. It’s in the third edition of Rudin’s real analysis book (“baby Rudin”, as I’m sure you’ve heard it called). I’ve never proved it, but I’ll take a look at it tonight. He gives a hint, so it’s probably at least a little bit complicated–maybe not long, but there’s some fine detail…
Is there some reason why a fairly modest computer program, using distributed computing techniques like Seti@home could not be set up to use Aristotle’s Sieve and just start listing. The numbers could be unloaded at “one end” as the process continued, and would produce the ongoing, changing answer to the OP.
Is such a thing possible? (I suspect yes, strongly enough to contemplate the program parameters for the last few minutes as I read the thread.)
Is such a thing useful? (Hey, these are mathematicians we’re talking about, any thing might be useful!)
Given a virtual terraflop computer, how large a prime are we talking about, in say, a year or so?
Tris
“What have you done to that cat? It looks half dead!” ~ Mrs. Erwin Schrodinger ~
Tris: Of course it’s possible. In fact, to the best of my knowledge, that’s the only known way to find all primes. But you’re not going to get very far–checking a number for primality by dividing it by all numbers less than its square root takes a while once you start to get to some large numbers (I wrote a program that found every factor of 2[sup]64[/sup] - 1 in a couple seconds, so we’re talking really big numbers).
btw, Eratosthenes devised that sieve, not Aristotle.
As another aside: Euclid’s proof doesn’t actually show that there are an infinite number of primes; rather, it shows that there is no largest prime. There are an infinite number of primes because the order relation on the naturals is antisymmetric, but I’m pretty sure I could devise a system where there are only two or three primes but no largest one.
Tris: Of course it’s possible. In fact, to the best of my knowledge, that’s the only known way to find all primes. But you’re not going to get very far–checking a number for primality by dividing it by all numbers less than its square root takes a while once you start to get to some large numbers (I wrote a program that found every factor of 2[sup]64[/sup] - 1 in a couple seconds, so we’re talking really big numbers).
btw, Eratosthenes devised that sieve, not Aristotle.
As another aside: Euclid’s proof doesn’t actually show that there are an infinite number of primes; rather, it shows that there is no largest prime. There are an infinite number of primes because the order relation on the naturals is antisymmetric, but I’m pretty sure I could devise a system where there are only two or three primes but no largest one.
Tris, actually it has been done. A group on UseNet a year or two ago used distributed computing to crack either an RSA or PGP encryption (I forget which one they broke). Anyway, essentially what they did was have the computers calculate primes up to 64 bit numbers and then test the numbers against the encryption. So it should be easy to take off the 64 bit limit and just have the computers continue to compute the primes.
I wrote a program in visual basic that wrote out primes using Eratosthenes sieve…it takes significantly longer for VB to write out the numbers on the screen than to actually calculate them.
I think crack is the wrong word. They had enough computers to brute force to recover a PGP key of pretty low number of bits using a really enormous amount of computer time. They would have to do the same for the next key.
64 bit numbers are not really big for PGP type encryption keys of around 1024 and 2048 are very common.
