Gaussian integer

From Wikipedia, the free encyclopedia

 

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. This integral domain is a particular case of a commutative ring of quadratic integers. It does not have a total ordering that respects arithmetic.

 

Gaussian integers as lattice points in the complex plane

Basic definitions

The Gaussian integers are the set

${\displaystyle \mathbf {Z} [i]=\{a+bi\mid a,b\in \mathbf {Z} \},\qquad {\text{ where }}i^{2}=-1.}$

In other words, a Gaussian integer is a complex number such that its real and imaginary parts are both integers. Since the Gaussian integers are closed under addition and multiplication, they form a commutative ring, which is a subring of the field of complex numbers. It is thus an integral domain.

When considered within the complex plane, the Gaussian integers constitute the 2-dimensional integer lattice.

The conjugate of a Gaussian integer a + bi is the Gaussian integer a – bi.

The norm of a Gaussian integer is its product with its conjugate.

${\displaystyle N(a+bi)=(a+bi)(a-bi)=a^{2}+b^{2}.}$

The norm of a Gaussian integer is thus the square of its absolute value as a complex number. The norm of a Gaussian integer is a nonnegative integer, which is a sum of two squares. Thus a norm cannot be of the form 4k + 3, with k integer.

The norm is multiplicative, that is, one has

${\displaystyle N(zw)=N(z)N(w),}$

for every pair of Gaussian integers z,w. This can be shown either by a direct check, or by using the multiplicative property of the absolute value of complex numbers.

The units of the ring of Gaussian integers (that is the Gaussian integers whose multiplicative inverse is also a Gaussian integer) are precisely the Gaussian integers with norm 1, that is, 1, –1, i and –i.

Euclidean division

Visualization of maximal distance to some Gaussian integer

Gaussian integers have a Euclidean division (division with remainder) similar to that of integers and polynomials. This makes the Gaussian integers a Euclidean domain, and implies that Gaussian integers share with integers and polynomials many important properties such as the existence of a Euclidean algorithm for computing greatest common divisors, Bézout's identity, the principal ideal property, Euclid's lemma, the unique factorization theorem, and the Chinese remainder theorem, all of which can be proved using only Euclidean division.

A Euclidean division algorithm takes, in the ring of Gaussian integers, a dividend a and divisor b ≠ 0, and produces a quotient q and remainder r such that

${\displaystyle a=bq+r\quad {\text{and}}\quad N(r)$

In fact, one may make the remainder smaller:

${\displaystyle a=bq+r\quad {\text{and}}\quad N(r)\leq {\frac {N(b)}{2}}.}$

Even with this better inequality, the quotient and the remainder are not necessarily unique, but one may refine the choice to ensure uniqueness.
To prove this, one may consider the complex number quotient x + iy = a/b. There are unique integers m and n such that –1/2 < x – m ≤ 1/2 and –1/2 < y – n ≤ 1/2, and thus N(x – m + i(y – n)) ≤ 1/2. Taking q = m + in, one has

${\displaystyle a=bq+r,}$

with

${\displaystyle r=b{\bigl (}x-m+i(y-n){\bigr )},}$

and

${\displaystyle N(r)\leq {\frac {N(b)}{2}}.}$

The choice of x – m and y – n in a semi-open interval is required for uniqueness. This definition of Euclidean division may be interpreted geometrically in the complex plane (see the figure), by remarking that the distance from a complex number ξ to the closest Gaussian integer is at most √2/2.

Principal ideals

Since the ring G of Gaussian integers is a Euclidean domain, G is a principal ideal domain, which means that every ideal of G is principal. Explicitly, an ideal I is a subset of a ring R such that every sum of elements of I and every product of an element of I by an element of R belong to I. An ideal is principal, if it consists of all multiples of a single element g, that is, it has the form

${\displaystyle \{gx\mid x\in G\}.}$

In this case, one says that the ideal is generated by g or that g is a generator of the ideal.

Every ideal I in the ring of the Gaussian integers is principal, because, if one chooses in I an nonzero element g of minimal norm, for every element x of I, the remainder of Euclidean division of x by g belongs also to I and has a norm that is smaller than that of g; because of the choice of g, this norm is zero, and thus the remainder is also zero. That is, one has x = qg, where q is the quotient.

For any g, the ideal generated by g is also generated by any associate of g, that is, g, gi, –g, –gi; no other element generates the same ideal. As all the generators of an ideal have the same norm, the norm of an ideal is the norm of any of its generators.

In some circumstances, it is useful to choose, once for all, a generator for each ideal. There are two classical ways for doing that, both considering first the ideals of odd norm. If the g = a + bi has an odd norm a² + b², then one of a and b is odd, and the other is even. Thus g has exactly one associate with a real part a that is odd and positive. In its original paper, Gauss did another choice, by choosing the unique associate such that the remainder of its division by 2 + 2i is one. In fact, as N(2 + 2i) = 8, the norm of the remainder is not greater than 4. As this norm is odd, and 3 is not the norm of a Gaussian integer, the norm of the remainder is one, that is, the remainder is a unit. Multiplying g by the inverse of this unit, one finds an associate that has one as a remainder, when divided by 2 + 2i.

If the norm of g is even, then either g = 2^kh or g = 2^kh(1 + i), where k is a positive integer, and N(h) is odd. Thus, one chooses the associate of g for getting a h which fits the choice of the associates for elements of odd norm.

Gaussian primes

As the Gaussian integers form a principal ideal domain they form also a unique factorization domain. This implies that a Gaussian integer is irreducible (that is, it is not the product of two non-units) if and only if it is prime (that is, it generates a prime ideal).

The prime elements of Z[i] are also known as Gaussian primes. An associate of a Gaussian prime is also a Gaussian prime. The conjugate of a Gaussian prime is also a Gaussian prime (this implies that Gaussian primes are symmetric about the real and imaginary axes).

A positive integer is a Gaussian prime if and only if it is a prime number that is congruent to 3 modulo 4 (that is, it may be written 4n + 3, with n a nonnegative integer) (sequence A002145 in the OEIS). The other prime numbers are not Gaussian primes, but each is the product of two conjugate Gaussian primes.

A Gaussian integer a + bi is a Gaussian prime if and only if either:

• one of a, b is zero and absolute value of the other is a prime number of the form 4n + 3 (with n a nonnegative integer), or
• both are nonzero and a² + b² is a prime number (which will not be of the form 4n + 3).

In other words, a Gaussian integer is a Gaussian prime if and only if either its norm is a prime number, or it is the product of a unit (±1, ±i) and a prime number of the form 4n + 3.
It follows that there are three cases for the factorization of a prime number p in the Gaussian integers:

• If p is congruent to 3 modulo 4, then it is a Gaussian prime; in the language of algebraic number theory, p is said to be inert in the Gaussian integers.
• If p is congruent to 1 modulo 4, then it is the product of a Gaussian prime by its conjugate, both of which are non-associated Gaussian primes (neither is the product of the other by a unit); p is said to be a decomposed prime in the Gaussian integers. For example, 5 = (2 + i)(2 − i) and 13 = (3 + 2i)(3 − 2i).
• If p = 2, we have 2 = (1 + i)(1 − i) = i(1 − i)²; that is, 2 is the product of the square of a Gaussian prime by a unit; it is the unique ramified prime in the Gaussian integers.

Unique factorization

As for every unique factorization domain, every Gaussian integer may be factored as a product of a unit and Gaussian primes, and this factorization is unique up to the order of the factors, and the replacement of any prime by any of its associates (together with a corresponding change of the unit factor).

If one chooses, once for all, a fixed Gaussian prime for each equivalence class of associated primes, and if one takes only these selected primes in the factorization, then one obtains a prime factorization which is unique up to the order of the factors. With the choices described above, the resulting unique factorization has the form

${\displaystyle u(1+i)^{e_{0}}{p_{1}}^{e_{1}}\cdots {p_{k}}^{e_{k}},}$

where u is a unit (that is, u ∈ {1, –1, i, –i}), e₀ and k are nonnegative integers, e₁, …, e_k are positive integers, and p₁, …, p_k are distinct Gaussian primes such that, depending on the choice of selected associates,

• either p_k = a_k + ib_k with a odd and positive, and b even,
• or the remainder of the Euclidean division of p_k by 2 + 2i equals 1 (this is Gauss's original choice).

An advantage of the second choice is that the selected associates behave well under products for Gaussian integers of odd norm. On the other hand, the selected associate for the real Gaussian primes are negative integers. For example, the factorization of 231 in the integers, and with the first choice of associates is 3 × 7 × 11, while it is –1 × –3 × –7 × –11 with the second choice.

Gaussian rationals

The field of Gaussian rationals is the field of fractions of the ring of Gaussian integers. It consists of the complex numbers whose real and imaginary part are both rational.

The ring of Gaussian integers is the integral closure of the integers in the Gaussian rationals.

This implies that Gaussian integers are quadratic integers and that a Gaussian rational is a Gaussian integer, if and only if it is a solution of an equation

${\displaystyle x^{2}+cx+d=0,}$

with c and d integers. In fact a + bi is solution of the equation

${\displaystyle x^{2}-2ax+a^{2}+b^{2},}$

and this equation has integer coefficients if and only if a and b are both integers.

Greatest common divisor

As for any unique factorization domain, a greatest common divisor (gcd) of two Gaussian integers a, b is a Gaussian integer d that is a common divisor of a and b, which has all common divisors of a and b as divisor. That is (where | denotes the divisibility relation),

• d | a and d | b, and
• c | a and c | b implies c | d.

Thus, greatest is meant relatively to the divisibility relation, and not for an ordering of the ring (for integers, both meanings of greatest coincide).

More technically, a greatest common divisor of a and b is a generator of the ideal generated by a and b (this characterization is valid for principal ideal domains, but not, in general, for unique factorization domains).

The greatest common divisor of two Gaussian integers is not unique, but is defined up to the multiplication by a unit. That is, given a greatest common divisor d of a and b, the greatest common divisors of a and b are d, –d, id, and –id.

There are several ways for computing a greatest common divisor of two Gaussian integers a and b. When one know prime factorizations of a and b,

${\displaystyle a=i^{k}\prod _{m}{p_{m}}^{\nu _{m}},\quad b=i^{n}\prod _{m}{p_{m}}^{\mu _{m}},}$

where the primes p_m are pairwise non associated, and the exponents μ_m non-associated, a greatest common divisor is

${\displaystyle \prod _{m}{p_{m}}^{\lambda _{m}},}$

with

${\displaystyle \lambda _{m}=\min(\nu _{m},\mu _{m}).}$

Unfortunately, except in simple cases, the prime factorization is difficult to compute, and Euclidean algorithm leads to a much easier (and faster) computation. This algorithm consists of replacing of the input (a, b) by (b, r), where r is the remainder of the Euclidean division of a by b, and repeating this operation until getting a zero remainder, that is a pair (d, 0). This process terminates, because, at each step, the norm of the second Gaussian integer decreases. The resulting d is a greatest common divisor, because (at each step) b and r = a – bq have the same divisors as a and b, and thus the same greatest common divisor.

This method of computation works always, but is not as simple as for integers because Euclidean division is more complicate. Therefore, a third method is often preferred for hand-written computations. It consists in remarking that the norm N(d) of the greatest common divisor of a and b is a common divisor of N(a), N(b), and N(a + b). When the greatest common divisor D of these three integers has few factors, then it is easy to test, for common divisor, all Gaussian integers with a norm dividing D.

For example, if a = 5 + 3i, and b = 2 – 8i, one has N(a) = 34, N(b) = 68, and N(a + b) = 74. As the greatest common divisor of the three norms is 2, the greatest common divisor of a and b has 1 or 2 as a norm. As a gaussian integer of norm 2 is necessary associated to 1 + i, and as 1 + i divides a and b, then the greatest common divisor is 1 + i.

If b is replaced by its conjugate b = 2 + 8i, then the greatest common divisor of the three norms is 34, the norm of a, thus one may guess that the greatest common divisor is a, that is, that a | b. In fact, one has 2 + 8i = (5 + 3i)(1 + i).

Congruences and residue classes

Given a Gaussian integer z₀, called a modulus, two Gaussian integers z₁,z₂ are congruent modulo z₀, if their difference is a multiple of z₀, that is if there exists a Gaussian integer q such that z₁ − z₂ = qz₀. In other words, two Gaussian integers are congruent modulo z₀, if their difference belongs to the ideal generated by z₀. This is denoted as z₁ ≡ z₂ (mod z₀).

The congruence modulo z₀ is an equivalence relation (also called a congruence relation), which defines a partition of the Gaussian integers into equivalence classes, called here congruence classes or residue classes. The set of the residue classes is usually denoted Z[i]/z₀Z[i], or Z[i]/⟨z₀⟩, or simply Z[i]/z₀.

The residue class of a Gaussian integer a is the set

${\displaystyle {\bar {a}}:=\left\{z\in \mathbf {Z} [i]\mid z\equiv a{\pmod {z_{0}}}\right\}}$

of all Gaussian integers that are congruent to a. It follows that a = b if and only if a ≡ b (mod z₀).
Addition and multiplication are compatible with congruences. This means that a₁ ≡ b₁ (mod z₀) and a₂ ≡ b₂ (mod z₀) imply a₁ + a₂ ≡ b₁ + b₂ (mod z₀) and a₁a₂ ≡ b₁b₂ (mod z₀). This defines well-defined operations (that is independent of the choice of representatives) on the residue classes:

${\displaystyle {\bar {a}}+{\bar {b}}:={\overline {a+b}}\quad {\text{and}}\quad {\bar {a}}\cdot {\bar {b}}:={\overline {ab}}.}$

With these operations, the residue classes form a commutative ring, the quotient ring of the Gaussian integers by the ideal generated by z₀, which is also traditionally called the residue class ring modulo z₀ (for more details, see Quotient ring).

Examples

• There are exactly two residue classes for the modulus 1 + i, namely 0 = {0, ±2, ±4,…,±1 ± i, ±3 ± i,…} (all multiples of 1 + i), and 1 = {±1, ±3, ±5,…, ±i, ±2 ± i,…}, which form a checkerboard pattern in the complex plane. These two classes form thus a ring with two elements, which is, in fact, a field, the unique (up to an isomorphism) field with two elements, and may thus be identified with the integers modulo 2. These two classes may be considered as a generalization of the partition of integers into even and odd integers. Thus one may speak of even and odd Gaussian integers (Gauss divided further even Gaussian integers into even, that is divisible by 2, and half-even).
• For the modulus 2 there are four residue classes, namely 0, 1, i, 1 + i. These form a ring with four elements, in which x = –x for every x. Thus this ring is not isomorphic with the ring of integers modulo 4, another ring with four elements. One has 1 + i² = 0, and thus this ring is not the finite field with four elements, nor the direct product of two copies of the ring of integers modulo 2.
• For the modulus 2 + 2i = (i − 1)³ there are eight residue classes, namely 0, ±1, ±i, 1 ± i, 2, whereof four contain only even Gaussian integers and four contain only odd Gaussian integers.

Describing residue classes

All 13 residue classes with their minimal residues (blue dots) in the square Q₀₀ (light green background) for the modulus z₀ = 3 + 2i. One residue class with z = 2 − 4i ≡ −i (mod z₀) is highlighted with yellow/orange dots.

Given a modulus z₀, all elements of a residue class have the same remainder for the Euclidean division by z₀, provided one uses the division with unique quotient and remainder, which is described above. Thus enumerating the residue classes is equivalent with enumerating the possible remainders. This can be done geometrically in the following way.

In the complex plane, one may consider a square grid, whose squares are delimited by the two lines

${\displaystyle {\begin{aligned}V_{s}&=\left\{\left.z_{0}\left(s-{\tfrac {1}{2}}+ix\right)\right\vert x\in \mathbf {R} \right\}\quad {\text{and}}\\H_{t}&=\left\{\left.z_{0}\left(x+i\left(t-{\tfrac {1}{2}}\right)\right)\right\vert x\in \mathbf {R} \right\},\end{aligned}}}$

with s and t integers (blue lines in the figure). These divide the plane in semi-open squares (where m and n are integers)

${\displaystyle Q_{mn}=\left\{(s+it)z_{0}\left\vert s\in \left[m-{\tfrac {1}{2}},m+{\tfrac {1}{2}}\right),t\in \left[n-{\tfrac {1}{2}},n+{\tfrac {1}{2}}\right)\right.\right\}.}$

The semi-open intervals that occur in the definition of Q_mn have been chosen in order that every complex number belong to exactly one square; that is, the squares Q_mn form a partition of the complex plane. One has

${\displaystyle Q_{mn}=(m+in)z_{0}+Q_{00}=\left\{(m+in)z_{0}+z\mid z\in Q_{00}\right\}.}$

This implies that every Gaussian integer is congruent modulo z₀ to a unique Gaussian integer in Q₀₀ (the green square in the figure), which its remainder for the division by z₀. In other words, every residue class contains exactly one element in Q₀₀.

The Gaussian integers in Q₀₀ (or in its boundary) are sometimes called minimal residues because their norm are not greater than the norm of any other Gaussian integer in the same residue class (Gauss called them absolutely smallest residues).

From this one can deduce by geometrical considerations, that the number of residue classes modulo a Gaussian integer z₀ = a + bi equals his norm N(z₀) = a² + b².

Residue class fields

The residue class ring modulo a Gaussian integer z₀ is a field if and only if ${\displaystyle z_{0}}$ is a Gaussian prime.
If z₀ is a decomposed prime or the ramified prime 1 + i (that is, if its norm N(z₀) is a prime number, which is either 2 or a prime congruent to 1 modulo 4), then the residue class field has a prime number of elements (that is, N(z₀)). It is thus isomorphic to the field of the integers modulo N(z₀).

If, on the other hand, z₀ is an inert prime (that is, N(z₀) = p² is the square of a prime number, which is congruent to 3 modulo 4), then the residue class field has p² elements, and it is an extension of degree 2 (unique, up to an isomorphism) of the prime field with p elements (the integers modulo p).

Primitive residue class group and Euler's totient function

Many theorems (and their proofs) for moduli of integers can be directly transferred to moduli of Gaussian integers, if one replaces the absolute value of the modulus by the norm. This holds especially for the primitive residue class group (also called multiplicative group of integers modulo n) and Euler's totient function. The primitive residue class group of a modulus z is defined as the subset of its residue classes, which contains all residue classes a that are coprime to z, i.e. (a,z) = 1. Obviously, this system builds a multiplicative group. The number of its elements shall be denoted by ϕ(z) (analogously to Euler's totient function φ(n) for integers n).

For Gaussian primes it immediately follows that ϕ(p) = |p|² − 1 and for arbitrary composite Gaussian integers

${\displaystyle z=i^{k}\prod _{m}{p_{m}}^{\nu _{m}}}$

Euler's product formula can be derived as

${\displaystyle \phi (z)=\prod _{m\,(\nu _{m}>0)}|{p_{m}}^{\nu _{m}}|^{2}\left(1-{\frac {1}{|p_{m}|^{2}}}\right)=|z|^{2}\prod _{p_{m}|z}\left(1-{\frac {1}{|p_{m}|^{2}}}\right)}$

where the product is to build over all prime divisors p_m of z (with ν_m > 0). Also the important theorem of Euler can be directly transferred:

For all a with (a,z) = 1, it holds that a^ϕ(z) ≡ 1 (mod z).

Historical background

The ring of Gaussian integers was introduced by Carl Friedrich Gauss in his second monograph on quartic reciprocity (1832). The theorem of quadratic reciprocity (which he had first succeeded in proving in 1796) relates the solvability of the congruence x² ≡ q (mod p) to that of x² ≡ p (mod q). Similarly, cubic reciprocity relates the solvability of x³ ≡ q (mod p) to that of x³ ≡ p (mod q), and biquadratic (or quartic) reciprocity is a relation between x⁴ ≡ q (mod p) and x⁴ ≡ p (mod q). Gauss discovered that the law of biquadratic reciprocity and its supplements were more easily stated and proved as statements about "whole complex numbers" (i.e. the Gaussian integers) than they are as statements about ordinary whole numbers (i.e. the integers).

In a footnote he notes that the Eisenstein integers are the natural domain for stating and proving results on cubic reciprocity and indicates that similar extensions of the integers are the appropriate domains for studying higher reciprocity laws.

This paper not only introduced the Gaussian integers and proved they are a unique factorization domain, it also introduced the terms norm, unit, primary, and associate, which are now standard in algebraic number theory.

Unsolved problems

The distribution of the small Gaussian primes in the complex plane

Most of the unsolved problems are related to distribution of Gaussian primes in the plane.

• Gauss's circle problem does not deal with the Gaussian integers per se, but instead asks for the number of lattice points inside a circle of a given radius centered at the origin. This is equivalent to determining the number of Gaussian integers with norm less than a given value.

There are also conjectures and unsolved problems about the Gaussian primes. Two of them are:

• The real and imaginary axes have the infinite set of Gaussian primes 3, 7, 11, 19, ... and their associates. Are there any other lines that have infinitely many Gaussian primes on them? In particular, are there infinitely many Gaussian primes of the form 1 + ki?
• Is it possible to walk to infinity using the Gaussian primes as stepping stones and taking steps of a uniformly bounded length? This is known as the Gaussian moat problem; it was posed in 1962 by Basil Gordon and remains unsolved.

Perfect number

From Wikipedia, the free encyclopedia

 

Illustration of the perfect number status of the number 6

In number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself (also known as its aliquot sum). Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself) i.e. σ₁(n) = 2n.

This definition is ancient, appearing as early as Euclid's Elements (VII.22) where it is called τέλειος ἀριθμός (perfect, ideal, or complete number). Euclid also proved a formation rule (IX.36) whereby ${\displaystyle q(q+1)/2}$ is an even perfect number whenever ${\displaystyle q}$ is a prime of the form ${\displaystyle 2^{p}-1}$ for prime ${\displaystyle p}$—what is now called a Mersenne prime. Much later, Euler proved that all even perfect numbers are of this form. This is known as the Euclid–Euler theorem.

It is not known whether there are any odd perfect numbers, nor whether infinitely many perfect numbers exist.

Examples

The first perfect number is 6. Its proper divisors are 1, 2, and 3, 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. The next perfect number is 28: 28 = 1 + 2 + 4 + 7 + 14. This is followed by the perfect numbers 496 and 8128 (sequence A000396 in the OEIS).

History

In about 300 BC Euclid showed that if 2^p − 1 is prime then (2^p − 1)2^p−1 is perfect. The first four perfect numbers were the only ones known to early Greek mathematics, and the mathematician Nicomachus had noted 8128 as early as 100 AD. Philo of Alexandria in his first-century book "On the creation" mentions perfect numbers, claiming that the world was created in 6 days and the moon orbits in 28 days because 6 and 28 are perfect. Philo is followed by Origen, and by Didymus the Blind, who adds the observation that there are only four perfect numbers that are less than 10,000. (Commentary on Genesis 1. 14-19). St Augustine defines perfect numbers in City of God (Part XI, Chapter 30) in the early 5th century AD, repeating the claim that God created the world in 6 days because 6 is the smallest perfect number. The Egyptian mathematician Ismail ibn Fallūs (1194–1252) mentioned the next three perfect numbers (33,550,336; 8,589,869,056; and 137,438,691,328) and listed a few more which are now known to be incorrect. In a manuscript written between 1456 and 1461, an unknown mathematician recorded the earliest European reference to a fifth perfect number, with 33,550,336 being correctly identified for the first time. In 1588, the Italian mathematician Pietro Cataldi also identified the sixth (8,589,869,056) and the seventh (137,438,691,328) perfect numbers, and also proved that every perfect number obtained from Euclid's rule ends with a 6 or an 8.

Even perfect numbers

Euclid proved that 2^p−1(2^p − 1) is an even perfect number whenever 2^p − 1 is prime (Euclid, Prop. IX.36).

For example, the first four perfect numbers are generated by the formula 2^p−1(2^p − 1), with p a prime number, as follows:

for p = 2:   2¹(2² − 1) = 6

for p = 3:   2²(2³ − 1) = 28

for p = 5:   2⁴(2⁵ − 1) = 496

for p = 7:   2⁶(2⁷ − 1) = 8128.

Prime numbers of the form 2^p − 1 are known as Mersenne primes, after the seventeenth-century monk Marin Mersenne, who studied number theory and perfect numbers. For 2^p − 1 to be prime, it is necessary that p itself be prime. However, not all numbers of the form 2^p − 1 with a prime p are prime; for example, 2¹¹ − 1 = 2047 = 23 × 89 is not a prime number. In fact, Mersenne primes are very rare—of the 2,270,720 prime numbers p up to 37,156,667, 2^p − 1 is prime for only 45 of them.

Nicomachus (60–120 AD) conjectured that every perfect number is of the form 2^p−1(2^p − 1) where 2^p − 1 is prime. Ibn al-Haytham (Alhazen) circa 1000 AD conjectured that every even perfect number is of that form. It was not until the 18th century that Leonhard Euler proved that the formula 2^p−1(2^p − 1) will yield all the even perfect numbers. Thus, there is a one-to-one correspondence between even perfect numbers and Mersenne primes; each Mersenne prime generates one even perfect number, and vice versa. This result is often referred to as the Euclid–Euler theorem. As of January 2018, 50 Mersenne primes are known, and therefore 50 even perfect numbers (the largest of which is 2^77232916 × (2^77232917 − 1) with 46,498,850 digits).

An exhaustive search by the GIMPS distributed computing project has shown that the first 47 even perfect numbers are 2^p−1(2^p − 1) for

p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, and 43112609 (sequence A000043 in the OEIS).

Three higher perfect numbers have also been discovered, namely those for which p = 57885161, 74207281, and 77232917, though there may be others within this range. It is not known whether there are infinitely many perfect numbers, nor whether there are infinitely many Mersenne primes.

As well as having the form 2^p−1(2^p − 1), each even perfect number is the (2^p − 1)th triangular number (and hence equal to the sum of the integers from 1 to 2^p − 1) and the 2^p−1th hexagonal number. Furthermore, each even perfect number except for 6 is the ((2^p + 1)/3)th centered nonagonal number and is equal to the sum of the first 2^(p−1)/2 odd cubes:

${\displaystyle {\begin{aligned}6&=2^{1}(2^{2}-1)&&=1+2+3,\\[8pt]28&=2^{2}(2^{3}-1)&&=1+2+3+4+5+6+7=1^{3}+3^{3},\\[8pt]496&=2^{4}(2^{5}-1)&&=1+2+3+\cdots +29+30+31\\&&&=1^{3}+3^{3}+5^{3}+7^{3},\\[8pt]8128&=2^{6}(2^{7}-1)&&=1+2+3+\cdots +125+126+127\\&&&=1^{3}+3^{3}+5^{3}+7^{3}+9^{3}+11^{3}+13^{3}+15^{3},\\[8pt]33550336&=2^{12}(2^{13}-1)&&=1+2+3+\cdots +8189+8190+8191\\&&&=1^{3}+3^{3}+5^{3}+\cdots +123^{3}+125^{3}+127^{3}.\end{aligned}}}$

Even perfect numbers (except 6) are of the form

${\displaystyle T_{2^{p}-1}=1+{\frac {(2^{p}-2)\times (2^{p}+1)}{2}}=1+9\times T_{(2^{p}-2)/3}}$

with each resulting triangular number (after subtracting 1 from the perfect number and dividing the result by 9) ending in 3 or 5, the sequence starting with 3, 55, 903, 3727815, ... This can be reformulated as follows: adding the digits of any even perfect number (except 6), then adding the digits of the resulting number, and repeating this process until a single digit (called the digital root) is obtained, always produces the number 1. For example, the digital root of 8128 is 1, because 8 + 1 + 2 + 8 = 19, 1 + 9 = 10, and 1 + 0 = 1. This works with all perfect numbers 2^p−1(2^p − 1) with odd prime p and, in fact, with all numbers of the form 2^m−1(2^m − 1) for odd integer (not necessarily prime) m.

Owing to their form, 2^p−1(2^p − 1), every even perfect number is represented in binary as p ones followed by p − 1  zeros; for example,

6₁₀ = 110₂

28₁₀ = 11100₂

496₁₀ = 111110000₂

and

8128₁₀ = 1111111000000₂.

Thus every even perfect number is a pernicious number.

Note that every even perfect number is also a practical number.

Odd perfect numbers

It is unknown whether there is any odd perfect number, though various results have been obtained. In 1496, Jacques Lefèvre stated that Euclid's rule gives all perfect numbers, thus implying that no odd perfect number exists. More recently, Carl Pomerance has presented a heuristic argument suggesting that indeed no odd perfect number should exist. All perfect numbers are also Ore's harmonic numbers, and it has been conjectured as well that there are no odd Ore's harmonic numbers other than 1.

Any odd perfect number N must satisfy the following conditions:

• N > 10¹⁵⁰⁰.
• N is not divisible by 105.
• N is of the form N ≡ 1 (mod 12), N ≡ 117 (mod 468), or N ≡ 81 (mod 324).
• N is of the form

${\displaystyle N=q^{\alpha }p_{1}^{2e_{1}}\cdots p_{k}^{2e_{k}},}$

where:

• q, p₁, ..., p_k are distinct primes (Euler).
• q ≡ α ≡ 1 (mod 4) (Euler).
• The smallest prime factor of N is less than (2k + 8) / 3.
• Either q^α > 10⁶², or p_j^2e_j  > 10⁶² for some j.^[20]
• N < 2^4k+1.
• ${\displaystyle \alpha +2e_{1}+2e_{2}+2e_{3}+\cdots +2e_{k}\geq (21k-18)/8}$ 

• The largest prime factor of N is greater than 10⁸.
• The second largest prime factor is greater than 10⁴, and the third largest prime factor is greater than 100.
• N has at least 101 prime factors and at least 10 distinct prime factors. If 3 is not one of the factors of N, then N has at least 12 distinct prime factors.

In 1888, Sylvester stated:

...a prolonged meditation on the subject has satisfied me that the existence of any one such [odd perfect number] — its escape, so to say, from the complex web of conditions which hem it in on all sides — would be little short of a miracle.

Euler stated: "Whether (...) there are any odd perfect numbers is a most difficult question".

Minor results

All even perfect numbers have a very precise form; odd perfect numbers either do not exist or are rare. There are a number of results on perfect numbers that are actually quite easy to prove but nevertheless superficially impressive; some of them also come under Richard Guy's strong law of small numbers:

• The only even perfect number of the form x³ + 1 is 28 (Makowski 1962).
• 28 is also the only even perfect number that is a sum of two positive cubes of integers (Gallardo 2010).
• The reciprocals of the divisors of a perfect number N must add up to 2 (to get this, take the definition of a perfect number, ${\displaystyle \sigma _{1}(n)=2n}$, and divide both sides by n):
  • For 6, we have ${\displaystyle 1/6+1/3+1/2+1/1=2}$;
  • For 28, we have ${\displaystyle 1/28+1/14+1/7+1/4+1/2+1/1=2}$, etc.
• The number of divisors of a perfect number (whether even or odd) must be even, because N cannot be a perfect square.
  • From these two results it follows that every perfect number is an Ore's harmonic number.
• The even perfect numbers are not trapezoidal numbers; that is, they cannot be represented as the difference of two positive non-consecutive triangular numbers. There are only three types of non-trapezoidal numbers: even perfect numbers, powers of two, and the numbers of the form ${\displaystyle 2^{n-1}(2^{n}+1)}$ formed as the product of a Fermat prime ${\displaystyle 2^{n}+1}$ with a power of two in a similar way to the construction of even perfect numbers from Mersenne primes.
• The number of perfect numbers less than n is less than ${\displaystyle c{\sqrt {n}}}$, where c > 0 is a constant. In fact it is ${\displaystyle o({\sqrt {n}})}$, using little-o notation.
• Every even perfect number ends in 6 or 28, base ten; and, with the only exception of 6, ends in 1, base 9. Therefore in particular the digital root of every even perfect number other than 6 is 1.
• The only square-free perfect number is 6.

Related concepts

The sum of proper divisors gives various other kinds of numbers. Numbers where the sum is less than the number itself are called deficient, and where it is greater than the number, abundant. These terms, together with perfect itself, come from Greek numerology. A pair of numbers which are the sum of each other's proper divisors are called amicable, and larger cycles of numbers are called sociable. A positive integer such that every smaller positive integer is a sum of distinct divisors of it is a practical number.

By definition, a perfect number is a fixed point of the restricted divisor function s(n) = σ(n) − n, and the aliquot sequence associated with a perfect number is a constant sequence. All perfect numbers are also ${\displaystyle {\mathcal {S}}}$-perfect numbers, or Granville numbers.

A semiperfect number is a natural number that is equal to the sum of all or some of its proper divisors. A semiperfect number that is equal to the sum of all its proper divisors is a perfect number. Most abundant numbers are also semiperfect; abundant numbers which are not semiperfect are called weird numbers.