[PDF] [PDF] MERSENNE PRIMES If n ≥ 2 and an − 1 is prime, we call an − 1 a

[PDF] file - -ORCA

1 Proof We prove the result for the case when n is multiplicatively e-perfect, the other prime number p, 2p-multiplicatively e-superperfect numbers which have the Te((p1 · p2)2p)=(p1 · p2)σ(2p)·d(2p) = (p1 · p2)3·(p+1)·4 = (p1 · p2)12·(p+1)

[PDF] On Perfect Numbers - Semantic Scholar

17 mai 2016 · Proof Let p be an integer such that 2p − 1 is a prime number We aim to show that all perfect numbers of the form 2p-1(2p − 1)? The next significant step in the answering of σ(6) = 1 + 2 + 3 + 6 = 12 σ(18) = 1 + 2 + 3 + 6 + 

[PDF] Digital Roots of Perfect Numbers - AWS

Roots that a perfect number other than 6 has digital root 1 We now provide a proof of this claim 12 is abundant, because 1 + 2 + 3 + 4 + 6 + 12 > 24 For, if p is a prime number, then 12p is necessarily an abundant number, because

[PDF] Perfect numbers - Irish Mathematical Society

Theorem 1 1f the number (2"-1) 18 prime, then the number 2n-1/2"-1) is Proof Let p = (2"-1) and suppose p 18 prime Then the 1 e (2"-1)(1+p) This equals 12"-1)2", One could say that m is perfect if the sum of all the factors of in, which is  

[PDF] MERSENNE PRIMES If n ≥ 2 and an − 1 is prime, we call an − 1 a

p − 1 is prime, and discuss an application to even perfect numbers The proof requires us to study the field Z/qZ[ √

[PDF] SOLUTIONS TO PROBLEM SET 1 Section 13 Exercise 4 We see

previous paragraph This shows that a = 1,2 have an unique balanced ternary expansion that p > n In particular, given a positive integer n we can always find a prime larger than n; by growing n Since (12,18) = 6 50 there are no solutions

[PDF] Some Results on Generalized Multiplicative Perfect Numbers

e-superperfect numbers and prove some results on them We also p = 1 It is impossible since p is a prime number If at least an αi is equal to 1, say α1 = 1, then from (2 2), we 2 be the prime factorisation of an integer n > 1 where p1 and p2 are r = 1: (3 3) becomes 2 · (α1 + 1) = 12 · (2p − 1); it gives α1 = 12p − 5

[PDF] There are No Multiply-Perfect Fibonacci Numbers - Mathematics

We show that no Fibonacci number (larger than 1) divides the sum of its divi- sors 2 Notation For a positive integer a and a prime p we write p a/ for the exact [ 3] and [21] we get that n0 2 ¹1; 2; 3; 4; 6; 12º, so n 2 ¹3; 6; 9; 12; 18; 36º, and the

SOLUTIONS

greater than 10 contains a prime number greater than or equal to 11, which is impossible And from 1,2, ,10 we cannot select nine consecutive numbers with the required We need the fact that every integer p ≥ 2 can be represented as a2 + b2 Methods of Proof 335 1 = 12, 2 = −12 − 22 − 32 + 42, 3 = −12 + 22,

[PDF] show that 4p^2 20p+9 0

[PDF] show that a sequence xn of real numbers has no convergent subsequence if and only if xn → ∞ asn → ∞

[PDF] show that etm turing reduces to atm.

[PDF] show that every infinite turing recognizable language has an infinite decidable subset.

[PDF] show that every tree with exactly two vertices of degree one is a path

[PDF] show that f is continuous on (−∞ ∞)

[PDF] show that for each n 1 the language bn is regular

[PDF] show that if a and b are integers with a ≡ b mod n then f(a ≡ f(b mod n))

[PDF] show that if an and bn are convergent series of nonnegative numbers then √ anbn converges

[PDF] show that if f is integrable on [a

[PDF] show that if lim sn

[PDF] show that p ↔ q and p ↔ q are logically equivalent slader

[PDF] show that p ↔ q and p ∧ q ∨ p ∧ q are logically equivalent

[PDF] show that p(4 2) is equidistant

[PDF] show that p2 will leave a remainder 1

MERSENNE PRIMES

SARAH MEIKLEJOHN AND STEVEN J. MILLER

ABSTRACT.

A Mersenne prime is a prime that can be written as2p¡1for some prime p. The first few Mersenne primes are3,7and31(corresponding respectively top= 2,

3and5). We give some standard conditions onpwhich ensure that2p¡1is prime,

and discuss an application to even perfect numbers. The proof requires us to study the fieldZ=qZ[p

3], whereq6= 3is a prime.

1.INTRODUCTION

Ifn¸2andan¡1is prime, we callan¡1a Mersenne prime. For which integersa canan¡1be prime? We taken¸2as ifn= 1thenais just one more than a prime.

We know, using the geometric series, that

a n¡1 = (a¡1)(an¡1+an¡2+¢¢¢+a+ 1):(1) So,a¡1jan¡1and thereforean¡1will be composite unlessa¡1 = 1, or equivalently unlessa= 2. Thus it suffices to investigate numbers of the form2n¡1. Further, we need only examine the case ofnprime. For assumenis composite, say n=mk. Then2n= 2mk= (2m)k, and 2 n¡1 = (2m)k¡1 = (2m¡1)((2m)k¡1+ (2m)k¡2+¢¢¢+ (2m)2+ 2m+ 1):(2) So ifn=mk,2n¡1always has a factor2m¡1, and therefore is prime only when 2 m¡1 = 1. This immediately reduces to2m= 2, or simplym= 1. Thus, ifnis composite,2n¡1is composite. Now we know we are only interested in numbers of the form2p¡1; if this number is prime then we call it a Mersenne prime. As it turns out, not every number of the form 2 p¡1is prime. For example,211¡1 = 2047, which is23¢89.

2.STATEMENT OF THELUCAS-LEHMERTEST

How do we determine whichpyieldMp= 2p¡1prime? An answer is the Lucas- Lehmer test, which states thatMpis prime if and only ifMpjsp¡2, where we recur- sively define s i=(

4ifi= 0;

s

2i¡1¡2ifi6= 0:(3)

We prove one direction of this statement, namely that ifMpjsp¡2, thenMpis prime.

We start by definingu= 2¡p

3andv= 2 +p

3. Some immediate properties are

u+v= 4 =s0; uv= 1, implying that(uv)x=uxvx= 1(souvto any power equals one).

Date: December 4, 2005.

1

2 SARAH MEIKLEJOHN AND STEVEN J. MILLER

We will show thatsn=ut(n)+vt(n), where we have definedt(s) = 2s. We shall see later that this is a useful way to writesn. Two properties oft(s)that we need are t(0) = 1; t(s+ 1) = 2s+1= 2t(s).

We prove by induction thatsn=ut(n)+vt(n).

Base Case:Clearly the base case is true, as we have already seen thats0=u1+v1= 4. Inductive Case:Assumingsn=ut(n)+vt(n), we must showsn+1=ut(n+1)+vt(n+1)= s

2n¡2. To do this, we look at

s n+1=s2n¡2 = (ut(n)+vt(n))2¡2 =u2t(n)+v2t(n)+ 2ut(n)vt(n)¡2: (4) But we already know thatut(n)vt(n)= (uv)t(n)= 1and2t(n) =t(n+ 1), so we have s n+1=ut(n+1)+vt(n+1)+ 2¡2 =ut(n+1)+vt(n+1); (5) which shows thatsn+1=ut(n+1)+vt(n+1).

3.PROOF OF THELUCAS-LEHMERTEST

We prove one direction of the Lucas-Lehmer test. Specifically, we prove by contra- diction that ifMpjsp¡2thenMpis prime.

3.1.Preliminaries.

We assume thatsp¡2is divisible byMp, but thatMpisnotprime. By direct calculation we may assume thatp >5. There is therefore an integerR >1 such that s p¡2=ut(p¡2)+vt(p¡2)=RMp:(6)

If we multiply both sides byut(p¡2), we obtain

u t(p¡2)¢(ut(p¡2)+vt(p¡2)) =ut(p¡1)+ 1 =RMp¢ut(p¡2):(7)

Subtracting one from each side gives

u t(p¡1)=RMp¢ut(p¡2)¡1:(8) We square both sides. As(ut(p¡1))2=ut(p), we obtain that u t(p)= (RMp¢ut(p¡2)¡1)2:(9)

Noteut(p)is not necessarily an integer.

Let us choose some prime factorq >1ofMpsuch thatq·p M p, or equivalently so thatq2·Mp. Does such aqexist? There is no problem with assumingq >1, but what aboutq·p M p? IfMp=bcthen eitherborcis at mostp M p, for if both were larger then the product would exceedMp. Note we are not claiming thatq

5(as the other cases can be handled by direct

MERSENNE PRIMES 3

computation). Thus we may writepas4n+a, wherenis an integer anda2 f1;3g. Thus M p= 2p¡1 = 2

4n+a¡1

= 2

4n¢2a¡1

= (2

4)n¢2a¡1

´2a¡1 mod 3;

(10) since24= 16´1 mod 3. Ifa= 1then24n+a¡1´1 mod 3, while ifa= 3then 2

4n+a¡1´1 mod 3. Thus3does not divideMp, and we may assume thatq6= 3

below. The proof is completed by analyzing the order ofut(p)in the fieldZ=qZ[p

3], where

qis a prime dividingMp. There are two different cases, depending on whether or not3 is a square moduloq. Note that if3is a square moduloq, then this field is actually just Z=qZ.

3.2.3is not a square moduloq.

We finish the proof in the case that3is not a square moduloq. This means thatt2¡3does not have a root inZ=qZ, or equivalently that t

2¡3is irreducible inZ=qZ.

Proof.

Consider the ringZ=qZ[p

3] =

©a+bp

3 :a;b2Z=qZª; note there areq2

elements, andq2¡1non-zero elements. Asq6= 3is prime,Z=qZis a field. Further,

Z=qZ[p

3]is a field asp

3is invertible inZ=qZ[p

3]; the inverse isbp

3, whereb2

Z=qZis such that3b´1 modq. More generally, letp(t) =t2¡32Z=qZ[t]be the irreducible monic polynomial forp

3overZ=qZ. Given anya+bp

32Z=qZ[p

3]with

aandbnot both zero, consider the linear polynomialg(t) =a+bt. Thenp(t)andg(t) are relatively prime (sincep(t)is monic and irreducible). Thus there are polynomials such thath1(t)g(t) +h2(t)p(t) = 1; lettingt=p

3yieldsh1(p

3)g(p

3) = 1, so we

have found an inverse tog(p

3) =a+bp

3, provingZ=qZ[p

3]is a field.

We may study the subset of elements with multiplicative inverses,

¡Z=qZ[p

3] order of this multiplicative group is q2¡1; thus by Lagrange"s theorem every element x2Z=qZ[p

3]satisfiesxq2¡1= 1; note that here by equals1we mean with respect to

the multiplication operation ofZ=qZ[p

3](which includes multiplication moduloqandp

3¢p

3 = 3).

From (7), we see that

u t(p¡1)´RMp¢ut(p¡2)¡1 modq:(11)

AsqjMp,Mp´0 modq. Therefore

u t(p¡1)´ ¡1 modq:(12)

Similarly, looking at (9), we see that

u which implies that u t(p)´(0¡1)2´1 modq:(14)

4 SARAH MEIKLEJOHN AND STEVEN J. MILLER

The order of an elementgin our multiplicative group¡Z=qZ[p 3] positiveksuch thatgk= 1; we often denote this byord(g). By Lagrange"s theorem, kjq2¡1. Further, by (14) we know thatord(u)jt(p). We now show thatord(u)is exactlyt(p). From (14) we see thatord(u)jt(p). As t(s) = 2s, iford(u)6=t(p)thenord(u)jt(p¡1). But iford(u)dividedt(p¡1)then u t(p¡1)´1 modq;(15) which contradicts (12). Thusord(u) =t(p) = 2p. However, since the order of any element is at most the order of the group, we have ord(u) = 2p·q2¡1< Mp= 2p¡1;(16) where the second inequality follows fromq2·Mp. We thus obtain the contradiction 2 p<2p¡1;(17)

3.3.3is a square moduloq.

We finish the proof in the case that3is a square modulo q. This means thatt2¡3has a root inZ=qZ, or equivalently thatt2¡3factors into two linear terms inZ=qZ. For example, ifq= 13thent2¡3´(t¡4)(t¡9) modq.

Proof.

We now assume that3is a square moduloq; for definiteness, letb2= 3. In §3.1 we showed that u t(p¡1)=RMp¢ut(p¡2)¡1(18) and u t(p)= (RMp¢ut(p¡2)¡1)2:(19) Noteut(n)isnotnecessarilyaninteger. Wemayregardtheseequationsmoduloq. Doing so, we replacep

3withb. Reducing these equations moduloqyield

u t(p¡1)´ ¡1 modq(20) and u t(p)´1 modq:(21) Arguing as in §3.2,ord(u) = 2p; the only difference is that now there areq¡1non-zero elements in our fieldZ=qZ, and notq2¡1. We therefore have ord(u) = 2p·q¡1·Mp= 2p¡1;(22)

4.MERSENNEPRIMES ANDPERFECTNUMBERS

Another interesting fact about Mersenne primes is their correspondence with perfect numbers. Perfect numbers are integers whose proper divisors (all divisors except the number itself) sum to the number. For example,6 = 1 + 2 + 3and28 = 1 + 2 +

4 + 7 + 14. There is a one-to-one correspondence between even perfect numbers and

Mersenne primes. While it can be shown that every even perfect number is of the form (2 p¡1)¢2p¡1, where2p¡1is a Mersenne prime, we content ourselves with showing that any number of the form(2p¡1)¢2p¡1is perfect when2p¡1is a Mersenne prime.

MERSENNE PRIMES 5

Letq= 2p¡1be a Mersenne prime; we show thatq¢2p¡1is perfect. We know that the proper divisors break up into two disjoint sets: f1;2;4;:::;2p¡1g [ fq;2q;4q;:::;2p¡2qg:(23)

So, using the geometric formula

1 +x+x2+¢¢¢+xn¡1=xn¡1

x¡1;(24) we see that the first set sums to

1 + 2 + 4 +¢¢¢+ 2p¡1=2p¡1

2¡1= 2p¡1 =q;(25)

and the second set sums to q+2q+4q+¢¢¢+2p¡2q=q(1+2+4+¢¢¢+2p¡2) =qµ2p¡1¡1 =q(2p¡1¡1): (26)

Thus the sum of the proper divisors is

q+q(2p¡1¡1) =q+ 2p¡1q¡q= 2p¡1q;(27) proving that(2p¡1)¢2p¡1is perfect.

E-mail address:sjmiller@math.brown.edu

DEPARTMENT OFMATHEMATICS, BROWNUNIVERSITY, PROVIDENCE, RI02912quotesdbs_dbs17.pdfusesText_23