Misplaced Pages

#822177

105-475: A prime number (or a prime ) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number . For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1 , involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of

210-416: A {\displaystyle a} and b {\displaystyle b} take infinitely many prime values. Stronger forms of the theorem state that the sum of the reciprocals of these prime values diverges, and that different linear polynomials with the same b {\displaystyle b} have approximately the same proportions of primes. Although conjectures have been formulated about

315-458: A {\displaystyle a} or p {\displaystyle p} divides b {\displaystyle b} (or both). Conversely, if a number p {\displaystyle p} has the property that when it divides a product it always divides at least one factor of the product, then p {\displaystyle p} must be prime. There are infinitely many prime numbers. Another way of saying this

420-680: A and b with b ≠ 0 there are natural numbers q and r such that The number q is called the quotient and r is called the remainder of the division of a by  b . The numbers q and r are uniquely determined by a and  b . This Euclidean division is key to the several other properties ( divisibility ), algorithms (such as the Euclidean algorithm ), and ideas in number theory. The addition (+) and multiplication (×) operations on natural numbers as defined above have several algebraic properties: Two important generalizations of natural numbers arise from

525-425: A + c = b . This order is compatible with the arithmetical operations in the following sense: if a , b and c are natural numbers and a ≤ b , then a + c ≤ b + c and ac ≤ bc . An important property of the natural numbers is that they are well-ordered : every non-empty set of natural numbers has a least element. The rank among well-ordered sets is expressed by an ordinal number ; for

630-466: A + 1 = S ( a ) and a × 1 = a . Furthermore, ( N ∗ , + ) {\displaystyle (\mathbb {N^{*}} ,+)} has no identity element. In this section, juxtaposed variables such as ab indicate the product a × b , and the standard order of operations is assumed. A total order on the natural numbers is defined by letting a ≤ b if and only if there exists another natural number c where

735-401: A × ( b + c ) = ( a × b ) + ( a × c ) . These properties of addition and multiplication make the natural numbers an instance of a commutative semiring . Semirings are an algebraic generalization of the natural numbers where multiplication is not necessarily commutative. The lack of additive inverses, which is equivalent to the fact that N {\displaystyle \mathbb {N} }

840-404: A × 0 = 0 and a × S( b ) = ( a × b ) + a . This turns ( N ∗ , × ) {\displaystyle (\mathbb {N} ^{*},\times )} into a free commutative monoid with identity element 1; a generator set for this monoid is the set of prime numbers . Addition and multiplication are compatible, which is expressed in the distribution law :

945-474: A digit when it would have been the last symbol in the number. The Olmec and Maya civilizations used 0 as a separate number as early as the 1st century BCE , but this usage did not spread beyond Mesoamerica . The use of a numeral 0 in modern times originated with the Indian mathematician Brahmagupta in 628 CE. However, 0 had been used as a number in the medieval computus (the calculation of

1050-606: A matter of definition. In 1727, Bernard Le Bovier de Fontenelle wrote that his notions of distance and element led to defining the natural numbers as including or excluding 0. In 1889, Giuseppe Peano used N for the positive integers and started at 1, but he later changed to using N 0 and N 1 . Historically, most definitions have excluded 0, but many mathematicians such as George A. Wentworth , Bertrand Russell , Nicolas Bourbaki , Paul Halmos , Stephen Cole Kleene , and John Horton Conway have preferred to include 0. Mathematicians have noted tendencies in which definition

1155-451: A natural number n {\displaystyle n} are the natural numbers that divide n {\displaystyle n} evenly. Every natural number has both 1 and itself as a divisor. If it has any other divisor, it cannot be prime. This leads to an equivalent definition of prime numbers: they are the numbers with exactly two positive divisors . Those two are 1 and the number itself. As 1 has only one divisor, itself, it

SECTION 10

#1732765440823

1260-460: A natural number as the class of all sets that are in one-to-one correspondence with a particular set. However, this definition turned out to lead to paradoxes, including Russell's paradox . To avoid such paradoxes, the formalism was modified so that a natural number is defined as a particular set, and any set that can be put into one-to-one correspondence with that set is said to have that number of elements. In 1881, Charles Sanders Peirce provided

1365-461: A natural number is to use one's fingers, as in finger counting . Putting down a tally mark for each object is another primitive method. Later, a set of objects could be tested for equality, excess or shortage—by striking out a mark and removing an object from the set. The first major advance in abstraction was the use of numerals to represent numbers. This allowed systems to be developed for recording large numbers. The ancient Egyptians developed

1470-526: A need to improve upon the logical rigor in the foundations of mathematics . In the 1860s, Hermann Grassmann suggested a recursive definition for natural numbers, thus stating they were not really natural—but a consequence of definitions. Later, two classes of such formal definitions emerged, using set theory and Peano's axioms respectively. Later still, they were shown to be equivalent in most practical applications. Set-theoretical definitions of natural numbers were initiated by Frege . He initially defined

1575-482: A number like any other. Independent studies on numbers also occurred at around the same time in India , China, and Mesoamerica . Nicolas Chuquet used the term progression naturelle (natural progression) in 1484. The earliest known use of "natural number" as a complete English phrase is in 1763. The 1771 Encyclopaedia Britannica defines natural numbers in the logarithm article. Starting at 0 or 1 has long been

1680-507: A powerful system of numerals with distinct hieroglyphs for 1, 10, and all powers of 10 up to over 1 million. A stone carving from Karnak , dating back from around 1500 BCE and now at the Louvre in Paris, depicts 276 as 2 hundreds, 7 tens, and 6 ones; and similarly for the number 4,622. The Babylonians had a place-value system based essentially on

1785-466: A prime p {\displaystyle p} for which this sum is bigger than x {\displaystyle x} . This shows that there are infinitely many primes, because if there were finitely many primes the sum would reach its maximum value at the biggest prime rather than growing past every x {\displaystyle x} . The growth rate of this sum is described more precisely by Mertens' second theorem . For comparison,

1890-423: A prime factorization with one or more prime factors. N {\displaystyle N} is evenly divisible by each of these factors, but N {\displaystyle N} has a remainder of one when divided by any of the prime numbers in the given list, so none of the prime factors of N {\displaystyle N} can be in the given list. Because there is no finite list of all

1995-428: A prime occurs multiple times, exponentiation can be used to group together multiple copies of the same prime number: for example, in the second way of writing the product above, 5 2 {\displaystyle 5^{2}} denotes the square or second power of 5. {\displaystyle 5.} The central importance of prime numbers to number theory and mathematics in general stems from

2100-509: A set (because of Russell's paradox ). The standard solution is to define a particular set with n elements that will be called the natural number n . The following definition was first published by John von Neumann , although Levy attributes the idea to unpublished work of Zermelo in 1916. As this definition extends to infinite set as a definition of ordinal number , the sets considered below are sometimes called von Neumann ordinals . The definition proceeds as follows: It follows that

2205-574: A subscript (or superscript) "0" is added in the latter case: This section uses the convention N = N 0 = N ∗ ∪ { 0 } {\displaystyle \mathbb {N} =\mathbb {N} _{0}=\mathbb {N} ^{*}\cup \{0\}} . Given the set N {\displaystyle \mathbb {N} } of natural numbers and the successor function S : N → N {\displaystyle S\colon \mathbb {N} \to \mathbb {N} } sending each natural number to

SECTION 20

#1732765440823

2310-506: A sum of three primes. Chen's theorem says that every sufficiently large even number can be expressed as the sum of a prime and a semiprime (the product of two primes). Also, any even integer greater than 10 can be written as the sum of six primes. The branch of number theory studying such questions is called additive number theory . Another type of problem concerns prime gaps , the differences between consecutive primes. The existence of arbitrarily large prime gaps can be seen by noting that

2415-483: A theorem of Wright . These assert that there are real constants A > 1 {\displaystyle A>1} and μ {\displaystyle \mu } such that are prime for any natural number n {\displaystyle n} in the first formula, and any number of exponents in the second formula. Here ⌊ ⋅ ⌋ {\displaystyle \lfloor {}\cdot {}\rfloor } represents

2520-490: Is Goldbach's conjecture , which asserts that every even integer n {\displaystyle n} greater than 2 can be written as a sum of two primes. As of 2014, this conjecture has been verified for all numbers up to n = 4 ⋅ 10 18 . {\displaystyle n=4\cdot 10^{18}.} Weaker statements than this have been proven; for example, Vinogradov's theorem says that every sufficiently large odd integer can be written as

2625-513: Is consistent (as it is usually guessed), then Peano arithmetic is consistent. In other words, if a contradiction could be proved in Peano arithmetic, then set theory would be contradictory, and every theorem of set theory would be both true and wrong. The five Peano axioms are the following: These are not the original axioms published by Peano, but are named in his honor. Some forms of the Peano axioms have 1 in place of 0. In ordinary arithmetic,

2730-505: Is a free monoid on one generator. This commutative monoid satisfies the cancellation property , so it can be embedded in a group . The smallest group containing the natural numbers is the integers . If 1 is defined as S (0) , then b + 1 = b + S (0) = S ( b + 0) = S ( b ) . That is, b + 1 is simply the successor of b . Analogously, given that addition has been defined, a multiplication operator × {\displaystyle \times } can be defined via

2835-478: Is a semiprime or 2-almost prime (the factors need not be distinct, hence squares of primes are included). A composite number with three distinct prime factors is a sphenic number . In some applications, it is necessary to differentiate between composite numbers with an odd number of distinct prime factors and those with an even number of distinct prime factors. For the latter (where μ is the Möbius function and x

2940-478: Is a subset of m . In other words, the set inclusion defines the usual total order on the natural numbers. This order is a well-order . Composite number The composite numbers up to 150 are: Every composite number can be written as the product of two or more (not necessarily distinct) primes. For example, the composite number 299 can be written as 13 × 23, and the composite number 360 can be written as 2 × 3 × 5; furthermore, this representation

3045-564: Is a multiple of any integer between 2 and n {\displaystyle {\sqrt {n}}} . Faster algorithms include the Miller–Rabin primality test , which is fast but has a small chance of error, and the AKS primality test , which always produces the correct answer in polynomial time but is too slow to be practical. Particularly fast methods are available for numbers of special forms, such as Mersenne numbers . As of October 2024

3150-509: Is based on Wilson's theorem and generates the number 2 many times and all other primes exactly once. There is also a set of Diophantine equations in nine variables and one parameter with the following property: the parameter is prime if and only if the resulting system of equations has a solution over the natural numbers. This can be used to obtain a single formula with the property that all its positive values are prime. Other examples of prime-generating formulas come from Mills' theorem and

3255-552: Is based on set theory . It defines the natural numbers as specific sets . More precisely, each natural number n is defined as an explicitly defined set, whose elements allow counting the elements of other sets, in the sense that the sentence "a set S has n elements" means that there exists a one to one correspondence between the two sets n and S . The sets used to define natural numbers satisfy Peano axioms. It follows that every theorem that can be stated and proved in Peano arithmetic can also be proved in set theory. However,

Prime number - Misplaced Pages Continue

3360-584: Is based on an axiomatization of the properties of ordinal numbers : each natural number has a successor and every non-zero natural number has a unique predecessor. Peano arithmetic is equiconsistent with several weak systems of set theory . One such system is ZFC with the axiom of infinity replaced by its negation. Theorems that can be proved in ZFC but cannot be proved using the Peano Axioms include Goodstein's theorem . The set of all natural numbers

3465-586: Is called squarefree . (All prime numbers and 1 are squarefree.) For example, 72 = 2 × 3 , all the prime factors are repeated, so 72 is a powerful number. 42 = 2 × 3 × 7, none of the prime factors are repeated, so 42 is squarefree. Another way to classify composite numbers is by counting the number of divisors. All composite numbers have at least three divisors. In the case of squares of primes, those divisors are { 1 , p , p 2 } {\displaystyle \{1,p,p^{2}\}} . A number n that has more divisors than any x < n

3570-422: Is called a prime number (or a prime ) if it is greater than 1 and cannot be written as the product of two smaller natural numbers. The numbers greater than 1 that are not prime are called composite numbers . In other words, n {\displaystyle n} is prime if n {\displaystyle n} items cannot be divided up into smaller equal-size groups of more than one item, or if it

3675-401: Is denoted as and means that the ratio of π ( n ) {\displaystyle \pi (n)} to the right-hand fraction approaches 1 as n {\displaystyle n} grows to infinity. This implies that the likelihood that a randomly chosen number less than n {\displaystyle n} is prime is (approximately) inversely proportional to

3780-410: Is given by the offset logarithmic integral An arithmetic progression is a finite or infinite sequence of numbers such that consecutive numbers in the sequence all have the same difference. This difference is called the modulus of the progression. For example, is an infinite arithmetic progression with modulus 9. In an arithmetic progression, all the numbers have the same remainder when divided by

3885-446: Is half the total of prime factors), while for the former However, for prime numbers, the function also returns −1 and μ ( 1 ) = 1 {\displaystyle \mu (1)=1} . For a number n with one or more repeated prime factors, If all the prime factors of a number are repeated it is called a powerful number (All perfect powers are powerful numbers). If none of its prime factors are repeated, it

3990-426: Is incomplete. The key idea is to multiply together the primes in any given list and add 1. {\displaystyle 1.} If the list consists of the primes p 1 , p 2 , … , p n , {\displaystyle p_{1},p_{2},\ldots ,p_{n},} this gives the number By the fundamental theorem, N {\displaystyle N} has

4095-410: Is not closed under subtraction (that is, subtracting one natural from another does not always result in another natural), means that N {\displaystyle \mathbb {N} } is not a ring ; instead it is a semiring (also known as a rig ). If the natural numbers are taken as "excluding 0", and "starting at 1", the definitions of + and × are as above, except that they begin with

4200-462: Is not possible to arrange n {\displaystyle n} dots into a rectangular grid that is more than one dot wide and more than one dot high. For example, among the numbers 1 through 6, the numbers 2, 3, and 5 are the prime numbers, as there are no other numbers that divide them evenly (without a remainder). 1 is not prime, as it is specifically excluded in the definition. 4 = 2 × 2 and 6 = 2 × 3 are both composite. The divisors of

4305-410: Is not prime by this definition. Yet another way to express the same thing is that a number n {\displaystyle n} is prime if it is greater than one and if none of the numbers 2 , 3 , … , n − 1 {\displaystyle 2,3,\dots ,n-1} divides n {\displaystyle n} evenly. The first 25 prime numbers (all

Prime number - Misplaced Pages Continue

4410-498: Is practicably applicable. Methods that are restricted to specific number forms include Pépin's test for Fermat numbers (1877), Proth's theorem (c. 1878), the Lucas–Lehmer primality test (originated 1856), and the generalized Lucas primality test . Since 1951 all the largest known primes have been found using these tests on computers . The search for ever larger primes has generated interest outside mathematical circles, through

4515-433: Is sometimes denoted by P {\displaystyle \mathbf {P} } (a boldface capital P) or by P {\displaystyle \mathbb {P} } (a blackboard bold capital P). The Rhind Mathematical Papyrus , from around 1550 BC, has Egyptian fraction expansions of different forms for prime and composite numbers. However, the earliest surviving records of the study of prime numbers come from

4620-429: Is standardly denoted N or N . {\displaystyle \mathbb {N} .} Older texts have occasionally employed J as the symbol for this set. Since natural numbers may contain 0 or not, it may be important to know which version is referred to. This is often specified by the context, but may also be done by using a subscript or a superscript in the notation, such as: Alternatively, since

4725-512: Is that the sequence of prime numbers never ends. This statement is referred to as Euclid's theorem in honor of the ancient Greek mathematician Euclid , since the first known proof for this statement is attributed to him. Many more proofs of the infinitude of primes are known, including an analytical proof by Euler , Goldbach's proof based on Fermat numbers , Furstenberg's proof using general topology , and Kummer's elegant proof. Euclid's proof shows that every finite list of primes

4830-456: Is the third largest city in the country", which are called ordinal numbers . Natural numbers are also used as labels, like jersey numbers on a sports team, where they serve as nominal numbers and do not have mathematical properties. The natural numbers form a set , commonly symbolized as a bold N or blackboard bold ⁠ N {\displaystyle \mathbb {N} } ⁠ . Many other number sets are built from

4935-542: Is the limiting probability that two random numbers selected uniformly from a large range are relatively prime (have no factors in common). The distribution of primes in the large, such as the question how many primes are smaller than a given, large threshold, is described by the prime number theorem , but no efficient formula for the n {\displaystyle n} -th prime is known. Dirichlet's theorem on arithmetic progressions , in its basic form, asserts that linear polynomials with relatively prime integers

5040-700: Is the sum of two primes, in a 1742 letter to Euler. Euler proved Alhazen's conjecture (now the Euclid–Euler theorem ) that all even perfect numbers can be constructed from Mersenne primes. He introduced methods from mathematical analysis to this area in his proofs of the infinitude of the primes and the divergence of the sum of the reciprocals of the primes 1 2 + 1 3 + 1 5 + 1 7 + 1 11 + ⋯ {\displaystyle {\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots } . At

5145-410: Is unique up to the order of the factors. This fact is called the fundamental theorem of arithmetic . There are several known primality tests that can determine whether a number is prime or composite which do not necessarily reveal the factorization of a composite input. One way to classify composite numbers is by counting the number of prime factors. A composite number with two prime factors

5250-422: Is used, such as algebra texts including 0, number theory and analysis texts excluding 0, logic and set theory texts including 0, dictionaries excluding 0, school books (through high-school level) excluding 0, and upper-division college-level books including 0. There are exceptions to each of these tendencies and as of 2023 no formal survey has been conducted. Arguments raised include division by zero and

5355-694: The Great Internet Mersenne Prime Search and other distributed computing projects. The idea that prime numbers had few applications outside of pure mathematics was shattered in the 1970s when public-key cryptography and the RSA cryptosystem were invented, using prime numbers as their basis. The increased practical importance of computerized primality testing and factorization led to the development of improved methods capable of handling large numbers of unrestricted form. The mathematical theory of prime numbers also moved forward with

SECTION 50

#1732765440823

5460-544: The Green–Tao theorem (2004) that there are arbitrarily long arithmetic progressions of prime numbers, and Yitang Zhang 's 2013 proof that there exist infinitely many prime gaps of bounded size. Most early Greeks did not even consider 1 to be a number, so they could not consider its primality. A few scholars in the Greek and later Roman tradition, including Nicomachus , Iamblichus , Boethius , and Cassiodorus , also considered

5565-519: The Meissel–Lehmer algorithm can compute exact values of π ( n ) {\displaystyle \pi (n)} faster than it would be possible to list each prime up to n {\displaystyle n} . The prime number theorem states that π ( n ) {\displaystyle \pi (n)} is asymptotic to n / log ⁡ n {\displaystyle n/\log n} , which

5670-598: The ancient Greek mathematicians , who called them prōtos arithmòs ( πρῶτος ἀριθμὸς ). Euclid 's Elements (c. 300 BC) proves the infinitude of primes and the fundamental theorem of arithmetic , and shows how to construct a perfect number from a Mersenne prime . Another Greek invention, the Sieve of Eratosthenes , is still used to construct lists of primes. Around 1000 AD, the Islamic mathematician Ibn al-Haytham (Alhazen) found Wilson's theorem , characterizing

5775-557: The floor function , the largest integer less than or equal to the number in question. However, these are not useful for generating primes, as the primes must be generated first in order to compute the values of A {\displaystyle A} or μ . {\displaystyle \mu .} Many conjectures revolving about primes have been posed. Often having an elementary formulation, many of these conjectures have withstood proof for decades: all four of Landau's problems from 1912 are still unsolved. One of them

5880-477: The fundamental theorem of arithmetic . This theorem states that every integer larger than 1 can be written as a product of one or more primes. More strongly, this product is unique in the sense that any two prime factorizations of the same number will have the same numbers of copies of the same primes, although their ordering may differ. So, although there are many different ways of finding a factorization using an integer factorization algorithm, they all must produce

5985-431: The fundamental theorem of arithmetic : every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order. The property of being prime is called primality . A simple but slow method of checking the primality of a given number n {\displaystyle n} , called trial division , tests whether n {\displaystyle n}

6090-422: The largest known prime number is a Mersenne prime with 41,024,320 decimal digits . There are infinitely many primes, as demonstrated by Euclid around 300 BC. No known simple formula separates prime numbers from composite numbers. However, the distribution of primes within the natural numbers in the large can be statistically modelled. The first result in that direction is the prime number theorem , proven at

6195-426: The natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers 0, 1, 2, 3, ... , while others start with 1, defining them as the positive integers 1, 2, 3, ... . Some authors acknowledge both definitions whenever convenient. Sometimes, the whole numbers are the natural numbers plus zero. In other cases,

6300-433: The sieve of Eratosthenes would not work correctly if it handled 1 as a prime, because it would eliminate all multiples of 1 (that is, all other numbers) and output only the single number 1. Some other more technical properties of prime numbers also do not hold for the number 1: for instance, the formulas for Euler's totient function or for the sum of divisors function are different for prime numbers than they are for 1. By

6405-453: The twin prime conjecture , that there exist infinitely many twin primes. The prime-counting function π ( n ) {\displaystyle \pi (n)} is defined as the number of primes not greater than n {\displaystyle n} . For example, π ( 11 ) = 5 {\displaystyle \pi (11)=5} , since there are five primes less than or equal to 11. Methods such as

SECTION 60

#1732765440823

6510-447: The whole numbers refer to all of the integers , including negative integers. The counting numbers are another term for the natural numbers, particularly in primary school education, and are ambiguous as well although typically start at 1. The natural numbers are used for counting things, like "there are six coins on the table", in which case they are called cardinal numbers . They are also used to put things in order, like "this

6615-468: The closely related Riemann hypothesis remains unproven, Riemann's outline was completed in 1896 by Hadamard and de la Vallée Poussin , and the result is now known as the prime number theorem . Another important 19th century result was Dirichlet's theorem on arithmetic progressions , that certain arithmetic progressions contain infinitely many primes. Many mathematicians have worked on primality tests for numbers larger than those where trial division

6720-574: The date of Easter), beginning with Dionysius Exiguus in 525 CE, without being denoted by a numeral. Standard Roman numerals do not have a symbol for 0; instead, nulla (or the genitive form nullae ) from nullus , the Latin word for "none", was employed to denote a 0 value. The first systematic study of numbers as abstractions is usually credited to the Greek philosophers Pythagoras and Archimedes . Some Greek mathematicians treated

6825-419: The deep algebraic number theory of Heegner numbers and the class number problem . The Hardy–Littlewood conjecture F predicts the density of primes among the values of quadratic polynomials with integer coefficients in terms of the logarithmic integral and the polynomial coefficients. No quadratic polynomial has been proven to take infinitely many prime values. Natural number In mathematics ,

6930-471: The development of various branches of number theory, focusing on analytic or algebraic aspects of numbers. Primes are used in several routines in information technology , such as public-key cryptography , which relies on the difficulty of factoring large numbers into their prime factors. In abstract algebra , objects that behave in a generalized way like prime numbers include prime elements and prime ideals . A natural number (1, 2, 3, 4, 5, 6, etc.)

7035-427: The differences among more than two prime numbers. Their infinitude and density are the subject of the first Hardy–Littlewood conjecture , which can be motivated by the heuristic that the prime numbers behave similarly to a random sequence of numbers with density given by the prime number theorem. Analytic number theory studies number theory through the lens of continuous functions , limits , infinite series , and

7140-460: The early 20th century, mathematicians began to agree that 1 should not be listed as prime, but rather in its own special category as a " unit ". Writing a number as a product of prime numbers is called a prime factorization of the number. For example: The terms in the product are called prime factors . The same prime factor may occur more than once; this example has two copies of the prime factor 5. {\displaystyle 5.} When

7245-448: The early 20th century, mathematicians started to agree that 1 should not be classified as a prime number. If 1 were to be considered a prime, many statements involving primes would need to be awkwardly reworded. For example, the fundamental theorem of arithmetic would need to be rephrased in terms of factorizations into primes greater than 1, because every number would have multiple factorizations with any number of copies of 1. Similarly,

7350-509: The end of the 19th century, which says that the probability of a randomly chosen large number being prime is inversely proportional to its number of digits, that is, to its logarithm . Several historical questions regarding prime numbers are still unsolved. These include Goldbach's conjecture , that every even integer greater than 2 can be expressed as the sum of two primes, and the twin prime conjecture, that there are infinitely many pairs of primes that differ by two. Such questions spurred

7455-409: The first axiomatization of natural-number arithmetic. In 1888, Richard Dedekind proposed another axiomatization of natural-number arithmetic, and in 1889, Peano published a simplified version of Dedekind's axioms in his book The principles of arithmetic presented by a new method ( Latin : Arithmetices principia, nova methodo exposita ). This approach is now called Peano arithmetic . It

7560-668: The first prime gap of length 8 is between the primes 89 and 97, much smaller than 8 ! = 40320. {\displaystyle 8!=40320.} It is conjectured that there are infinitely many twin primes , pairs of primes with difference 2; this is the twin prime conjecture . Polignac's conjecture states more generally that for every positive integer k , {\displaystyle k,} there are infinitely many pairs of consecutive primes that differ by 2 k . {\displaystyle 2k.} Andrica's conjecture , Brocard's conjecture , Legendre's conjecture , and Oppermann's conjecture all suggest that

7665-467: The first prime number. In the mid-18th century, Christian Goldbach listed 1 as prime in his correspondence with Leonhard Euler ; however, Euler himself did not consider 1 to be prime. Many 19th century mathematicians still considered 1 to be prime, and Derrick Norman Lehmer included 1 in his list of primes less than ten million published in 1914. Lists of primes that included 1 continued to be published as recently as 1956. However, around this time, by

7770-654: The largest gaps between primes from 1 {\displaystyle 1} to n {\displaystyle n} should be at most approximately n , {\displaystyle {\sqrt {n}},} a result that is known to follow from the Riemann hypothesis, while the much stronger Cramér conjecture sets the largest gap size at O ( ( log ⁡ n ) 2 ) . {\displaystyle O((\log n)^{2}).} Prime gaps can be generalized to prime k {\displaystyle k} -tuples , patterns in

7875-533: The modulus; in this example, the remainder is 3. Because both the modulus 9 and the remainder 3 are multiples of 3, so is every element in the sequence. Therefore, this progression contains only one prime number, 3 itself. In general, the infinite progression can have more than one prime only when its remainder a {\displaystyle a} and modulus q {\displaystyle q} are relatively prime. If they are relatively prime, Dirichlet's theorem on arithmetic progressions asserts that

7980-450: The natural numbers are defined iteratively as follows: It can be checked that the natural numbers satisfy the Peano axioms . With this definition, given a natural number n , the sentence "a set S has n elements" can be formally defined as "there exists a bijection from n to S ." This formalizes the operation of counting the elements of S . Also, n ≤ m if and only if n

8085-403: The natural numbers naturally form a subset of the integers (often denoted Z {\displaystyle \mathbb {Z} } ), they may be referred to as the positive, or the non-negative integers, respectively. To be unambiguous about whether 0 is included or not, sometimes a superscript " ∗ {\displaystyle *} " or "+" is added in the former case, and

8190-435: The natural numbers, this is denoted as ω (omega). In this section, juxtaposed variables such as ab indicate the product a × b , and the standard order of operations is assumed. While it is in general not possible to divide one natural number by another and get a natural number as result, the procedure of division with remainder or Euclidean division is available as a substitute: for any two natural numbers

8295-649: The natural numbers. For example, the integers are made by adding 0 and negative numbers. The rational numbers add fractions, and the real numbers add infinite decimals. Complex numbers add the square root of −1 . This chain of extensions canonically embeds the natural numbers in the other number systems. Natural numbers are studied in different areas of math. Number theory looks at things like how numbers divide evenly ( divisibility ), or how prime numbers are spread out. Combinatorics studies counting and arranging numbered objects, such as partitions and enumerations . The most primitive method of representing

8400-439: The next one, one can define addition of natural numbers recursively by setting a + 0 = a and a + S ( b ) = S ( a + b ) for all a , b . Thus, a + 1 = a + S(0) = S( a +0) = S( a ) , a + 2 = a + S(1) = S( a +1) = S(S( a )) , and so on. The algebraic structure ( N , + ) {\displaystyle (\mathbb {N} ,+)} is a commutative monoid with identity element  0. It

8505-492: The number of digits in n {\displaystyle n} . It also implies that the n {\displaystyle n} th prime number is proportional to n log ⁡ n {\displaystyle n\log n} and therefore that the average size of a prime gap is proportional to log ⁡ n {\displaystyle \log n} . A more accurate estimate for π ( n ) {\displaystyle \pi (n)}

8610-413: The number 1 differently than larger numbers, sometimes even not as a number at all. Euclid , for example, defined a unit first and then a number as a multitude of units, thus by his definition, a unit is not a number and there are no unique numbers (e.g., any two units from indefinitely many units is a 2). However, in the definition of perfect number which comes shortly afterward, Euclid treats 1 as

8715-490: The numerals for 1 and 10, using base sixty, so that the symbol for sixty was the same as the symbol for one—its value being determined from context. A much later advance was the development of the idea that  0 can be considered as a number, with its own numeral. The use of a 0 digit in place-value notation (within other numbers) dates back as early as 700 BCE by the Babylonians, who omitted such

8820-599: The ordinary natural numbers via the ultrapower construction . Other generalizations are discussed in Number § Extensions of the concept . Georges Reeb used to claim provocatively that "The naïve integers don't fill up N {\displaystyle \mathbb {N} } ". There are two standard methods for formally defining natural numbers. The first one, named for Giuseppe Peano , consists of an autonomous axiomatic theory called Peano arithmetic , based on few axioms called Peano axioms . The second definition

8925-601: The primality of the Fermat numbers 2 2 n + 1 {\displaystyle 2^{2^{n}}+1} , and Marin Mersenne studied the Mersenne primes , prime numbers of the form 2 p − 1 {\displaystyle 2^{p}-1} with p {\displaystyle p} itself a prime. Christian Goldbach formulated Goldbach's conjecture , that every even number

9030-403: The prime numbers as the numbers n {\displaystyle n} that evenly divide ( n − 1 ) ! + 1 {\displaystyle (n-1)!+1} . He also conjectured that all even perfect numbers come from Euclid's construction using Mersenne primes, but was unable to prove it. Another Islamic mathematician, Ibn al-Banna' al-Marrakushi , observed that

9135-671: The prime numbers less than 100) are: No even number n {\displaystyle n} greater than 2 is prime because any such number can be expressed as the product 2 × n / 2 {\displaystyle 2\times n/2} . Therefore, every prime number other than 2 is an odd number , and is called an odd prime . Similarly, when written in the usual decimal system, all prime numbers larger than 5 end in 1, 3, 7, or 9. The numbers that end with other digits are all composite: decimal numbers that end in 0, 2, 4, 6, or 8 are even, and decimal numbers that end in 0 or 5 are divisible by 5. The set of all primes

9240-540: The prime numbers to be a subdivision of the odd numbers, so they did not consider 2 to be prime either. However, Euclid and a majority of the other Greek mathematicians considered 2 as prime. The medieval Islamic mathematicians largely followed the Greeks in viewing 1 as not being a number. By the Middle Ages and Renaissance, mathematicians began treating 1 as a number, and by the 17th century some of them included it as

9345-491: The primes, there must be infinitely many primes. The numbers formed by adding one to the products of the smallest primes are called Euclid numbers . The first five of them are prime, but the sixth, is a composite number. There is no known efficient formula for primes. For example, there is no non-constant polynomial , even in several variables, that takes only prime values. However, there are numerous expressions that do encode all primes, or only primes. One possible formula

9450-441: The progression contains infinitely many primes. The Green–Tao theorem shows that there are arbitrarily long finite arithmetic progressions consisting only of primes. Euler noted that the function yields prime numbers for 1 ≤ n ≤ 40 {\displaystyle 1\leq n\leq 40} , although composite numbers appear among its later values. The search for an explanation for this phenomenon led to

9555-411: The proportions of primes in higher-degree polynomials, they remain unproven, and it is unknown whether there exists a quadratic polynomial that (for integer arguments) is prime infinitely often. Euler's proof that there are infinitely many primes considers the sums of reciprocals of primes, Euler showed that, for any arbitrary real number x {\displaystyle x} , there exists

9660-518: The related mathematics of the infinite and infinitesimal . This area of study began with Leonhard Euler and his first major result, the solution to the Basel problem . The problem asked for the value of the infinite sum 1 + 1 4 + 1 9 + 1 16 + … , {\displaystyle 1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,} which today can be recognized as

9765-479: The same natural number, the number of elements of the set. This number can also be used to describe the position of an element in a larger finite, or an infinite, sequence . A countable non-standard model of arithmetic satisfying the Peano Arithmetic (that is, the first-order Peano axioms) was developed by Skolem in 1933. The hypernatural numbers are an uncountable model that can be constructed from

9870-545: The same result. Primes can thus be considered the "basic building blocks" of the natural numbers. Some proofs of the uniqueness of prime factorizations are based on Euclid's lemma : If p {\displaystyle p} is a prime number and p {\displaystyle p} divides a product a b {\displaystyle ab} of integers a {\displaystyle a} and b , {\displaystyle b,} then p {\displaystyle p} divides

9975-417: The sequence n ! + 2 , n ! + 3 , … , n ! + n {\displaystyle n!+2,n!+3,\dots ,n!+n} consists of n − 1 {\displaystyle n-1} composite numbers, for any natural number n . {\displaystyle n.} However, large prime gaps occur much earlier than this argument shows. For example,

10080-481: The sieve of Eratosthenes can be sped up by considering only the prime divisors up to the square root of the upper limit. Fibonacci took the innovations from Islamic mathematics to Europe. His book Liber Abaci (1202) was the first to describe trial division for testing primality, again using divisors only up to the square root. In 1640 Pierre de Fermat stated (without proof) Fermat's little theorem (later proved by Leibniz and Euler ). Fermat also investigated

10185-399: The size of the empty set . Computer languages often start from zero when enumerating items like loop counters and string- or array-elements . Including 0 began to rise in popularity in the 1960s. The ISO 31-11 standard included 0 in the natural numbers in its first edition in 1978 and this has continued through its present edition as ISO 80000-2 . In 19th century Europe, there

10290-520: The start of the 19th century, Legendre and Gauss conjectured that as x {\displaystyle x} tends to infinity, the number of primes up to x {\displaystyle x} is asymptotic to x / log ⁡ x {\displaystyle x/\log x} , where log ⁡ x {\displaystyle \log x} is the natural logarithm of x {\displaystyle x} . A weaker consequence of this high density of primes

10395-433: The successor of x {\displaystyle x} is x + 1 {\displaystyle x+1} . Intuitively, the natural number n is the common property of all sets that have n elements. So, it seems natural to define n as an equivalence class under the relation "can be made in one to one correspondence ". This does not work in all set theories , as such an equivalence class would not be

10500-404: The sum does not grow to infinity as n {\displaystyle n} goes to infinity (see the Basel problem ). In this sense, prime numbers occur more often than squares of natural numbers, although both sets are infinite. Brun's theorem states that the sum of the reciprocals of twin primes , is finite. Because of Brun's theorem, it is not possible to use Euler's method to solve

10605-402: The two definitions are not equivalent, as there are theorems that can be stated in terms of Peano arithmetic and proved in set theory, which are not provable inside Peano arithmetic. A probable example is Fermat's Last Theorem . The definition of the integers as sets satisfying Peano axioms provide a model of Peano arithmetic inside set theory. An important consequence is that, if set theory

10710-423: The two uses of counting and ordering: cardinal numbers and ordinal numbers . The least ordinal of cardinality ℵ 0 (that is, the initial ordinal of ℵ 0 ) is ω but many well-ordered sets with cardinal number ℵ 0 have an ordinal number greater than ω . For finite well-ordered sets, there is a one-to-one correspondence between ordinal and cardinal numbers; therefore they can both be expressed by

10815-597: The value ζ ( 2 ) {\displaystyle \zeta (2)} of the Riemann zeta function . This function is closely connected to the prime numbers and to one of the most significant unsolved problems in mathematics, the Riemann hypothesis . Euler showed that ζ ( 2 ) = π 2 / 6 {\displaystyle \zeta (2)=\pi ^{2}/6} . The reciprocal of this number, 6 / π 2 {\displaystyle 6/\pi ^{2}} ,

10920-421: Was Bertrand's postulate , that for every n > 1 {\displaystyle n>1} there is a prime between n {\displaystyle n} and 2 n {\displaystyle 2n} , proved in 1852 by Pafnuty Chebyshev . Ideas of Bernhard Riemann in his 1859 paper on the zeta-function sketched an outline for proving the conjecture of Legendre and Gauss. Although

11025-430: Was mathematical and philosophical discussion about the exact nature of the natural numbers. Henri Poincaré stated that axioms can only be demonstrated in their finite application, and concluded that it is "the power of the mind" which allows conceiving of the indefinite repetition of the same act. Leopold Kronecker summarized his belief as "God made the integers, all else is the work of man". The constructivists saw

#822177