Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**ZHero****Real Member**- Registered: 2008-06-08
- Posts: 1,889

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!

If two or more thoughts intersect, there has to be a point!

Offline

**ZHero****Real Member**- Registered: 2008-06-08
- Posts: 1,889

**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.

If two or more thoughts intersect, there has to be a point!

Offline

**Qwerticianist****Member**- Registered: 2010-05-13
- Posts: 3

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.

Offline

**ZHero****Real Member**- Registered: 2008-06-08
- Posts: 1,889

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.

If two or more thoughts intersect, there has to be a point!

Offline

**ZHero****Real Member**- Registered: 2008-06-08
- Posts: 1,889

**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].

If two or more thoughts intersect, there has to be a point!

Offline

**ZHero****Real Member**- Registered: 2008-06-08
- Posts: 1,889

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!

If two or more thoughts intersect, there has to be a point!

Offline

**simron****Real Member**- Registered: 2006-10-07
- Posts: 237

**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

Linux FTW

Offline

**reconsideryouranswer****Member**- Registered: 2011-05-11
- Posts: 171

ZHero wrote:

Definition of Prime number:A number which has EXACTLY TWO factors (divisors) is called a Prime number!

e. g.2has factors 1, 2 (exactly two factors) hence is a Prime number.3has 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.13has 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).

Signature line:

I wish a had a more interesting signature line.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

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)

**igloo** **myrtilles** **fourmis**

Offline

**wintersolstice****Real Member**- Registered: 2009-06-06
- Posts: 115

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 2the 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)*

Why did the chicken cross the Mobius Band?

To get to the other ...um...!!!

Offline

**Alex23****Member**- Registered: 2012-01-31
- Posts: 19

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.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

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?

**igloo** **myrtilles** **fourmis**

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

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)*

**igloo** **myrtilles** **fourmis**

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

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?

**igloo** **myrtilles** **fourmis**

Offline

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 220

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)*

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

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)*

**igloo** **myrtilles** **fourmis**

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 100,277

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

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.** **Thinking is cheating.**

Offline

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 220

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)*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 100,277

Hi;

Thanks for explaining your idea.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.** **Thinking is cheating.**

Offline

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 220

Hi Bobbym

You are welcome and thanks for your latex link.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 100,277

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.** **Thinking is cheating.**

Offline

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 220

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.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 100,277

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.** **Thinking is cheating.**

Offline

**Stangerzv****Member**- Registered: 2012-01-30
- Posts: 220

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.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 100,277

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.** **Thinking is cheating.**

Offline