Prime Numbers!!

ZHero · 2010-05-08 03:14:08

Hi everyone!

I'd like us all to take this opportunity to discuss all the stuff bout the "Prime Numbers" at 'One Place'!

It can be any simple or complex observation (like Facts, Properties, Relations, Theorems, Conjectures, Formulae etc etc) by you or somebody else.

Try to make it Simple by using your own words rather just copying/pasting material from somewhere else. Plz put it in an "Easy to Understand" way, even if its a Really Complex thing!

ZHero · 2010-05-08 07:13:22

Definition of Prime number: A number which has EXACTLY TWO factors (divisors) is called a Prime number!
e. g. 2 has factors 1, 2 (exactly two factors) hence is a Prime number.
3 has factors 1, 3 (exactly two factors) hence is a Prime number.
4 has factors 1, 2, 4 (more than two factors) hence is Not Prime. Such numbers are called Composite numbers.
13 has factors 1, 13 (exactly two factors) hence is a Prime number.

Note: We consider the positive natural number divisiors only.

Here are a few basic observations (proofs to be given later):

> 1 is neither prime nor composite. It has EXACTLY ONE factor.

> All prime numbers, except 2, are odd numbers.

> No other prime number ends in a (has its unit's place) 2 or 5 !

> The minimum difference possible between any two prime numbers is 2.
2 and 3 are the only exceptions which have a difference of 1.

Qwerticianist · 2010-05-13 21:46:49

Euclid's theorem proved that there are an infinite number of primes.

Imagine the biggest prime number ever discovered (call it P). Then take P factorial and add 1. Call this new number P! + 1 = Q. What's interesting is that no number between 1 and P will divide perfectly into Q, since all numbers between 1 and P divide perfectly into P factorial, and Q is P factorial + 1. Therefore any prime factors Q may have are either greater than P, proving there is at least one prime greater than P, or Q has no factors at all besides itself and 1, also proving there is at least one prime greater than P (namely Q itself). In fact it's not only at least one, but at least infinity, since any prime number greater than the original P can itself represent P.

Hopefully this makes sense.

ZHero · 2010-05-14 00:18:21

hi Qwerticianist

That's a very good explanation! Thx!!
Welcome to the forum......

> All prime numbers, except 2, are odd numbers.

Proof: Its self evident coz if a number (other than 2 of course) is not odd (i.e. even) then its divisible by 2 and hence its number of factors increases (i.e. more than 2 factors) and hence its not prime.

> The minimum difference possible between any two prime numbers is 2.
2 and 3 are the only exceptions which have a difference of 1.

Proof: consider two numbers x and x+1 (difference is 1).
we know that any number divided by 2 can give only two remainders viz. 1 or 0 .

we need to show that both x and x+1 cannot be prime.
for that, we'll show that exactly one of x and x+1 is divisible by 2.

let's say, x>2
CASE-I: x is divisible by 2.
hence, x is not prime.
CASE-II: x is not divisible by 2.
then x÷2 will give remainder 1?
hence, (x+1)÷2 will give remainder (1+1=2)÷2=0 --> x+1 is divisible by 2!
Note: if remainder ≥ divisor, then we divide the remainder by divisor again till the remainder lies in the range 0 ≤ remainder < divisor.
hence, both x and x+1 cannot be prime.

ZHero · 2010-05-30 03:37:22

Goldbach Conjecture: Every EVEN integer, greater than 2, can be written as the Sum of Two Prime numbers!
e. g. 7 = 5 + 2
18 = 5 + 13 = 7 + 11 etc.
This Decomposition of Integers into Prime numbers is called as Goldbach partition.

Goldbach Conjecture (Another Form): Every Integer, greater than 5, can be written as the Sum of Three Prime numbers!
e. g. 7 = 2 + 2 + 3
20 = 2 + 7 + 11 = 2 + 5 + 13 etc.

Goldbach Conjecture (Weak): All ODD Integers, greater than 7, can be written as the Sum of Three Odd Prime numbers!
e. g. 9 = 3 + 3 + 3
23 = 5 + 5 + 13 = 5 + 7 + 11 etc.

IMPORTANT: All these Forms of Goldbach Conjecture are STILL NOT PROVEN TO BE TRUE/FALSE!!
However, they have been Verified for numbers as large as 10[sup]14[/sup].

ZHero · 2010-06-14 22:56:12

This one's startling and was known to Diophantus in the third century. It was explored further by Fermat, and then by Euler and Gauss and subsequently by others.

Prime Series → 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...

Now delete all numbers which are 1 less than a multiple of 4 (i.e. 3, 7, 11 etc.)

New Series → 2, 5, 13, 17, 29, 37, 41, 53, 57, 61, 73 ...

Every Prime Number of this New Series is the Sum of Two Squares in a Unique Way!

e.g. 2=1²+1²

5=1²+2²

13=2²+3²

17=1²+4²

29=2²+5² and so on...

This extraordinary fact is related to Pythagorass theorem about the sides of a right-angled triangle!

simron · 2010-06-21 09:53:39

Primes in Computer Encryption
Huge primes are used in computer encryption, which was explained very well in a post by mathsyperson: (I'm paraphrasing, as the post was long, and I can't find it.)

mathsyperson wrote:

Let's say that Person A wants to send something through the mail to Person B. It is of considerable value, so A wants to make sure that it is not stolen. However, shady Person C (who happens to be the only mailman for miles around) wants to steal it. So Person A puts a lock on it. However, Person B doesn't have the key to the lock, so B puts another lock on it and sends it back to A. A takes his lock off, and sends it back to B. B takes off his lock, and the item is safe, even though both have probably spent their life's savings on locks, and shipping costs. With hackers, it's the same deal, except valuable items are replaced with valuable data, and locks are replaced with very, very large prime numbers.

Mersenne Primes and the Prime95 (GIMPS) Project
Mersenne primes are prime numbers of the form

. 3 is a Mersenne prime - it is equal to . GIMPS is an acronym for "Great Internet Mersenne Prime Search". It is a large program built up by many computers that are searching for Mersenne Primes with unused memory.

reconsideryouranswer · 2011-05-23 07:25:22

ZHero wrote:

Definition of Prime number: A number which has EXACTLY TWO factors (divisors) is called a Prime number!
e. g. 2 has factors 1, 2 (exactly two factors) hence is a Prime number.
3 has factors 1, 3 (exactly two factors) hence is a Prime number.
4 has factors 1, 2, 4 (more than two factors) hence is Not Prime. Such numbers are called Composite numbers.
13 has factors 1, 13 (exactly two factors) hence is a Prime number.

Note: We consider the positive natural number divisors only.

Use this instead:

Prime Number: A positive integer which has exactly two distinct positive integer factors (divisors).

John E. Franklin · 2012-01-19 02:30:15

This thread is a good place to discuss the primality tests, perhaps, and Fermat's little theorem...
(delete this post if want to since it contains only thread-choices, not math)

wintersolstice · 2012-01-20 09:16:39

a number in the form of

is called a Fermat number. The regular polygons that can be constructed with "straightedge and compass constructions" are those where the number of sides is:

- a Fermat number which is prime (Fermat Prime)
- a power of two
- a number made by multiplying a Fermat Prime by a power of two
- a number made by multiplying distinct Fermat Primes
- a number that can be made by multiplying a product of distinct Fermat Primes by a power of 2

a number in the form of

can only be prime if k is a power of 2

the only known Fermat Primes are

3,5,17,257,65537 (n=0,1,2,3,4)

Last edited by wintersolstice (2012-01-20 09:27:45)

Alex23 · 2012-01-31 04:28:48

Hello. I'm glad to now be a member of this cool forum. I love math and physics.

My contribution to this topic.

Make it as simple as possible but not simpler - Einstein
-Extra elementary definition of primes:
Prime numbers are those positive integers that cannot be written as a repeated summation of any smaller such number excluding 1 because it already creates all positive integers.
E.g. 10 can be 2+2+2+2+2 or 5+5. On the other hand prime number 7 cannot be written like that.

Ancient greeks visualized numbers as pebbles (before modern tradition with the number line). Prime number of pebbles cannot be organized to form a rectangle (plus its special case the square). Greeks for this reason called them linear numbers.

-Prime numbers are "attracted" next to numbers having as factors both 2 and 3, thus multiples of 6.
This is in other words the fact that prime numbers greater than 3, thus almost all of them, are of the form 6n + 1 or 6n -1, for n=positive integer.
In a table of positive integers arranged in 6 columns, prime numbers greater than 3 all fall in the 1st and 5th columns.
A definite non primality test for a number X is to divide X+1 and X-1 with 6. If in both cases there is a remainder, X is not prime.

-Explicit formula for e in terms of prime counting function π(χ).
This is a beautiful derivation that for some reason is not popular and not found in Wiki, Wolfram and other sites.

Starting with the Prime number Theorem and solving for e the following formula is derived:

Where the power of n can be interpreted as the prime number density. Indeed. n grows to infinity, but in the meantime the prime number density gets very very close to 0 limiting the expression to the constant of growth e.

The beauty of this formula is offset by the painfully slow convergence rate. Even for n=1E21 (a billion trillion) there is still a mistake of the order of 2%.
It's more like a beautiful connection than a workhorce of an equation.

John E. Franklin · 2012-02-02 22:48:35

it turns out 1 (one) might also be a prime number if you believe this formula for possible prime numbers.
This is an extension of the 6n+/-1 formula:

30n +/- 1,29,7,23,11,19,13,17 = possible places for primes. This is a subset of the 6n+/-1 because I have put in the 5 factor too!

It's just simple. Can't you see the pattern?

John E. Franklin · 2012-02-02 22:59:10

Or if you want a smaller subset, use this one!!
210n +/- 11,13,17,19,23,29,31...103 (only use primes in this list up to 103, or up to 209 if you want duplicates with near n's.

Since 209 is 11 times 19, maybe you should only go up to 199 and 11 + 199 = 210.
Maybe the 1 thing is useful though, because 211 is prime, so I suggest doing plus or minus 1 too in the formula
just like the 6n one.

Last edited by John E. Franklin (2012-02-02 23:03:41)

John E. Franklin · 2012-02-02 23:18:15

And if you want a smaller subset of the 6n -+1 formula, you can do this one:

2310n +/- 1, (skip 2,3,5,7,11), 13, 17, 19, 23, 29, 31, 37, 41 ... 1129, 1151, 1153.

1153 is the last prime under half of 2310 or 1155.

Pretty cool huh?? Do you believe it yet? Do you know what 2 * 3 * 5 * 7 * 11 is?

Stangerzv · 2012-02-02 23:42:56

I have formulated a generalize equation for Prime numbers and most of prime can be described using this equation. Few of the primes that lie under this formulation are Mersenne, Wagstaff and Fermat prime.

Here one of the primes using this formulation:

This prime is 2241 digits [11507067905299776611167663020
41590820051565995672304288311
24854137822480173849330291461
66087367460386669118580647249
30052681875635965617124940310
62326938026349750640865076202
03736318769140528216656033596
44722489898447864802153907872
27300511462471040094207321270
90554844559843700179014387094
18711097783152486213088339385
71160237500018069648323469545
68456524256016347658045443319
53262052348945357102129180166
13434453629744837793476024582
94674804197353103153987874654
59943642151201364331007751892
96425124029747391445436875529
28501871772617302046028319930
01243378185688089736375529835
79093892581749382816469541124
35425111220333572540153219290
48997955954591971369247628415
93681545530044116107712656841
34326600658063029626751434962
24123539953325905994586049538
94293795422174439212170655862
61629910962908281206699254406
40894865787684694841534937813
51183142744391230210968312832
97125852159307941535125376738
31691036872766879337859307696
89249971644131434793031660037
13686942780437566554379784876
39523010057682582534115066202
27471586245145046138132408605
29725343923440292133829627878
86192693980231385671987258056
19719084243186856232253678301
58320066502319045978542194300
68163673355668883889104829136
80636692160116791042330612047
67590855543616358502660982725
02499776086860852743643061075
42872410233457793232918649292
96194473399825261215374706935
09107041251706156044897741900
54577787182575412514440471591
17459515308966495842580774699
25448653647411653670217926543
38228436679228994630246306543
30382349143519853968166423962
34925730484716753057321805154
44191564580373361653042665048
76415258148510464374012060422
82647018701310201324806753679
28127886170683068570890544080
56336771271953474474032329183
69246979601097391109845011856
95642127480440609912594627485
36426506457693532707595612327
17594273764876973834356898572
32631247788528229678127928732
21469394190199916742560269984
83523768730518439732639512064
50553817892930225740351817482
69367973377232288579420198280
87658206805864897478365851624
50915566680066251071210443389
18934327827719202572717325462
08235698011349885492159938160
15222469285995577561649810793
70501655784930752373089650499
78224714356131112735263185117
99669421636956973444063380527
20122798020869243613385645059
85692174307382376534038923542
29745901]

Last edited by Stangerzv (2012-02-02 23:43:56)

John E. Franklin · 2012-02-03 00:02:15

Maybe we could get MIFun to add the ability to add dots to his online number line thingy by clicking on the marks or something. Maybe we could have 16 different colors 256 colors or maybe the number line could allow you to attach colored rings of varying sizes around any number. Or maybe we could get MIF to allow one to write something like 6n+1 and 6n-1 for n = 1 to 25 in red dots, and it would magically appear on the number-line he made. Wouldn't that be awesome!! Or maybe we could get Mif to come up with his own method to allow some sort of plotting numerous dots on his number line, and if the dots were a whole number, then they would be displayed because the user could choose only whole number dots or something, and then numbers not exactly whole maybe wouldn't be displayed, I don't know. What I'm thinking about is similar to have the ability to do the Sieve of Erostethenes on his number line, but do it manually, one number at a time, and the numbers like 2*3 and 2*3*5 and 2*3*5*7 and 2*3*5*11, you could tell it to merge the colors or you could have some other vertical hash marks with tiny dots above the number line for each equation you specify. Or you could say, I would like all "x=2n green dots at y=0.5 for n from 0 to 1000, and boom, 501 green dots would appear just above the number line at y=1/2 for the even numbers from 0 to 1000. Wouldn't that really be a fun experiment???

Last edited by John E. Franklin (2012-02-03 00:02:54)

bobbym · 2012-02-03 06:47:41

Hi Stangerzv;

Going through vixra I do not see a paper on your method of prime generation. Can you provide a little bit more on that prime you have generated in post #15

Stangerzv · 2012-02-03 12:17:54

Basically the formulation is a conjecture and I need some time to prove it. In the old days, Mersenne, Wagstaff and Fermat did derive their equations by playing with the equations and numbers. The generalize equation for prime was found during my research on symmetric function involving Fermat's Polynomials which is in stepping down of 2nd power. This function was actually used by Euler and Sophie Germaine to prove p=3&5 for Fermat's Last theorem using infinite descent method. I have developed a function using sums of power for arithmetic progression and found out there is a factorization pattern in the Fermat's last theorem when we set n=2. I named this function rule of division of symmetric function and from this generalize equation we can get infinite sub-formulations for primes like Mersenne, Wagstaff and Fermat. The thing that amazes me is that the equation is so simple but it can do a lots of things. Using this equation, I can even generated bigger primes than Mersenne at smaller prime input. The prime above was obtained by using p=281 and symmetric function (10002 and 10003). My limitation is that I need bigger computing power to check for the primality test. Here the generalize equation for prime:

Where t is the mutiplier and for integer Ps "p" should be odd/prime otherwise Ps would be categorised as special cases. Fermat's prime falls under this special case so as with the Pythagorean's triple. If Ps is prime then p must be prime and Ps not necessarily prime if p is prime. The prime Ps primality test is done using Elliptic Curve Method (ECM).

this one gives you 2241 digits prime

and this one gives you 849 digits prime

Other primes

Last edited by Stangerzv (2012-02-03 12:50:22)

bobbym · 2012-02-03 12:58:07

Hi;

Thanks for explaining your idea.

Stangerzv · 2012-02-03 13:18:50

Hi Bobbym

You are welcome and thanks for your latex link.

bobbym · 2012-02-03 21:29:39

Hi;

You are welcome!

My limitation is that I need bigger computing power to check for the primality test.

What method are you using? If you are using ECM there are better ways.

Stangerzv · 2012-02-03 22:53:51

Hi Bobbym

I am running quad core i5 with 8gb memory and it took me around a day to check the primality of that 2241 digits prime. I am using ECM program written by an Argentinian's programmer. You can get his program at alpertron dot com dot ar. His program only could test up to 20,000 digits. I think if someone could write a primality checker for larger prime using the formulation I got, it would be kool. I am working to get first 1 million digits prime using the formulation but I think it is going to take for ages. Got a friend who tried to write the program but he quit. Can you suggest me the better way to check the primality accurately and fast? From the equation, theoretically we could get bigger prime than the Mersenne because it allows bigger numbers in the equation.

bobbym · 2012-02-03 23:06:37

Hi Stangerzv;

Depends on what you mean by better. The ECM is for factoring a number not for proving or disproving primality. Factoring is much harder problem than proving primality.

There are two types of tests for primality that I know of. The AKS developed by 3 Indian fellows and Rabin Miller which is a probabilistic test.

Stangerzv · 2012-02-03 23:46:48

Hi Bobbym

I haven't try AKS method yet, if you could provide me the link of any program using that method let me know. I know, ECM is not for proving and disproving but the guy had incorporated Rabin-Miller probabilistic test in the program and it would tell you whether the number is prime or not at the end of factorization. Anyway, it would be a great help if you could provide me a link where to download or use AKS method. For your information I haven't got into programming for quite long time and to write a program for checking primality on my own would take some times.

By the way, thanks for your suggestion and idea it is a great help.

bobbym · 2012-02-03 23:55:08

Hi;

I am looking for one. I have one written for Mathematica but not for anything else just yet.

The Miller - Rabin does not need to factor the number. It is quite fast, but it is not deterministic. It can only provide a probabilty that the number is composite. Of course this probabilty can be made very, very small.

Math Is Fun Forum

#1 2010-05-08 03:14:08

Prime Numbers!!

#2 2010-05-08 07:13:22

Re: Prime Numbers!!

#3 2010-05-13 21:46:49

Re: Prime Numbers!!

#4 2010-05-14 00:18:21

Re: Prime Numbers!!

#5 2010-05-30 03:37:22

Re: Prime Numbers!!

#6 2010-06-14 22:56:12

Re: Prime Numbers!!

#7 2010-06-21 09:53:39

Re: Prime Numbers!!

#8 2011-05-23 07:25:22

Re: Prime Numbers!!

#9 2012-01-19 02:30:15

Re: Prime Numbers!!

#10 2012-01-20 09:16:39

Re: Prime Numbers!!

#11 2012-01-31 04:28:48

Re: Prime Numbers!!

#12 2012-02-02 22:48:35

Re: Prime Numbers!!

#13 2012-02-02 22:59:10

Re: Prime Numbers!!

#14 2012-02-02 23:18:15

Re: Prime Numbers!!

#15 2012-02-02 23:42:56

Re: Prime Numbers!!

#16 2012-02-03 00:02:15

Re: Prime Numbers!!

#17 2012-02-03 06:47:41

Re: Prime Numbers!!

#18 2012-02-03 12:17:54

Re: Prime Numbers!!

#19 2012-02-03 12:58:07

Re: Prime Numbers!!

#20 2012-02-03 13:18:50

Re: Prime Numbers!!

#21 2012-02-03 21:29:39

Re: Prime Numbers!!

#22 2012-02-03 22:53:51

Re: Prime Numbers!!

#23 2012-02-03 23:06:37

Re: Prime Numbers!!

#24 2012-02-03 23:46:48

Re: Prime Numbers!!

#25 2012-02-03 23:55:08

Re: Prime Numbers!!

Board footer