Prime # Discussion

[master_q 0]

Prime # Discussion

 

You know the kind of # everyone loves. The #s you hear about all the time in movies and in Star Trek. Well even if you don’t really know what they are, then you probably have heard of them one time.

 

Just in case you don’t know . . . .

 

A number n is a prime # if only 1 and n are divisible by n

Example) 2, 3, 5, 7, 11, . . . . are prime #s

 

This means that if only 1 and the # it self can be divided into a whole #, then the # in question is a prime #.

 

A number that is not a prime is called a composite

 

From what I know the biggest prime we know of is:

2^3021377 -1

(This # would take around 500 pages to write out in regular form)

But that was a few years ago so I would bet that we now know of a bigger one

 

What are prime #s so important?

 

I would say a majority of people that know what a prime # is don’t really know why they are important. Someone might know that they don’t really have a direct pattern, but that’s just one thing and is not the most important thing about them.

 

Number Theory!

 

Fundamental Theorem of Arithmetic:

This was a theory developed by Euclid.

It says that any natural # > 1 is either prime or else can be expressed as a product of primes! Now that’s really neat if you think about it. It says that prime #s are the building blocks from which natural #s are constructed and understanding the prime factorization of a # will almost tell you everything about the # in question. This really opens the doors to many things in math. For example understanding factoring or even making codes are deeply connected in understanding what a prime # is.

 

Well as you probably know primes become less and less common the higher you go up. The ratio between primes and composites goes down the more and more you go up (I’m referring to primes:composites).

 

Even though primes become less and less we still have primes continue to go forever.

Here’s a little proof (and it’s pretty simple):

 

(NOTE: n is for #, p is for prime)

 

p₁, p₂, p₃, p₄, . .

p₁ = 2

p₂ = 3

p₃ = 5

P₄ = 7

. . .

 

N = p₁p₂ . . . p_n

We need to show that there is a p beyond pn

N = p1p2 . . . pn + 1

When you multiply all of the p’s and add 1, N must be > p_n

 

If N equals a prime, then there must be a prime larger then p_n

If N is not a prime, then it must be divisible by a prime; (p)

 

When dividing N by any of the primes (p₁p₂ . . . p_n) you will get a remainder! We know that there are prime factors that make up the # and if none of them make that # up this means that another prime must be divisible by N and as a result that # (p) must be greater then p_n!!

 

As you can see primes are pretty neat! I hope that some of you will make some comments on the issue on primes because there are a lot of grounds to them. (And I’ll probably post some more neat things.)

 

 

Master Q

StarTrek_Master_Q@yahoo.com

[Xeroc 0]

Actually, Master_Q, the largest prime is: 2^13466917-1. It has 4053946 digits! The top 10 primes so far are:

2^13466917-1

2^6972593-1

2^3021377-1

2^2976221-1

3 * 2^2145353+1

62722^131072+1

2^1398269-1

1540550^65536+1

1483076^65536+1

1478036^65536+1

 

 

Primes - very interesting stuff!!!

 

It is also kind of interesting how many encryption algorithims are based on the difficulty of factoring huge numers into two large primes! A type of encryption that will become obsolete when quantum computing comes aound because quantum computers will be able to factor them in just minutes!

 

Also, the number 137 is also prime!

[master_q 0]

Actually, Master_Q, the largest prime is: 2^13466917-1. It has 4053946 digits!  The top 10 primes so far are:

2^13466917-1

2^6972593-1

2^3021377-1

2^2976221-1

3 * 2^2145353+1

62722^131072+1

2^1398269-1

1540550^65536+1

1483076^65536+1

1478036^65536+1

 

 

Primes - very interesting stuff!!!

 

It is also kind of interesting how many encryption algorithims are based on the difficulty of factoring huge numers into two large primes!  A type of encryption that will become obsolete when quantum computing comes aound because quantum computers will be able to factor them in just minutes!

 

Also, the number 137 is also prime!

Thanks for the update. My source is getting old - that’s why I said it is probably higher

 

It is true once we get quantum computers then figuring out things like primes will be a lot faster then what we have now. Pretty neat stuff

 

 

Master Q

StarTrek_Master_Q@yahoo.com

[master_q 0]

One of those neat things about primes comes from Goldbach’s Conjecture.

 

Maybe it is not the biggest thing, but I find it interesting.

 

This whole conjecture actually came about when Goldbach wrote a letter to Euler. Goldbach said that he thinks that every even number greater then 2 is a sum of two prime, but he did not know how to really make a direct proof. Even today we don’t really have a direct proof. However, it has been checked (probably the trillions and trillions - LOL).

 

Well that was just something interesting, but the next thing I really want to post.

 

Fermat gave us a neat check (well it does not always work) to see if the # in question is a prime or is not.

 

If any # “p” is a prime and any # “a” is < p, then a^p-1 – 1 will be divisible by p. Now this is a really important principle Fermat gave us.

 

For example)

 

2^n-1 - 1

In this we want to find out if n is a prime then we have to figure out if it is divisible by n.

One of the problems in something like this (as I stated) is that there is no guarantee that it is a prime if we figure out that it is divisible by n. So that’s one of the problems and as far as I know it has been solved, but the method is a bit different. I don’t know what it is called off the top of my head.

 

Do you know what it is called Xeroc?

I know it starts with a A (or at least I think) - something like that

 

Ok, to get back another problem is that figuring out something to the n could take a very long time. So we have to shorten it a bit and this really is needed once you deal with larger #s. If for example you were trying to figure out a # that was really big and had the computer do it, then it might take hours and hours. However, we can shorten it. (And that’s the fun part)

 

So . . .

when dividing n into 2^n-1 - 1 you don’t have to figure out the multiples of n (as in the power) because multiples will cross cancel! And again the aim in solving is to see if the remainder is zero (but like stated multiples of n will not affect the remainder)

 

I’m sure many of you know in math (because it’s pretty elementary) mod

 

(Like if we have 5 mod 2 it will equal 1 because we have a remainder of 1)

 

 

Let’s test 61 to see if it’s a prime

However, we don’t want to figure out what 2⁶⁰ is . . .

 

We know that 2⁶ = 64 and because we know that we can deduce that 2⁶ mod 61 = 3. Remember: {2³⁰ = (2⁶)⁵} . . .

 

2³⁰ mod 61 = (2⁶ mod 61)⁵ mod 61 = 35 mod 61 = 243 mod 61 = 60

 

Now because of that . ..

 

2⁶⁰ mod 61 = (2³⁰)² mod 61 = (2³⁰ mod 61)² mod 61 = 602 mod 61 = 3,600 mod 61 = 1

 

 

(2⁶⁰ – 1) mod 61 = 0!!

 

So now we know that it is a prime! (Or in the very rare cases it might not be)

However, I’m not sure how to do the other method to make 100% sure.

 

Xeroc, if you could find (or if you know off the top of your head) what that method is called that would be a big help. And if you know how to do that method I would really like that (I’m not quite sure how) - Thank you

 

 

Master Q

StarTrek_Master_Q@yahoo.com

Edited June 28, 2003 by master_q

[master_q 0]

Xeroc, did you find out what it is called or the exact method of how it is done?

 

I was trying to look it up, but I have not been that successful. I’m going to check out a few books to see if I can find it. I hope I will.

 

Please reply to tell me if you found it (or have not) ASAP Thank you

 

 

Master Q

StarTrek_Master_Q@yahoo.com

[Xeroc 0]

Xeroc, did you find out what it is called or the exact method of how it is done?

 

I was trying to look it up, but I have not been that successful. I’m going to check out a few books to see if I can find it. I hope I will.

 

Please reply to tell me if you found it (or have not) ASAP Thank you

 

 

Master Q

StarTrek_Master_Q@yahoo.com

Unfortunately, no - I should know this but it slipped my mind. If I find out I'll tell you ASAP!

[master_q 0]

Unfortunately, no - I should know this but it slipped my mind.  If I find out I'll tell you ASAP!

One of the things that sparked this topic was I was talking to someone about prime #s and the whole process for Eratosthenes Sieve. So he and I were making the algorithms and things to that nature. Once we graphed on the computer a greatest integer function (he’s a programmer. I only know some basics of programming. When it comes to computer I know more about the hardware and things like the OSI) and then we had the program cross out #s that were divisible by x^0.5 (where x of course was a floor function). It turned out ok and everything. We got our primes, but what we really want to do is integrate this method with Fermat’s modified property (what ever that is called and how ever you do it).

 

So this is the general outline out what we really have and how we are basically correlating everything:

 

(All of this is “less then or equal” to or “greater then or equal to” - just as note. I did not want to make things longer then they have to be)

 

(Let’s say we have an odd integer)

Now this is just computing back into the fundamental theory and getting that out Fermat’s property . . . (So I’m going to show that work I have)

1 < a < n - 1. So if a^8 --- 1 (mod n) or a^((2^i)s) --- -1 (mod n) for 0 < j < r - 1 (well here is a problem that I see and I’m sure you would - this is a “if” event also and again ties into that grander picture.), then n will pass the test. (A prime # will pass the test for a)

So this would give us (1 + o (1)))lg n multiples (mod n)

 

(NOTE: lg = log bas 2)

 

But this again is an incomplete picture.

 

Now this we are not fully sure of, but I think that it is. It is really a toss up. And maybe is the result for a lack of really knowing much about Complexity Theory. That might be it. I don’t know. I’m sure you know (well you should know) as I do accepts of this theory. Other then that I’m at a lost a bit LOL

 

Well now that I think about it. I take it back. The paragraph above this makes me look like I don’t know what I’m talking about. The theory fits (as it would), but figureing out the things like the algorithms and just the general method is the actual type. Thats a key thing!

 

I’m not sure if it is considered (or maybe it was actually later taken out) as in considered a p-probelm.

 

Do you think this a P-type problem, Xeroc?

Thank you

 

 

(But this again takes us out more to the actual factorization, but I guess that is needed to fully corelate Fermat’s property)

 

What do you think?

 

 

Master Q

StarTrek_Master_Q@yahoo.com

[master_q 0]

I found it

 

If you look in the Mathematics journal of Computation 42 it has info on the APRCL test.

 

It is pretty complex and very hard to explain and I don’t know all the facts about it, but it is pretty interesting stuff.

 

 

Master Q

StarTrek_Master_Q@yahoo.com