4.4: Perfect, Mersenne, and Fermat Numbers
( \newcommand{\kernel}{\mathrm{null}\,}\)
Integers with certain properties were studied extensively over the centuries. We present some examples of such integers and prove theorems related to these integers and their properties.
We start by defining perfect numbers.
A positive integer n is called a perfect number if σ(n)=2n.
In other words, a perfect number is a positive integer which is the sum of its proper divisors.
The first perfect number is 6, since σ(6)=12. You can also view this as 6=1+2+3. The second perfect number is 28, since σ(28)=56 or 28=1+2+4+7+14.
The following theorem tells us which even positive integers are perfect.
The positive integer n is an even perfect number if and only if n=2l−1(2l−1), where l is an integer such that l≥2 and 2l−1 is prime.
We show first that if n=2l−1(2l−1) where l is an integer such that l≥2 and 2l−1 is prime then n is perfect. Notice that 2l−1 is odd and thus (2l−1,2l−1)=1. Also, notice that σ is a multiplicative function and thus σ(n)=σ(2l−1)σ(2l−1). Notice that σ(2l−1)=2l−1 and since 2l−1 is prime we get σ(2l−1)=2l. Thus σ(n)=2n. We now prove the converse. Suppose that n is a perfect number. Let n=2rs, where r and s are positive integers and s is odd. Since (2r,s)=1, we get σ(n)=σ(2r)σ(s)=(2r+1−1)σ(s). Since n is perfect, we get (2r+1−1)σ(s)=2r+1s. Notice now that (2r+1−1,2r+1)=1 and thus 2r+1∣σ(s). Therefore there exists an integer q such that σ(s)=2r+1q. As a result, we have (2r+1−1)2r+1q=2r+1s and thus we get (2r+1−1)q=s So we get that q∣s. We add q to both sides of the above equation and we get s+q=(2r+1−1)q+q=2r+1q=σ(s). We have to show now that q=1. Notice that if q≠1, then s will have three divisors and thus σ(s)≥1+s+q. Hence q=1 and as a result s=2r+1−1. Also notice that σ(s)=s+1. This shows that s is prime since the only divisors of s are 1 and s. As a result, n=2r(2r+1−1), where (2r+1−1) is prime.
In theorem 50, we see that to determine even perfect numbers, we need to find primes of the form 2l−1. It is still unknown whether there are odd perfect numbers or not.
If 2l−1 is prime where l is a positive integer, then l must be prime.
Suppose that l is composite, that is l=rs where 1<r<m and 1<s<m. Thus after factoring, we get that 2m−1=(2r−1)(2r(s−1)+2r(s−2)+...+2r+1) Notice that the two factors above are both greater than 1. Thus 2m−1 is not prime. This is a contradiction.
The above theorem motivates the definition of interesting numbers called Mersenne numbers.
Let l be a positive integer. An integer of the form Ml=2l−1 is called the lth Mersenne number; if l is prime then Ml=2l−1 is called the lth Mersenne prime.
M3=23−1=7 is the third Mersenne prime.
We prove a theorem that help decide whether Mersenne numbers are prime.
Divisors of Mp=2p−1 for prime p is of the form 2mp+1, where m is a positive integer.
Let p1 be a prime dividing Mp=2p−1. By Fermat’s theorem, we know that p1∣(2p1−1−1). Also, it is easy to see that (2p−1,2p1−1−1)=2(p,p1−1)−1. Since p1 is a common divisor of 2p−1 and 2p1−1−1 and thus not relatively prime. Hence (p,p1−1)=p. Hence p∣(p1−1) and thus there exists a positive integer k such that p1−1=kp. Since p1 is odd, then k is even and thus k=2m. Hence p1=kp+1=2mp+1. Because any divisor of Mp is a product of prime divisors of Mp, each prime divisor of Mp is of the form 2mp+1 and the result follows.
M23=223−1 is divisible by 47=46k+1. We know this by trial and error and thus looking at all primes of the form 46k+1 that are less than √M23.
We now define Fermat numbers and prove some theorems about the properties of these numbers.
Integers of the form Fn=22n+1 are called Fermat numbers.
Fermat conjectured that these integers are primes but it turned out that this is not true. Notice that F0=3, F1=5, F2=17, F3=257 and F4=65,537 while F5 is composite. It turned out the F5 is divisible by 641. We now present a couple of theorems about the properties of these numbers.
For all positive integers n, we have F0F1F2...Fn−1=Fn−2
We will prove this theorem by induction. For n=1, the above identity is true. Suppose now that F0F1F2...Fn−1=Fn−2 holds. We claim that F0F1F2...Fn=Fn+1−2. Notice that F0F1F2...Fn=(Fn−2)Fn=(22n−1)(22n+1)=22n+1−1=Fn+1−2.
Using Theorem 53, we prove that Fermat numbers are relatively prime.
Let s≠t be nonnegative integers. Then (Fs,Ft)=1.
Assume without loss of generality that s<t. Thus by Theorem 52, we have F0F1F2...Fs...Ft−1=Ft−2 Assume now that there is a common divisor d of Fs and Ft. thus we see that d divides Ft−F0F1F2...Fs...Ft−1=2. Thus d=1 or d=2. But since Ft is odd for all t. We have d=1. Thus Fs and Ft are relatively prime.
Exercises
- Find the six smallest even perfect numbers.
- Find the eighth perfect number.
- Find a factor of 21001−1.
- We say n is abundant if σ(n)>2n. Prove that if n=2m−1(2m−1) where m is a positive integer such that 2m−1 is composite, then n is abundant.
- Show that there are infinitely many even abundant numbers.
- Show that there are infinitely many odd abundant numbers.
- Determine whether M11 is prime.
- Determine whether M29 is prime.
- Find all primes of the form 22n+5 where n is a nonnegative integer.
Contributors and Attributions
Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.