Theorems Related To Mersenne Primes Mathematics Essay

Theorems Related To Mersenne Primes Mathematics Essay Introduction: In the past many use to consider that the numbers of the type 2p-1 were prime for all primes numbers which is p, but when Hudalricus Regius (1536) clearly established that 211-1 = 2047 was not prime because it was divisible by 23 and 83 and later on Pietro Cataldi (1603) had properly confirmed about 217-1 and 219-1 as both give prime numbers but also inaccurately declared that 2p-1 for 23, 29, 31 and 37 gave prime numbers. Then Fermat (1640) proved Cataldi was wrong about 23 and 37 and Euler (1738) showed Cataldi was also incorrect regarding 29 but made an accurate conjecture about 31. Then after this extensive history of this dilemma with no accurate result we saw the entry of Martin Mersenne who declared in the introduction of his Cogitata Physica-Mathematica (1644) that the numbers 2p-1 were prime for:- p= 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 and for  other positive integers where p So simply the definition is when 2p-1 forms a prime number it is recognized to be a Mersenne prime. Many years later with new numbers being discovered belonging to Mersenne Primes there are still many fundamental questions about Mersenne primes which remain unresolved. It is still not identified whether Mersenne primes is infinite or finite. There are still many aspects, functions it performs and applications of Mersenne primes that are still unfamiliar With this concept in mind the focus of my extended essay would be: What are Mersenne Primes and it related functions? The reason I choose this topic was because while researching on my extended essay topics and I came across this part which from the beginning intrigued me and it gave me the opportunity to fill this gap as very little was taught about these aspects in our school and at the same time my enthusiasm to learn something new through research on this topic. Through this paper I will explain what are Mersenne primes and certain theorems, related to other aspects and its application that are related with it. Theorems Related to Mersenne Primes: p is prime only if 2p  Ãƒ ¢Ã‹â€ Ã¢â‚¬â„¢Ã‚  1 is prime. Proof: If p is composite then it can be written as p=x*y with x, y > 1. 2xy-1= (2x-1)*(1+2x+22x+23x+à ¢Ã¢â€š ¬Ã‚ ¦Ãƒ ¢Ã¢â€š ¬Ã‚ ¦Ãƒ ¢Ã¢â€š ¬Ã‚ ¦Ãƒ ¢Ã¢â€š ¬Ã‚ ¦..+2(b-1)a) Thus we have got 2xy à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 as a product of integers > 1. If n is an odd prime, then any prime m that divides 2n à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 must be 1 plus a multiple of 2n. This holds even when 2n à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 is prime. Examples: Example I: 25 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 = 31 is prime, and 31 is multiple of (2ÃÆ'-5) +1 Example II: 211 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 = 23ÃÆ'-89, where 23 = 1 + 2ÃÆ'-11, and 89 = 1 + 8ÃÆ'-11. Proof: If m divides 2n à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 then 2n à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod m). By Fermats Theorem we know that 2(m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod m). Assume n and m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 are comparatively prime which is similar to Fermats Theorem that states that (m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1)(n à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod n). Hence there is a number x à ¢Ã¢â‚¬ °Ã‚ ¡ (m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1)(n à ¢Ã‹â€ Ã¢â‚¬â„¢ 2) for which (m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) ·x à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod n), and thus a number k for which (m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) ·x à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 = kn. Since 2(m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod m), raising both sides of the congruence to the power x gives 2(m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1)x à ¢Ã¢â‚¬ °Ã‚ ¡ 1, and since 2n à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod m), raising both sides of the congruence to the power k gives 2kn à ¢Ã¢â‚¬ °Ã‚ ¡ 1. Thus 2(m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1)x/2kn = 2(m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1)x à ¢Ã‹â€ Ã¢â‚¬â„¢ kn à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod m). But by meaning, ( m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1)x à ¢Ã‹â€ Ã¢â‚¬â„¢ kn = 1 which implies that 21 à ¢Ã¢â‚¬ °Ã‚ ¡ 1 (mod m) which means that m divides 1. Thus the first conjecture that n and m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 are relatively prime is unsustainable. Since n is prime m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 have to be a multiple of n. Note: This information provides a confirmation of the infinitude of primes different from Euclids Theorem which states that if there were finitely many primes, with n being the largest, we have a contradiction because every prime dividing 2n à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 must be larger than n. If n is an odd prime, then any prime m that divides 2n à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 must be congruent to +/-1 (mod 8). Proof: 2n + 1 = 2(mod m), so 2(n + 1) / 2 is a square root of 2 modulo m. By quadratic reciprocity, any prime modulo which 2 has a square root is congruent to +/-1 (mod 8). A Mersenne prime cannot be a Wieferich prime. Proof: We show if p = 2m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 is a Mersenne prime, then the congruence does not satisfy. By Fermats Little theorem, m | p à ¢Ã‹â€ Ã¢â‚¬â„¢ 1. Now write, p à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 = mÃŽÂ ». If the given congruence satisfies, then p2 | 2mÃŽÂ » à ¢Ã‹â€ Ã¢â‚¬â„¢ 1, therefore Hence 2m à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 | ÃŽÂ », and therefore . This leads to , which is impossible since . The Lucas-Lehmer Test Mersenne prime are found using the following theorem: For n an odd prime, the Mersenne number 2n-1 is a prime if and only if 2n -1 divides S(p-1) where S(p+1) = S(p)2-2, and S(1) = 4. The assumption for this test was initiated by Lucas (1870) and then made into this straightforward experiment by Lehmer (1930). The progression S(n) is calculated modulo 2n-1 to conserve time.   This test is perfect for binary computers since the division by 2n-1 (in binary) can only be completed using rotation and addition. Lists of Known Mersenne Primes: After the discovery of the first few Mersenne Primes it took more than two centuries with rigorous verification to obtain 47 Mersenne primes. The following table below lists all recognized Mersenne primes:- It is not well-known whether any undiscovered Mersenne primes present between the 39th and the 47th from the above table; the position is consequently temporary as these numbers werent always discovered in their increasing order. The following graph shows the number of digits of the largest known Mersenne primes year wise. Note: The vertical scale is logarithmic. Factorization The factorization of a prime number is by meaning itself the prime number itself. Now if talk about composite numbers. Mersenne numbers are excellent investigation cases for the particular number field sieve algorithm, so frequently that the largest figure they have factorized with this has been a Mersenne number. 21039 1 (2007) is the record-holder after estimating took with the help of a couple of hundred computers, mostly at NTT in Japan and at EPFL in Switzerland and yet the time period for calculation was about a year. The special number field sieve can factorize figures with more than one large factor. If a number has one huge factor then other algorithms can factorize larger figures by initially finding the answer of small factors and after that making a primality test on the cofactor. In 2008 the largest Mersenne number with confirmed prime factors is 217029 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 = 418879343 ÃÆ'- p, where p was prime which was confirmed with ECPP. The largest with possible pr ime factors allowed is 2684127 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 = 23765203727 ÃÆ'- q, where q is a likely prime. Generalization: The binary depiction of 2p à ¢Ã‹â€ Ã¢â‚¬â„¢ 1 is the digit 1 repeated p times. A Mersenne prime is the base 2 repunit primes. The base 2 depiction of a Mersenne number demonstrates the factorization example for composite exponent. Examples in binary notation of the Mersenne prime would be: 25à ¢Ã‹â€ Ã¢â‚¬â„¢1 = 111112 235à ¢Ã‹â€ Ã¢â‚¬â„¢1 = (111111111111111111111111111111)2 Mersenne Primes and Perfect Numbers Many were anxious with the relationship of a two sets of different numbers as two how they can be interconnected. One such connection that many people are concerned still today is Mersenne primes and Perfect Numbers. When a positive integer that is the sum of its proper positive divisors, that is, the sum of the positive divisors excluding the number itself then is it said to be known as Perfect Numbers. Equivalently, a perfect number is a number that is half the sum of all of its positive divisors. There are said to be two types of perfect numbers: 1) Even perfect numbers- Euclid revealed that the first four perfect numbers are generated by the formula 2nà ¢Ã‹â€ Ã¢â‚¬â„¢1(2n  Ãƒ ¢Ã‹â€ Ã¢â‚¬â„¢Ã‚  1): n = 2:    2(4 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) = 6 n = 3:    4(8 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) = 28 n = 5:    16(32 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) = 496 n = 7:    64(128 à ¢Ã‹â€ Ã¢â‚¬â„¢ 1) = 8128. Noticing that 2n  Ãƒ ¢Ã‹â€ Ã¢â‚¬â„¢Ã‚  1 is a prime number in each instance, Euclid proved that the formula 2nà ¢Ã‹â€ Ã¢â‚¬â„¢1(2n  Ãƒ ¢Ã‹â€ Ã¢â‚¬â„¢Ã‚  1) gives an even perfect number whenever 2p  Ãƒ ¢Ã‹â€ Ã¢â‚¬â„¢Ã‚  1 is prime 2) Odd perfect numbers- It is unidentified if there might be any odd perfect numbers. Various results have been obtained, but none that has helped to locate one or otherwise resolve the question of their existence. An example would be the first perfect number that is 6. The reason for this is so since 1, 2, and 3 are its proper positive divisors, and 1  +  2  +  3  =  6. Equivalently, the number 6 is equal to half the sum of all its positive divisors: (1  +  2  +  3  +  6)  /  2  =  6. Few Theorems related with Perfect numbers and Mersenne primes: Theorem One: z is an even perfect number if and only if it has the form 2n-1(2n-1) and 2n-1 is a prime. Suppose first that   p = 2n-1 is a prime number, and set l = 2n-1(2n-1).   To show l is perfect we need only show sigma(l) = 2l.   Since sigma is multiplicative and sigma(p) = p+1 = 2n, we know sigma(n) = sigma(2n-1).sigma(p) =  (2n-1)2n = 2l. This shows that l is a perfect number. On the other hand, suppose l is any even perfect number and write l as 2n-1m where m is an odd integer and n>2.   Again sigma is multiplicative so sigma(2n-1m) = sigma(2n-1).sigma(m) = (2n-1).sigma(m). Since l is perfect we also know that sigma(l) = 2l = 2nm. Together these two criteria give 2nm = (2n-1).sigma(m), so 2n-1 divides 2nm hence 2n-1 divides m, say m = (2n-1)M.   Now substitute this back into the equation above and divide by 2n-1 to get 2nM = sigma(m).   Since m and M are both divisors of m we know that 2nM = sigma(m) > m + M = 2nM, so sigma(m) = m + M.   This means that m is prime and its only two divisors are itself (m) and one (M).   Thus m = 2n-1 is a prime and we have prove that the number l has the prescribed form. Theorem Two: n will also be a prime if 2n-1 is a prime. Proof: Let r and s be positive integers, then the polynomial xrs-1 is xs-1 times xs(r-1) + xs(r-2) + + xs + 1.   So if n is composite (say r.s with 1 Theorem Three:   Let n and m be primes. If q divides Mn = 2n-1, then q = +/-1 (mod 8)  Ã‚  Ã‚  Ã‚   and  q = 2kn + 1 for some integer k. Proof: If p divides Mq, then 2q  =  1 (mod p) and the order of 2 (mod p) divides the prime q, so it must be q.   By Fermats Little Theorem the order of 2 also divides p-1, so p-1  =  2kq.   This gives 2(p-1)/2 = 2qk = 1 (mod p) so 2 is a quadratic residue mod p and it follows p = +/-1 (mod 8), which completes the proof. Theorem Four: If p = 3 (mod 4) be prime and then 2p+1 is also prime only if 2p+1 divides 2p-1. Proof: Suppose q = 2p+1 is prime. q  =  7 (mod  8) so 2 is a quadratic residue modulo q and it follows that there is an integer n such that n2  =  2 (mod  q). This shows 2p = 2(q-1)/2 = nq-1 = 1 (mod q), showing q divides Mp.       Conversely, let 2p+1 be a factor of Mp. Suppose, for proof by contradiction, that 2p+1 is composite and let q be its least prime factor. Then 2p  =  1 (mod  q) and the order of 2 modulo q divides both p and q-1, hence p divides q-1. This shows q  >  p and it follows (2p+1) + 1 > q2 > p2 which is a contradiction since p > 2. Theorem Five: When we add the digits of any even perfect number with the exception of 6 and then sum the digits of the resulting number and keep doing it again until we get a single digit which will be one. Examples. 28  ¬10  ¬ 1, 496  ¬ 19  ¬ 10  ¬ 1, and 8128  ¬ 19  ¬10  ¬ 1 Proof: Let s(n) be the sum of the digits of n. It is easy to see that s(n) = n (mod 9). So to prove the theorem, we need only show that perfect numbers are congruent to one modulo nine. If n is a perfect number, then n has the form 2p-1(2p-1) where p is prime which see in the above theorem one. So p is either 2, 3, or is congruent to 1 or 5 modulo 6. Note that we have excluded the case p=2 (n=6). Finally, modulo nine, the powers of 2 repeat with period 6 (that is, 26 = 1 (mod 9)), so modulo nine n is congruent to one of the three numbers 21-1(21-1), 23-1(23-1), or 25-1(25-1), which are all 1 (mod 9). Conjectures and Unsolved Problems: Does an odd perfect number exist?   We have so far known that even perfect numbers are 2n-1(2n-1)from the Theorem One above, but what about odd perfect numbers?   If there is an odd perfect number, then it has to follow certain conditions:- To be a perfect square times an odd power of a single prime; It is divisible by at least eight primes and has to have at least 75 prime factors with at least 9 distinct It has at least 300 decimal digits and it has a prime divisor greater that 1020. Are there infinite numbers of Mersenne primes?   The answer is probably yes because of the harmonic sequence deviation. The New Mersenne Conjecture: P. T. Bateman, J. L. Selfridge and Wagstaff, Jr., S. S., have conjectured the following:- Let n be any odd natural number. If two of the following statements hold, subsequently so does the third: n = 2p+/-1  Ã‚   or  Ã‚   n = 4p+/-3 2n-1 is a prime (2n+1)/3 is a prime. Are all Mersenne number 2n-1 square free? This is kind of like an open question to which the answer is still not known and hence it cannot be called a conjecture. It is simple to illustrate that if the square of a prime n divides a Mersenne, then p is a Wieferich prime which are uncommon!   Only two are acknowledged lower than 4,000,000,000,000 and none of these squared divide a Mersenne.    If C0 = 2, then let C1 = 2C0-1, C2 = 2C1-1, C3 = 2C2-1à ¢Ã¢â€š ¬Ã‚ ¦Ãƒ ¢Ã¢â€š ¬Ã‚ ¦ then are all of these prime numbers?   Dickson Catalan (1876) responded to Lucas stating 2127-1 (which is C4) being a prime with this sequence: C0 = 2 (which is a prime) C1 = 3 (which is a prime) C2 = 7 (which is a prime) C3 = 127 (which is a prime) C4 = 170141183460469231731687303715884105727 (which is a prime) C5 > 1051217599719369681875006054625051616349 (is C5 a prime or not?) It looks as if it will not be very likely that C5 or further larger terms would be prime number.   If there is a single composite term in this series, then by theorem one each and every one of the following terms would be composite.   Are there more double-Mersenne primes? Another general misunderstanding was that if n=Mp is prime, then so is Mn; Lets assume this number Mn to be MMp which would be a double-Mersenne.  As we apply this to the first four such numbers we get prime numbers: MM2 = 2(4  -1) -1= 23-1  Ã‚   =  7 MM3 =  2(8-1)-1  Ã‚   =  127 MM5 =  2(32-1)-1  =  2147483647, MM7 =  2(128-1)-1 =  170141183460469231731687303715884105727. Application of Mersenne Prime: In computer science, unspecified p-bit integers can be utilized to express numbers up to Mp. In the mathematical problem Tower of Hanoi is where the Mersenne primes are used. It is a mathematical puzzle consisting of three rods, and a number of disks of different sizes, which can slide onto any rod. The puzzle begins with the disks in ascending order of size on the first rod, the largest at the bottom to the smallest at the top. A diagram given below illustrates the Tower of Hanoi. The objective of the puzzle is to move the entire stack to another rod, obeying the following rules: Only one disk may be moved at a time. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod. No disk may be placed on top of a smaller disk. Now to solve this game with a p-disc tower needs the minimum of Mp no of steps, where p is the no of disc used in the Tower of Hanoi and if we use the formula of Mersenne then we get the required result. An example of this would be if there were 5 discs involved in this Tower of Hanoi then the least number of steps required to finish this game would be 31 steps minimum. Conclusion After investigating the entire aspects, functions, and few applications of Mersenne Primes I believe that there is still many unsolved theories when it comes to Mersenne primes. These primes are also useful to investigates much further and deeper into the number system and help us to understand more sets of numbers such as Fermat prime, Wieferich prime, Wagstaff prime, Solinas prime etc.