Mersenne prime

In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a number that can be written in the form Mn = 2n −1 for some integer n. They are named after Marin Mersenne, a French Minim friar, the first four Mersenne primes are 3,7,31, and 127. If n is a number so is 2n −1. The definition is therefore unchanged when written Mp = 2p −1 where p is assumed prime, more generally, numbers of the form Mn = 2n −1 without the primality requirement are called Mersenne numbers. The smallest composite pernicious Mersenne number is 211 −1 =2047 =23 ×89, Mersenne primes Mp are noteworthy due to their connection to perfect numbers. As of January 2016,49 Mersenne primes are known, the largest known prime number 274,207,281 −1 is a Mersenne prime. Since 1997, all newly found Mersenne primes have been discovered by the “Great Internet Mersenne Prime Search”, many fundamental questions about Mersenne primes remain unresolved. It is not even whether the set of Mersenne primes is finite or infinite.

The Lenstra–Pomerance–Wagstaff conjecture asserts that there are infinitely many Mersenne primes,23 | M11,47 | M23,167 | M83,263 | M131,359 | M179,383 | M191,479 | M239, and 503 | M251. Since for these primes p, 2p +1 is congruent to 7 mod 8, so 2 is a quadratic residue mod 2p +1, since p is a prime, it must be p or 1. The first four Mersenne primes are M2 =3, M3 =7, M5 =31, a basic theorem about Mersenne numbers states that if Mp is prime, the exponent p must be prime. This follows from the identity 2 a b −1 = ⋅ = ⋅ and this rules out primality for Mersenne numbers with composite exponent, such as M4 =24 −1 =15 =3 ×5 = ×. Though the above examples might suggest that Mp is prime for all p, this is not the case. The evidence at hand does suggest that a randomly selected Mersenne number is more likely to be prime than an arbitrary randomly selected odd integer of similar size. Nonetheless, prime Mp appear to grow increasingly sparse as p increases, in fact, of the 2,270,720 prime numbers p up to 37,156,667, Mp is prime for only 45 of them.

The lack of any simple test to determine whether a given Mersenne number is prime makes the search for Mersenne primes a difficult task, the Lucas–Lehmer primality test is an efficient primality test that greatly aids this task. The search for the largest known prime has somewhat of a cult following, consequently, a lot of computer power has been expended searching for new Mersenne primes, much of which is now done using distributed computing

Eisenstein prime

In mathematics, an Eisenstein prime is an Eisenstein integer z = a + b ω that is irreducible in the ring-theoretic sense, its only Eisenstein divisors are the units, a + bω itself and its associates. The associates and the conjugate of any Eisenstein prime are prime. It follows that the absolute value squared of every Eisenstein prime is a prime or the square of a natural prime. The first few Eisenstein primes that equal a natural prime 3n −1 are,2,5,11,17,23,29,41,47,53,59,71,83,89,101. Natural primes that are congruent to 0 or 1 modulo 3 are not Eisenstein primes, some non-real Eisenstein primes are 2 + ω,3 + ω,4 + ω,5 + 2ω,6 + ω,7 + ω,7 + 3ω. Up to conjugacy and unit multiples, the primes listed above, as of March 2017, the largest known Eisenstein prime is the seventh largest known prime 10223 ×231172165 +1, discovered by Péter Szabolcs and PrimeGrid. All larger known primes are Mersenne primes, discovered by GIMPS, real Eisenstein primes are congruent to 2 mod 3, and Mersenne primes are congruent to 1 mod 3, thus no Mersenne prime is an Eisenstein prime

Pierpont prime

A Pierpont prime is a prime number of the form 2 u 3 v +1 for some nonnegative integers u and v. That is, they are the prime numbers p for which p −1 is 3-smooth. They are named after the mathematician James Pierpont, who introduced them in the study of regular polygons that can be constructed using conic sections. It is possible to prove that if v =0 and u >0, u must be a power of 2, if v is positive u must be positive, and the Pierpont prime is of the form 6k +1. Empirically, the Pierpont primes do not seem to be rare or sparsely distributed. There are 36 Pierpont primes less than 106,59 less than 109,151 less than 1020, there are few restrictions from algebraic factorisations on the Pierpont primes, so there are no requirements like the Mersenne prime condition that the exponent must be prime. As there are Θ numbers of the form in this range. Andrew M. Gleason made this explicit, conjecturing there are infinitely many Pierpont primes. According to Gleasons conjecture there are Θ Pierpont primes smaller than N, when 2 u >3 v, the primality of 2 u 3 v +1 can be tested by Proths theorem.

As part of the ongoing search for factors of Fermat numbers. The following table gives values of m, k, and n such that k ⋅2 n +1 divides 22 m +1, the left-hand side is a Pierpont prime when k is a power of 3, the right-hand side is a Fermat number. As of 2017, the largest known Pierpont prime is 3 ×210829346 +1, whose primality was discovered by Sai Yik Tang, in the mathematics of paper folding, the Huzita axioms define six of the seven types of fold possible. It has been shown that these folds are sufficient to allow the construction of the points that solve any cubic equation. It follows that they allow any regular polygon of N sides to be formed, as long as N >3 and of the form 2m3nρ and this is the same class of regular polygons as those that can be constructed with a compass and angle-trisector. Regular polygons which can be constructed with compass and straightedge are the special case where n =0 and ρ is a product of distinct Fermat primes, themselves a subset of Pierpont primes. In 1895, James Pierpont studied the same class of regular polygons, Pierpont generalized compass and straightedge constructions in a different way, by adding the ability to draw conic sections whose coefficients come from previously constructed points.

As he showed, the regular N-gons that can be constructed with these operations are the ones such that the totient of N is 3-smooth. Since the totient of a prime is formed by subtracting one from it, Pierpont did not describe the form of the composite numbers with 3-smooth totients. As Gleason showed, these numbers are exactly the ones of the form 2m3nρ given above, the smallest prime that is not a Pierpont prime is 11, the hendecagon is the smallest regular polygon that cannot be constructed with compass and angle trisector

Subset

In mathematics, especially in set theory, a set A is a subset of a set B, or equivalently B is a superset of A, if A is contained inside B, that is, all elements of A are elements of B. The relationship of one set being a subset of another is called inclusion or sometimes containment, the subset relation defines a partial order on sets. The algebra of subsets forms a Boolean algebra in which the relation is called inclusion. For any set S, the inclusion relation ⊆ is an order on the set P of all subsets of S defined by A ≤ B ⟺ A ⊆ B. We may partially order P by reverse set inclusion by defining A ≤ B ⟺ B ⊆ A, when quantified, A ⊆ B is represented as, ∀x. So for example, for authors, it is true of every set A that A ⊂ A. Other authors prefer to use the symbols ⊂ and ⊃ to indicate proper subset and superset and this usage makes ⊆ and ⊂ analogous to the inequality symbols ≤ and <. For example, if x ≤ y x may or may not equal y, but if x < y, x definitely does not equal y, and is less than y. Similarly, using the convention that ⊂ is proper subset, if A ⊆ B, A may or may not equal B, the set A = is a proper subset of B =, thus both expressions A ⊆ B and A ⊊ B are true.

The set D = is a subset of E =, thus D ⊆ E is true, any set is a subset of itself, but not a proper subset. The empty set, denoted by ∅, is a subset of any given set X and it is always a proper subset of any set except itself. These are two examples in both the subset and the whole set are infinite, and the subset has the same cardinality as the whole. The set of numbers is a proper subset of the set of real numbers. In this example, both sets are infinite but the set has a larger cardinality than the former set. Another example in an Euler diagram, Inclusion is the partial order in the sense that every partially ordered set is isomorphic to some collection of sets ordered by inclusion. The ordinal numbers are a simple example—if each ordinal n is identified with the set of all ordinals less than or equal to n, a ≤ b if and only if ⊆. For the power set P of a set S, the partial order is the Cartesian product of k = |S| copies of the partial order on for which 0 <1. This can be illustrated by enumerating S = and associating with each subset T ⊆ S the k-tuple from k of which the ith coordinate is 1 if and only if si is a member of T

Pythagorean prime

A Pythagorean prime is a prime number of the form 4n +1. Pythagorean primes are exactly the odd numbers that are the sum of two squares. For instance, the number 5 is a Pythagorean prime, √5 is the hypotenuse of a triangle with legs 1 and 2. The first few Pythagorean primes are 5,13,17,29,37,41,53,61,73,89,97,101,109,113, by Dirichlets theorem on arithmetic progressions, this sequence is infinite. More strongly, for n, the numbers of Pythagorean and non-Pythagorean primes up to n are approximately equal. However, the number of Pythagorean primes up to n is frequently smaller than the number of non-Pythagorean primes. For example, the values of n up to 600000 for which there are more Pythagorean than non-Pythagorean odd primes are 26861 and 26862. Sum of one odd square and one square is congruent to 1 mod 4. Fermats theorem on sums of two states that the prime numbers that can be represented as sums of two squares are exactly 2 and the odd primes congruent to 1 mod 4. The representation of such number is unique, up to the ordering of the two squares.

Another way to understand this representation as a sum of two squares involves Gaussian integers, the numbers whose real part and imaginary part are both integers. The norm of a Gaussian integer x + yi is the number x2 + y2, the Pythagorean primes occur as norms of Gaussian integers, while other primes do not. Within the Gaussian integers, the Pythagorean primes are not considered to be prime numbers, their squares can be factored in a different way than their integer factorization, as p2 =22 =. The real and imaginary parts of the factors in these factorizations are the leg lengths of the right triangles having the given hypotenuses, in the finite field Z/p with p a Pythagorean prime, the polynomial equation x2 = −1 has two solutions. This may be expressed by saying that −1 is a quadratic residue mod p, in contrast, this equation has no solution in the finite fields Z/p where p is an odd prime but is not Pythagorean. Pythagorean Primes, including 5,13 and 137, sloanes A007350, Where prime race 4n-1 vs. 4n+1 changes leader.

The On-Line Encyclopedia of Integer Sequences

Circular prime

A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its digits will be prime. For example,1193 is a prime, since 1931,9311 and 3119 all are prime. There are no other circular primes up to 1023, a type of prime related to the circular primes are the permutable primes, which are a subset of the circular primes. Where Rn is a prime in base 12 with n digits. There are no other circular primes in base 12 up to 128, in base 2, only Mersenne primes can be circular primes, since any 0 permuted to the ones place results in an even number. Circular prime at The Prime Glossary Circular prime at World of Numbers A068652 a related sequence Circular, Permutable and Deletable Primes

Motzkin number

In mathematics, a Motzkin number for a given number n is the number of different ways of drawing non-intersecting chords between n points on a circle. The Motzkin numbers are named after Theodore Motzkin, and have diverse applications in geometry, combinatorics. The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle, the following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle. Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers, a Motzkin prime is a Motzkin number that is prime. Guibert, Pergola & Pinzani showed that vexillary involutions are enumerated by Motzkin numbers

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a number is called a composite number. For example,5 is prime because 1 and 5 are its only positive integer factors, the property of being prime is called primality. A simple but slow method of verifying the primality of a number n is known as trial division. It consists of testing whether n is a multiple of any integer between 2 and n, algorithms much more efficient than trial division have been devised to test the primality of large numbers. Particularly fast methods are available for numbers of forms, such as Mersenne numbers. As of January 2016, the largest known prime number has 22,338,618 decimal digits, there are infinitely many primes, as demonstrated by Euclid around 300 BC. There is no simple formula that separates prime numbers from composite numbers. However, the distribution of primes, that is to say, many questions regarding prime numbers remain open, such as Goldbachs conjecture, and the twin prime conjecture.

Such questions spurred the development of branches of number theory. Prime numbers give rise to various generalizations in other domains, mainly algebra, such as prime elements. A natural number is called a number if it has exactly two positive divisors,1 and the number itself. Natural numbers greater than 1 that are not prime are called composite, among the numbers 1 to 6, the numbers 2,3, and 5 are the prime numbers, while 1,4, and 6 are not prime. 1 is excluded as a number, for reasons explained below. 2 is a number, since the only natural numbers dividing it are 1 and 2. Next,3 is prime, too,1 and 3 do divide 3 without remainder, however,4 is composite, since 2 is another number dividing 4 without remainder,4 =2 ·2. 5 is again prime, none of the numbers 2,3, next,6 is divisible by 2 or 3, since 6 =2 ·3. The image at the right illustrates that 12 is not prime,12 =3 ·4, no even number greater than 2 is prime because by definition, any such number n has at least three distinct divisors, namely 1,2, and n

Gaussian integer

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with addition and multiplication of complex numbers, form an integral domain. This integral domain is a case of a commutative ring of quadratic integers. It does not have an ordering that respects arithmetic. Formally, the Gaussian integers are the set Z =, where i 2 = −1, note that when they are considered within the complex plane the Gaussian integers may be seen to constitute the 2-dimensional integer lattice. The norm of a Gaussian integer is the square of its value as a complex number. It is the natural number defined as N = a 2 + b 2 = ¯ =, the norm is multiplicative, since the absolute value of complex numbers is multiplicative, i. e. one has N = N N. The latter can be verified by a straightforward check, the units of Z are precisely those elements with norm 1, i. e. the set. The Gaussian integers form a principal ideal domain with units, for x ∈ Z, the four numbers ±x, ±ix are called the associates of x.

As for every principal ideal domain, Z is a unique factorization domain and it follows that a Gaussian integer is prime if and only if it is irreducible. The prime elements of Z are known as Gaussian primes, an associate of a Gaussian prime is a Gaussian prime. The Gaussian primes are symmetric about the real and imaginary axes, the positive integer Gaussian primes are the prime numbers that are congruent to 3 modulo 4. One should not refer to only these numbers as the Gaussian primes, which refers to all the Gaussian primes, many of which do not lie in Z. In other words, a Gaussian integer is a Gaussian prime if and only if either its norm is a prime number, for example,5 = · and 13 = ·. If p =2, we have 2 = = i2, the ring of Gaussian integers is the integral closure of Z in the field of Gaussian rationals Q consisting of the complex numbers whose real and imaginary part are both rational. It is easy to see graphically that every number is no farther than a distance of 22 from some Gaussian integer.

Put another way, every number has a maximal distance of 22 N units to some multiple of z, where z is any Gaussian integer, this turns Z into a Euclidean domain. The ring of Gaussian integers was introduced by Carl Friedrich Gauss in his monograph on quartic reciprocity