ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

The Magic of Prime Numbers

Updated on November 10, 2013
Carl Fridrich Gauss (1777-1855), a German mathematician and physicist. (source: corbisimage)
Carl Fridrich Gauss (1777-1855), a German mathematician and physicist. (source: corbisimage)


As R. Courant and H. Robbins say in his famous book "What is mathematics", most statements in mathematics are concerned not with a single object – like a concrete number, but with a class of objects, like all even integers,

2, 4, 6, 8,... or

the class of all integers divisible by 3,

3,6,9,...

In number theory, of a fundamental interest is a class of all primes or prime numbers. While numbers like 10, 12 or 15 can be represented as a product of smaller factors,

10=5*2,

12=3*2*2,

15=5*3,

prime numbers cannot be resolved in that way.

More precisely, prime number is an integer, greater than 1, which is divisible only by itself and one. Thus, in the set of natural numbers prime numbers are

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...

One of the first questions related to prime numbers is whether there is finitely of infinitely many such numbers. The answer is found by a Greek mathematician Euclid: there is infinitely many primes in the set of natural numbers. Although, in general, proofs of the mentioned facts are out of the scope of this articles, we will give this proof since it is rather simple and a very nice example of a proof by contradiction.

There are two distinct types of natural numbers:

  • prime numbers
  • composite numbers.

The number one is neither prime nor composite.

Firstly, we conclude that there are only two possibilities: the number of primes is either finite or infinite. Now suppose that the number of primes is finite and all prime numbers are p1,p2,...,pn. Let construct the number A

A=p1*p2*...*pn+1.

Obviously, A is grater than any prime p but it is not divisible by any of p. In case the assumption is true, than A should be divisible by at least one of the primes. However, the remainder is always 1. So, since we have only two possibilities here and one of them leads to a contradiction, we conclude that alternative statement is the right one.


Primes – building blocks of integers


Prime numbers can be understood as building blocks of the set of all integers. For example,

144=2*72=2*2*36=2*2*2*18=2*2*2*2*9=2*2*2*2*3*3=24*32,

165=3*55=3*5*11.

Every composite number (i.e. the number which is not prime) can be represented as a product of primes. Moreover, one remarkable property holds for this factorizationit is unique! Every integer (greater than 1) can be factored into a product of primes in only one way. The rule is known as the fundamental theorem of arithmetic.


Ulam spiral - graphical presentation of primes in the plane

Regular pentagon. Gauss has shown that triangle, pentagon, then 17-gon i.e. polygons which side is a Fermat prime can be constructed by rule and compass only. (source: flysky)
Regular pentagon. Gauss has shown that triangle, pentagon, then 17-gon i.e. polygons which side is a Fermat prime can be constructed by rule and compass only. (source: flysky)

Searching for a prime formula


The Eratosthenes sieve (see the video below) is a procedure of listing all the primes up to any given integer N. Firstly we strike out all those numbers up to N which are multiples of 2, then all those remaining which are multiples of 3 and so on until all composite numbers have been striking out.

Fermat primes

However, mathematicians were looking for more elegant way of generating the primes, they are seeking for a formula producing all the primes. A famous French mathematician Pierre de Fermat (1601-1665) made the conjecture that all the numbers of the form

F(n)=2n2+1

are prime numbers. One can easily check that this is true for n=1,2,3,4:

F(1)=22+1=5,

F(2)=17,

F(3)=257,

F(4)=65537.

However, the conjectures is not true since yet for F(5) we have a composite number. Namely, in 1732 a Swiss mathematician and physicist L. Euler (1707-1783) discovered that F(5)=641*6700417, thus F(5) is not prime.

Prime numbers of the above form are called Fermat primes. Although Fermat formula was false for the purpose to produce all primes, there is a remarkable relation between the Fermat primes and the existence of a construction of a regular plane polygon with ruler and compasses only. As it is proved by a German mathematician C. F. Gauss, regular plane polygon with p sides, where p is a prime, is capable of such a construction if and only if p is a Fermat prime. (So, it holds both: if such a construction is possible then p is a Fermat prime, and if p is a Fermat prime than construction is possible.)

Unsolved question at present is whether there are finitely or infinitely many Fermat primes.

p
Mersenne Primes
Discoverer, year
13
8191
anonymus, 1456
17
131071
Cataldi, 1588
19
524287
Cataldi, 1588
31
2147483647
Euler, 1772
Some Known Mersenne Primes

Mersenne primes

Mersenne number is a number of the form Mn=2n-1, which means that Mersenne numbers consist of all 1s in base 2.

When the number of the form 2n-1 is prime it is called Mersenne prime, after a French scientist M. Mersenne (1588-1648). Namely, Mersenne conjectured that the numbers 2n-1 were primes for n=2, 3, 5, 7, 13, 17,19,31,67,127 and 257. Letter it was shown that the correct list is 2,3,5,7,13,17,19,31,61,89,107 and 127. It is known that if 2p-1 is prime then p is prime. Mersenne primes are of particular interest in providing examples of large prime numbers. For example,

244497- 1 is the 27th Mersenne prime,

243112609 -1 is currently the largest known prime number.

Density of primes

Finally, mathematicians turned to investigation of the distribution of primes among the natural numbers instead of looking for an exact formula for primes. Let Pn be the number of primes among the integers 1,2,...,n. Instead of looking for an equation resulting with Pn for a given n, we are going to deal with the ratio Pn/n, which can be understand as a "density" of primes. It can be shown that this ratio decline with n logarithmically. More precisely,

lim Pn/n =1/ln (n) when n goes to infinity.

This result, describing the distribution of primes, is known as the prime number theorem.

There are also other nice rules prescribing the presence of primes in the whole set of natural numbers. One remarkable fact showing that primes are "well distributed" is that for every n>1, there is always a prime between n and 2n (Bertrand's postulate).

After many effort of a few scientists, a German mathematician L. Dirichlet (1805-1859) finally succeeded to prove that in an arithmetical progression there are infinitely many primes. More precisely in any progression a, a+d, a+2d,...,a+nd, where a and d have no common factor, there are infinitely many prime members of the progression.


An Apollonian packing. There is a remarkable fact that the twin prime conjecture holds for this circle system; i.e. it holds the analogy: there are infinitely many circle pairs (red) with prime curvature touching each other. (source: flysky)
An Apollonian packing. There is a remarkable fact that the twin prime conjecture holds for this circle system; i.e. it holds the analogy: there are infinitely many circle pairs (red) with prime curvature touching each other. (source: flysky)

Twin primes conjecture


There are a few remarkable properties of primes observed that are neither proved nor disproved. Twin prime conjecture says that there are infinitely many "twin" primes i.e. infinitely many pairs of primes with the difference 2. Such pairs are

3 and 5,

11 and 13,

17 and 19, etc.

Interestingly, an analogy with twin prime conjecture is proven in the case of Apollonian circle package. Starting with the three mutually tangent circles there are two other circles touching all of them, one of two is the outer circle. Furthermore, we can continue to fill the gap between any three circles, with a new circle. Let assume that the first three circles have rational radius. In such a set of circles there are infinitely many mutually tangent pairs of circles with prime curvature (curvature is reciprocally of radius).


Goldbach conjecture

A German mathematician C. Goldbach (1690-1764) in his letter to Euler conjectured that every even number can be represented as the sum of two primes (except 2, which is itself a prime). For example:

4=2+2,

6=3+3,

8=3+5,

10=5+5, etc.

First breakthrough towards the possible proof was done by a Russian mathematician L. Schnirelmann in 1931, who proved that every positive integer can be represented as the sum of not more than 300000 primes. Later a Russian mathematician A. I. Vinogradov and an Indian mathematician S. Ramanujan reduced the number from 300000 to 4. However, it doesn't hold for the all integers but for all integers greater than a certain integer N. Goldbach conjecture still remains one of the oldest and the most famous open problems in number theory and in the whole mathematics.


Primality test


A primality test is a procedure that determines whether a given number is prime or not. One simple method would be to check if a given number N is divisible by any number between 3 and square root of N. If there is at least one number in this range that divide N than N is composite, otherwise it is not.

Some known theorems as the Fermat's Little Theorem and Wilson's Theorem can serve as the test or as a base for some more sophisticated and more efficient tests. Wilson's theorem states that a number p is prime if and only if

(p-1)! ≡ -1 (mod p)

For example if p=5 than we have (5-1)!=1*2*3*4=24, 24 mod 5 ≡ 4 ≡ -1. Thus, 5 is a prime, whereas p=6 is not: (6-1)!=120, 120 mod 6 ≡ 0.

The disadvantage of the method is that it needs many multiplication in case of bigger numbers.

A search for largest known prime has always intrigued not only mathematicians but the broader community as well. There is even an award granted by a non-profit organization Electronic Frontier Foundation for the largest prime found. Currently the largest known prime is a Mersenne number with the exponent 43112609 with 12978189 digits, found in 2008.


The Sieve of Eratosthenes

Summary

  • Natural numbers can be either prime or composite.
  • Every natural number can be represented as a product of primes and this factorization is unique.
  • There are infinitely many primes in the set of all natural numbers.
  • The "density" of primes decline logarithmically; there is always a prime between numbers n and 2n.
  • Two the most famous open question regarding primes are twin prime conjecture and Goldbach conjecture.
  • Regular polygon with p sides, p being prime, is constructable by rule and compass only if and only if p is a Fermat prime.
  • Wilson's theorem can serve as a primality test but direct usage is impractical for bigger numbers.

A short quiz...

view quiz statistics
Carson Dellosa Mark Twain Prime Numbers Chart (414062)
Carson Dellosa Mark Twain Prime Numbers Chart (414062)

This chartlets is an excellent help for learning. It measure 17'' x 22'' and includes a resource guide.

 

Comments

    0 of 8192 characters used
    Post Comment

    No comments yet.

    working

    This website uses cookies

    As a user in the EEA, your approval is needed on a few things. To provide a better website experience, hubpages.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

    For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: "https://hubpages.com/privacy-policy#gdpr"

    Show Details
    Necessary
    HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
    LoginThis is necessary to sign in to the HubPages Service.
    Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
    AkismetThis is used to detect comment spam. (Privacy Policy)
    HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
    HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
    Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
    CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
    Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
    Features
    Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
    Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
    Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
    Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
    Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
    VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
    PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
    Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
    MavenThis supports the Maven widget and search functionality. (Privacy Policy)
    Marketing
    Google AdSenseThis is an ad network. (Privacy Policy)
    Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
    Index ExchangeThis is an ad network. (Privacy Policy)
    SovrnThis is an ad network. (Privacy Policy)
    Facebook AdsThis is an ad network. (Privacy Policy)
    Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
    AppNexusThis is an ad network. (Privacy Policy)
    OpenxThis is an ad network. (Privacy Policy)
    Rubicon ProjectThis is an ad network. (Privacy Policy)
    TripleLiftThis is an ad network. (Privacy Policy)
    Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
    Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
    Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
    Statistics
    Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
    ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
    Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)