Theorems Related To Mersenne Primes Mathematics Essay

Theorems Related To Mersenne Primes Mathematics EssayIntroductionIn the old many use to consider that the figure of speechs of the type 2p-1 were primordial for all rosinesss government issues which is p, but when Hudalricus Regius (1536) clearly established that 211-1 = 2047 was not blossom because it was divisible by 23 and 83 and later on Pietro Cataldi (1603) had meetly confirmed well-nigh 217-1 and 219-1 as both give primal come pool but also inaccurately declared that 2p-1 for 23, 29, 31 and 37 gave prime numbers. Then Fermat (1640) kindled Cataldi was wrong about 23 and 37 and Euler (1738) showed Cataldi was also incorrect regarding 29 but do 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 forother confirming 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 find belonging to Mersenne Primes thither 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 unfamiliarWith this concept in mind the focus of my extended turn out would beWhat are Mersenne Primes and it tie in 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 corresponding time my enthusiasm to learn something new through research on this topic.Through this paper I will explain what are Mer senne primes and certain theorems, related to other aspects and its application that are related with it.Theorems Related to Mersenne Primesp is prime only if 2p1 is prime. conclusion If p is composite hence it back tooth 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 unrivalled 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) +1Example 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 on that point 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 b oth 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). alone by meaning, (m 1)x kn = 1 which implies that 21 1 (mod m) which means that m divides 1. Thus the graduation 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 showtime 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 Wi eferich 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. instantaneously 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 TestMersenne prime are found using the pastime theoremFor 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 cipher modulo 2n-1 to conserve time. This test is thoroughgoing(a) for binary data processors since the division by 2n-1 (in binary) can only be completed using rotation and addition.Lists of Known Mersenne PrimesAfter the breakthrough of the first few Mersenne Primes it took more than two centuries with rigorous verification to obtai n 47 Mersenne primes. The following table below lists all recognized Mersenne primes-It is not well-known(a) whether any un platterovered 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.FactorizationThe 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 scope 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 prime factors allowed is 2684127 1 = 23765203727 - q, where q is a likely prime.GeneralizationThe 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 annotation of the Mersenne prime would be251 = 1111122351 = (111111111111111111111111111111)2Mersenne Primes and Perfect NumbersMany 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 numbers1) tied(p) perfect numbers- Euclid revealed that the first four perfect numbers are generated by the formula 2n1(2n1)n = 2 2(4 1) = 6n = 3 4(8 1) = 28n = 5 16(32 1) = 496n = 7 64(128 1) = 8128.Noticing that 2n1 is a prime number in each instance, Euclid proved that the formula 2n1(2n1) gives an even perfect number whenever 2p1 is prime2) 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 turn up one or otherwise resolve the quest ion 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. hardly a(prenominal) Theorems related with Perfect numbers and Mersenne primesTheorem 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 affect only show sigma(l) = 2l. Since sigma is multiplicative and sigma(p) = p+1 = 2n, we knowsigma(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 n2. Again sigma is multiplicative sosigma(2n-1m) = sigma(2n-1).sigma(m) = (2n-1).sigma(m).Since l is perfect we also know thatsigma(l) = 2l = 2nm.Together these two crit eria give2nm = (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 that2nM = 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 1Theorem Three Let n and m be primes. If q divides Mn = 2n-1, then q = +/-1 (mod 8) andq = 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 (mod8) so 2 is a quadratic residue modulo q and it follows that there is an integer n such that n2=2 (modq). This shows2p = 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 (modq) and the order of 2 modulo q divides both p and q-1, hence p divides q-1. This shows qp and it follows(2p+1) + 1 q2 p2which 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, and8128 19 10 1Proof Let s(n) be the sum of the digits of n. It is e asy 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 ProblemsDoes 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 primeIt is divisible by at least eight primes and has to have at least 75 prime factors with at least 9 distinctIt has at l east 300 decimal digits and it has a prime divisor great that 1020. be there infinite numbers of Mersenne primes?The answer is probably yes because of the harmonic sequence deviation.The New Mersenne ConjectureP. 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 thirdn = 2p+/-1 or n = 4p+/-32n-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 just 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 sequenceC0 = 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 MnLets 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 numbersMM2 = 2(4-1) -1= 23-1 =7MM3 =2(8-1)-1 =127MM5 =2(32-1)-1=2147483647,MM7 =2(128-1)-1 =170141183460469231731687303715884105727.Application of Mersenne PrimeIn computer science, unspecified p-bit integers can be utilized to express numbers up to Mp.In the numeric 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 rulesOnly one disk may be moved at a time.Each move consists of taking the upper disk from one of the rods and slew 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 i nvolved in this Tower of Hanoi then the least number of steps required to finish this game would be 31 steps minimum.ConclusionAfter canvas 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 ashes and help us to understand more sets of numbers such as Fermat prime, Wieferich prime, Wagstaff prime, Solinas prime etc.