Tag Archives: Mersenne

Numbers Courtesy of Fermat and Mersenne

A portrait of Pierre de Fermat, lawyer and amateur mathematician. Image: Author and painter unknown, via Wikimedia Commons.

It is not often a person contributes to a field they do not even work in the way Pierre de Fermat has contributed to the field of mathematics. Born to a wealthy leather merchant, Fermat received a bachelor’s in civil law from the University of Orléans and went on to become a lawyer, while at the same time engraving his name into math history books, doing said math just for recreation. His importance in mathematics lead to many theorems named after him, as well as numbers. These numbers are known as Fermat numbers, which are positive integers, that take of the form Fn = 2(2n) + 1, when n is nonnegative and an integer. For example for F1, F1= 2(2)+1= 5. The first five Fermat numbers are 3, 5, 17, 257, and 65537, and these numbers continue to grow to incredibly large magnitudes. Fermat believed this form created an infinite number of prime numbers, which are known as Fermat primes.

Fermat numbers are occasionally written as 2n+1, but since when n is greater than zero and Fn prime, n must be a power of two, the form Fn = 2(2n) + 1 is the common form for Fermat numbers. One of the main problems with Fermat claiming all these numbers are prime is the fact that they soon become too large to calculate for even today’s computers, let alone a man with his pen and paper in the 17th century. Unfortunately for Fermat, by the time the 18th century rolled around, he was dead. In 1732, mathematician Leonhard Euler found that F5, which is 4,294,967,297, is actually divisible by 641, most likely figuring this out from having a large amount of time on his hands. While this showed that some Fermat numbers are not actually prime, excluding when n=0 in the form 2n+1, it does not discount the fact that the Fermat number equation could still make an infinite number of primes, since there are infinite amount of Fermat numbers. However as of now, the only Fermat primes that are known are F0 through F4.

Now initially I found the idea of an equation, the equation here being Fn = 2(2n) + 1, that finds only certain prime numbers, most of which are way too large to even be calculated even 400 years after the equation for them was created, the equivalent to a student doing extra credit when he has a 98% in his class. What I’m trying to say is, I found Fermat numbers pointless and to be the 17th century mathematician’s version of a braggadocio. However, I know nothing and Gauss managed to find a relationship between “Euclidean construction of regular polygons and Fermat primes,” where he showed a regular 17-gon could be constructed. It was also found a regular n-gon can be created if n is the product of any number of Fermat primes and the number 2. These regular n-gons take the property of being able to be constructed with a compass and straightedge. Who would have thought one of the greatest mathematicians to ever live could leave me feeling so inadequate, at least mathematically.

Similar to Fermat numbers are what are known Mersenne numbers, created by 17th century French mathematician and music theorist Marin Mersenne. Yet again a person being a jack of all trades, except instead of being a master of none they were a master of a few or at least of one. Mersenne numbers take of the form Mn = 2n -1, and Mersenne primes are numbers that take that form which are prime. Mersenne believed that for n<=257, Mn was prime for n= 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257, and the rest are composite. While this belief turned out to incorrect, he still got the name for the primes. Just like Fermat primes, it is unknown whether there are an infinite number of Mersenne primes, but as of now 48 Mersenne primes are known, the largest being 257885161-1, which again makes me wonder how much time do some of these mathematicians have on their hands.

Mersenne numbers were originally studied because of their connection to perfect numbers, which are positive integers that are equal to the sum of their divisors. Euclid proved that if the number 2n-1 is prime, then 2n-1(2n-1) is a perfect number, which many years later led to Euler discovering that all even perfect numbers come in this form. Another interesting fact is that the ten largest known prime numbers are Mersenne numbers. I personally find number theory incredibly interesting, partly because I like numbers and partly because how mathematicians are able to come with these theorems and proofs baffle me. I ultimately wonder if they had any true goals when thinking about these primes, or if it was just for the pure fun and interest in it.

References:

http://en.wikipedia.org/wiki/Fermat_number

http://interact.sagemath.org/edu/2010/414/projects/tsang.pdf

http://mathworld.wolfram.com/FermatNumber.html

http://mathworld.wolfram.com/FermatPrime.html

https://primes.utm.edu/glossary/page.php?sort=FermatNumber

http://en.wikipedia.org/wiki/Mersenne_prime

http://en.wikipedia.org/wiki/Marin_Mersenne

http://en.wikipedia.org/wiki/Pierre_de_Fermat

http://mathworld.wolfram.com/MersennePrime.html

Advertisements

Fermat prime and Mersenne prime

Fermat prime

https://i1.wp.com/upload.wikimedia.org/wikipedia/commons/f/f3/Pierre_de_Fermat.jpg

In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form. Fn=22n+1, where n is a nonnegative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617. And he is the first to investigate numbers of the form 22n.

There is the Pépin test which gives sufficient and necessary condition for the primality of the Fermat prime and this can only be implemented by use of modern computers. Pépin’s test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth’s test. The test is named for a French mathematician, Théophile Pépin.Let Fn be a Fermat number. Fn is prime if and only if 3(Fn-1)/2 = -1 (mod Fn).Here 3 can be replaced by any positive integer k for which the Jacobi symbol (k|Fn) is -1. These include k=3, 5, and 10.If Fn is prime, this primality can be shown by Pepin’s test, but when Fn is composite, Pepin’s test does not tell us what the factors will be (only that it is composite). For example, Selfridge and Hurwitz showed that F14 was composite in 1963, but we still do not know any of its divisors. (Chris K. Caldwell)

Mersenne numbers, which take the form of 2n-1, were named after Marin Mersenne, a French monk from the early 17 century, who corresponded with Fermat. We are particularly interested in the case when Mersenne number are prime. It is not doubt that the first 17 primes of the form 2n-1 match the following n values: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281 (Zegarelli 287).

The first 12 Mersenne primes were known since 1914 and the 12th, 2127-1, was established by Anatole Lucas in 1876. It was one of the largest-known prime number for over 75 years. The next 5 Mersenne primes (p=13 to 17)were discovered in 1952. It was in 1952 when the testing program for Mersenne numbers was began. This led to the establishment of three other primes. More testing has been carried out using modern day computers and the smallest Mersenne number that is untested is 22309-1 (~2013), and this has not been a case of great interest. There is a conjecture that 2n-1 is always prime when n is a Mersenne number. And the more interesting case is the 28191-1 because the 8191 also is the Mersenne number. (Křížek, Florian and Lawrence 214).

Works Cited

Chris K. Caldwell (2014). Pepin’s test . [ONLINE] Available at: http://primes.utm.edu/glossary/page.php?sort=PepinsTest.

Crandall, Richard E, and Carl Pomerance. Prime Numbers: A Computational Perspective. New York: Springer, 2005. Internet resource.

Zegarelli, Mark. Basic Math & Pre-Algebra Workbook for Dummies. Hoboken, N.J: Wiley, 2008. Internet resource.

Křížek, Michal, Florian Luca, and Lawrence Somer. 17 Lectures on Fermat Numbers:    From Number Theory to Geometry. New York, NY [u.a.: Springer, 2001. Print.

GIMPS: The Great Internet Mersenne Prime Search

The GIMPS Logo. Public domain, via Wikimedia Commons.

The GIMPS Logo. Public domain, via Wikimedia Commons.

Approximately two years ago, I decided to build my first desktop. From browsing various forums on the internet, I learned that many PC builders would run their hardware at higher speeds for more performance than the manufacturers specify when selling components. However, when doing this, one must run a program that uses 100% of a processor’s computing power to ensure the stability of the PC so that it will not shut down or encounter a Blue Screen of Death while playing video games or doing other important work. It was in this situation that I first encountered a program known as Prime95.

Prime95, in addition to being used to test overclocked processors, is used by the members of The Great Internet Mersenne Prime Search, or GIMPS, to search for large Mersenne primes.

Mersenne numbers have the form 2n-1, where n is a positive integer. Mersenne primes are those Mersenne numbers that are prime; the first four are 22-1, 23-1, 25-1, and 27-1. These special primes are named for the French theologian and mathematician Marin Mersenne. Born in 1588 in Oizé, France, Mersenne was always interested in studying mathematics, and published a paper in 1644 that included a statement about numbers of the form 2n-1. He claimed that for n less than 257, the values n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 made the number prime. However, Mersenne admitted to not having tested all of the positive integers less than 257. With the use of many mathematical discoveries, it was shown that n = 67 and 257 did not make 2n-1 prime, and that n = 61, 89, and 107 also made it prime, making a total of five errors in Mersenne’s list for n < 257. This led to many individuals becoming interested in finding large Mersenne primes.

GIMPS was founded in 1996 by George Woltman, who graduated from MIT with a Master’s degree in Computer Science. GIMPS and Prime95 use a method to perform calculations known as “distributed computing.” Distributed computing is essentially an alternative to using supercomputers to perform difficult calculations – instead of using a small number of supercomputers to solve problems, people around the world “donate” time when their computer is not being used to work on small chunks of these large calculations.

Since 1996, Prime95 has been used to discover fourteen Mersenne Primes. The first of these was in November of the year GIMPS was founded, 21,398,269-1. On January 25th, 2013, the 48th known Mersenne prime was discovered, 257,885,161-1. On February 24th of this year (2014), it was verified that the 43rd known Mersenne prime, 230,402,457-1, was, in fact, the 43rd Mersenne prime, meaning that we know of every Mersenne prime smaller than this 43rd one, and there are exactly 42 Mersenne primes that are smaller.

How does GIMPS discover these large primes? Prime95 uses a method known as the Lucas-Lehmer Primality test, a recursive relation, to determine whether a Mersenne number (Mn = 2n – 1) is prime or not. If it is prime, it is therefore a Meresnne prime (Mp = 2p – 1) where n=p. The Lucas-Lehmer test uses the following relation:

sn ≡ (sn-1)2-2 mod Mn.

where s0 ≡ 4. The Lucas-Lehmer residue, sn-2 mod Mn, determines whether a Mersenne number is prime; a Mersenne number is prime if and only if the Lucas-Lehmer residue is congruent to 0 mod Mn.

If, for example, we want to determine whether the Mersenne number 211-1 is a prime, then p = 11 and M11 = 2047. We therefore need to find the Lucas-Lehmer residue, s9, to determine whether M11 is a Mersenne prime.

The first index is always congruent to 0, so we start with:
s0 ≡ 4 mod M11.

We then calculate the second residue using the formula.
s1 ≡ sn-12-2 mod M11 ≡ s02-2 mod M11.

Since s0 ≡ 4 mod M11:
s02 – 2 mod M11 ≡ 16-2 mod M11.

Which is then congruent to:
16-2 mod M11 ≡ 14 mod M11.

Therefore, our second residue s1 is:
s1 ≡ 14 mod M11.

We then use this second residue to calculate our third residue s2.
s2 ≡ s22-2 mod M11 ≡ 194 mod M11.

We then continue to use this formula to calculate the next six residues:

s3 ≡ 788 mod M11.
s4 ≡ 701 mod M11.
s5 ≡ 119 mod M11.
s6 ≡ 1877 mod M11.
s7 ≡ 240 mod M11.
s8 ≡ 282 mod M11.

We can now finally calculate s9, the Lucas-Lehmer residue. This tenth residue turns out to be:
s9 ≡ 1736 mod M11.

Because the Lucas-Lehmer residue must be congruent to 0 mod M11 for M11 to be a Mersenne prime, the Mersenne number M11 = 2047 is not a Mersenne prime, which matches GIMPS’ own list of the 48 known Mersenne primes.

While the search for these large primes may not seem particularly relevant at first, there is one important application: RSA encryption. In RSA encryption, a user can post a “public key” which is the product of two extremely large primes. A message can be encrypted to that user with the public key, but for the message to be decrypted, the public key has to be factored into the exact two primes used to get it. This is an extremely time consuming and difficult feat to accomplish – unless you happen to know what those two primes are. This makes large primes extremely effective in encryption, the most prevalent use of large primes in our world today. Click here for more information on RSA encryption.

The Great Internet Mersenne Prime Search has generated many primes with their distributed computing program Prime95, which primarily uses the Lucas-Lehmer primality test to test large Mersenne numbers. If you want to join in the search for the next Mersenne prime, you can sign up at http://www.mersenne.org and download Prime95.

But don’t try computing these by hand with a calculator. M48 is 17.4 million digits long.

Sources:

http://mathworld.wolfram.com/Lucas-LehmerTest.html

http://www.mersenne.org/

http://www.bacchae.co.uk/docs/dist.html

http://primes.utm.edu/bios/page.php?lastname=Woltman

http://primes.utm.edu/glossary/page.php?sort=MersennesConjecture

http://www-history.mcs.st-andrews.ac.uk/Biographies/Mersenne.html

http://arstechnica.com/science/2013/02/ask-ars-why-spend-time-and-money-finding-new-prime-numbers/