Editing Prime number (section)

== Abstract algebra ==

=== Modular arithmetic and finite fields ===
{{Main|Modular arithmetic}}
Modular arithmetic modifies usual arithmetic by only using the numbers {{tmath|\{0,1,2,\dots,n-1\} }}, for a natural number {{tmath|n}} called the modulus.
Any other natural number can be mapped into this system by replacing it by its remainder after division by {{tmath|n}}.<ref>{{harvtxt|Kraft|Washington|2014}}, [https://books.google.com/books?id=VG9YBQAAQBAJ&pg=PA96 Proposition 5.3], p. 96.</ref> Modular sums, differences and products are calculated by performing the same replacement by the remainder on the result of the usual sum, difference, or product of integers.<ref>{{cite book|title=Algebra in Action: A Course in Groups, Rings, and Fields|volume=27|series=Pure and Applied Undergraduate Texts|first=Shahriar|last=Shahriari|author-link= Shahriar Shahriari |publisher=American Mathematical Society|year=2017|isbn=978-1-4704-2849-5|pages=20–21|url=https://books.google.com/books?id=GJwxDwAAQBAJ&pg=PA20}}</ref> Equality of integers corresponds to ''congruence'' in modular arithmetic: {{tmath|x}} and {{tmath|y}} are congruent (written <math>x\equiv y</math> mod {{tmath|n}}) when they have the same remainder after division by {{tmath|n}}.<ref>{{harvnb|Dudley|1978}}, [https://books.google.com/books?id=tr7SzBTsk1UC&pg=PA28 Theorem 3, p. 28].</ref> However, in this system of numbers, [[Division (mathematics)|division]] by all nonzero numbers is possible if and only if the modulus is prime. For instance, with the prime number 7 as modulus, division by 3 is possible: {{tmath| 2/3\equiv 3\bmod{7} }}, because [[clearing denominators]] by multiplying both sides by 3 gives the valid formula {{tmath| 2\equiv 9\bmod{7} }}. However, with the composite modulus 6, division by 3 is impossible. There is no valid solution to <math>2/3\equiv x\bmod{6}</math>: clearing denominators by multiplying by 3 causes the left-hand side to become 2 while the right-hand side becomes either 0 or 3. In the terminology of [[abstract algebra]], the ability to perform division means that modular arithmetic modulo a prime number forms a [[field (mathematics)|field]] or, more specifically, a [[finite field]], while other moduli only give a [[ring (mathematics)|ring]] but not a field.<ref>{{harvnb|Shahriari|2017}}, [https://books.google.com/books?id=GJwxDwAAQBAJ&pg=PA27 pp. 27–28].</ref>

Several theorems about primes can be formulated using modular arithmetic. For instance, [[Fermat's little theorem]] states that if <math>a\not\equiv 0</math> (mod {{tmath|p}}), then <math>a^{p-1}\equiv 1</math> (mod {{tmath|p}}).<ref>{{harvnb|Ribenboim|2004}}, Fermat's little theorem and primitive roots modulo a prime, pp. 17–21.</ref> Summing this over all choices of {{tmath|a}} gives the equation
:<math>\sum_{a=1}^{p-1} a^{p-1} \equiv (p-1) \cdot 1 \equiv -1 \pmod p,</math>
valid whenever {{tmath|p}} is prime.
[[Giuga's conjecture]] says that this equation is also a sufficient condition for {{tmath|p}} to be prime.<ref>{{harvnb|Ribenboim|2004}}, The property of Giuga, pp. 21–22.</ref> [[Wilson's theorem]] says that an integer <math>p>1</math> is prime if and only if the [[factorial]] <math>(p-1)!</math> is congruent to <math>-1</math> mod {{tmath|p}}. For a composite number&nbsp;{{tmath|1= n = r\cdot s }} this cannot hold, since one of its factors divides both {{mvar|n}} and {{tmath|(n-1)!}}, and so <math>(n-1)!\equiv -1 \pmod{n}</math> is impossible.<ref>{{harvnb|Ribenboim|2004}}, The theorem of Wilson, p. 21.</ref>

=== ''p''-adic numbers ===
{{main|p-adic number}}
The [[p-adic order|{{tmath|p}}-adic order]] <math>\nu_p(n)</math> of an integer {{tmath|n}} is the number of copies of {{tmath|p}} in the prime factorization of {{tmath|n}}. The same concept can be extended from integers to rational numbers by defining the {{tmath|p}}-adic order of a fraction <math>m/n</math> to be {{tmath|\nu_p(m)-\nu_p(n)}}. The {{tmath|p}}-adic absolute value <math>|q|_p</math> of any rational number {{tmath|q}} is then defined as {{tmath|1= \vert q \vert_p=p^{-\nu_p(q)} }}. Multiplying an integer by its {{tmath|p}}-adic absolute value cancels out the factors of {{tmath|p}} in its factorization, leaving only the other primes. Just as the distance between two real numbers can be measured by the absolute value of their distance, the distance between two rational numbers can be measured by their {{tmath|p}}-adic distance, the {{tmath|p}}-adic absolute value of their difference. For this definition of distance, two numbers are close together (they have a small distance) when their difference is divisible by a high power of {{tmath|p}}. In the same way that the real numbers can be formed from the rational numbers and their distances, by adding extra limiting values to form a [[complete field]], the rational numbers with the {{tmath|p}}-adic distance can be extended to a different complete field, the [[p-adic number|{{tmath|p}}-adic numbers]].<ref name="childress"/><ref>{{cite book | last1 = Erickson | first1 = Marty | last2 = Vazzana | first2 = Anthony | last3 = Garth | first3 = David | edition = 2nd | isbn = 978-1-4987-1749-6 | mr = 3468748 | page = 200 | publisher = CRC Press | location = Boca Raton, FL | series = Textbooks in Mathematics | title = Introduction to Number Theory | url = https://books.google.com/books?id=QpLwCgAAQBAJ&pg=PA200 | year = 2016}}</ref>

This picture of an order, absolute value, and complete field derived from them can be generalized to [[algebraic number field]]s and their [[Valuation (algebra)|valuations]] (certain mappings from the [[multiplicative group]] of the field to a [[totally ordered group|totally ordered additive group]], also called orders), [[Absolute value (algebra)|absolute values]] (certain multiplicative mappings from the field to the real numbers, also called [[Norm (mathematics)|norm]]s),<ref name="childress">{{cite book | last = Childress | first = Nancy | doi = 10.1007/978-0-387-72490-4 | isbn = 978-0-387-72489-8 | mr = 2462595 | pages = 8–11 | publisher = Springer, New York | series = Universitext | title = Class Field Theory | url = https://books.google.com/books?id=RYdy4PCJYosC&pg=PA8 | year = 2009 }} See also p. 64.</ref> and places (extensions to [[complete field]]s in which the given field is a [[dense set]], also called completions).<ref>{{cite book | last = Weil | first = André | author-link = André Weil | isbn = 978-3-540-58655-5 | mr = 1344916 | page = [https://archive.org/details/basicnumbertheor00weil_866/page/n56 43] | publisher = Springer-Verlag | location = Berlin | series = Classics in Mathematics | title = Basic Number Theory | url = https://archive.org/details/basicnumbertheor00weil_866 | url-access = limited | year = 1995}} Note however that some authors such as {{harvtxt|Childress|2009}} instead use "place" to mean an equivalence class of norms.</ref> The extension from the rational numbers to the [[real number]]s, for instance, is a place in which the distance between numbers is the usual [[absolute value]] of their difference. The corresponding mapping to an additive group would be the [[logarithm]] of the absolute value, although this does not meet all the requirements of a valuation. According to [[Ostrowski's theorem]], up to a natural notion of equivalence, the real numbers and {{tmath|p}}-adic numbers, with their orders and absolute values, are the only valuations, absolute values, and places on the rational numbers.<ref name="childress"/> The [[local–global principle]] allows certain problems over the rational numbers to be solved by piecing together solutions from each of their places, again underlining the importance of primes to number theory.<ref>{{cite book | last = Koch | first = H. | doi = 10.1007/978-3-642-58095-6 | isbn = 978-3-540-63003-6 | mr = 1474965 | page = 136 | publisher = Springer-Verlag | location = Berlin | title = Algebraic Number Theory | url = https://books.google.com/books?id=wt1sCQAAQBAJ&pg=PA136 | year = 1997| citeseerx = 10.1.1.309.8812 }}</ref>

=== Prime elements of a ring ===
{{Main|Prime element|Irreducible element}}
[[File:Gaussian primes.svg|thumb|All [[Gaussian prime]]s with norm squared less than 500]]
A [[commutative ring]] is an [[algebraic structure]] where addition, subtraction and multiplication are defined. The integers are a ring, and the prime numbers in the integers have been generalized to rings in two different ways, ''prime elements'' and ''irreducible elements''. An element {{tmath|p}} of a ring {{tmath|R}} is called prime if it is nonzero, has no [[multiplicative inverse]] (that is, it is not a [[Unit (ring theory)|unit]]), and satisfies the following requirement: whenever {{tmath|p}} divides the product <math>xy</math> of two elements of {{tmath|R}}, it also divides at least one of {{tmath|x}} or {{tmath|y}}. An element is irreducible if it is neither a unit nor the product of two other non-unit elements. In the ring of integers, the prime and irreducible elements form the same set,
: <math>\{ \dots, -11, -7, -5, -3, -2, 2, 3, 5, 7, 11, \dots \}\, .</math>
In an arbitrary ring, all prime elements are irreducible. The converse does not hold in general, but does hold for [[unique factorization domain]]s.<ref>{{cite book | last = Lauritzen | first = Niels | doi = 10.1017/CBO9780511804229 | isbn = 978-0-521-53410-9 | location = Cambridge | mr = 2014325 | page = 127 | publisher = Cambridge University Press | title = Concrete Abstract Algebra: From numbers to Gröbner bases | url = https://books.google.com/books?id=BdAbcje-TZUC&pg=PA127 | year = 2003 }}</ref>

The fundamental theorem of arithmetic continues to hold (by definition) in unique factorization domains. An example of such a domain is the [[Gaussian integer]]s {{tmath|\mathbb{Z}[i]}}, the ring of [[complex number]]s of the form <math>a+bi</math> where {{tmath|i}} denotes the [[imaginary unit]] and {{tmath|a}} and {{tmath|b}} are arbitrary integers. Its prime elements are known as [[Gaussian prime]]s. Not every number that is prime among the integers remains prime in the Gaussian integers; for instance, the number 2 can be written as a product of the two Gaussian primes <math>1+i</math> and {{tmath|1-i}}. Rational primes (the prime elements in the integers) congruent to 3 mod 4 are Gaussian primes, but rational primes congruent to 1 mod 4 are not.<ref>{{harvnb|Lauritzen|2003}}, Corollary 3.5.14, p. 133; Lemma 3.5.18, p. 136.</ref> This is a consequence of [[Fermat's theorem on sums of two squares]],
which states that an odd prime {{tmath|p}} is expressible as the sum of two squares, {{tmath|1= p=x^2+y^2 }}, and therefore factorable as {{tmath|1= p=(x+iy)(x-iy) }}, exactly when {{tmath|p}} is 1 mod 4.<ref>{{harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA297 Section 12.1, Sums of two squares, pp. 297–301].</ref>

=== Prime ideals ===
{{Main|Prime ideals}}
Not every ring is a unique factorization domain. For instance, in the ring of numbers <math>a+b\sqrt{-5}</math> (for integers {{tmath|a}} and {{tmath|b}}) the number <math>21</math> has two factorizations {{tmath|1= 21=3\cdot7=(1+2\sqrt{-5})(1-2\sqrt{-5}) }}, where neither of the four factors can be reduced any further, so it does not have a unique factorization. In order to extend unique factorization to a larger class of rings, the notion of a number can be replaced with that of an [[ideal (ring theory)|ideal]], a subset of the elements of a ring that contains all sums of pairs of its elements, and all products of its elements with ring elements.
''Prime ideals'', which generalize prime elements in the sense that the [[principal ideal]] generated by a prime element is a prime ideal, are an important tool and object of study in [[commutative algebra]], [[number theory|algebraic number theory]] and [[algebraic geometry]]. The prime ideals of the ring of integers are the ideals {{tmath|(0)}}, {{tmath|(2)}}, {{tmath|(3)}}, {{tmath|(5)}}, {{tmath|(7)}}, {{tmath|(11)}}, ... The fundamental theorem of arithmetic generalizes to the [[Lasker–Noether theorem]], which expresses every ideal in a [[Noetherian ring|Noetherian]] [[commutative ring]] as an intersection of [[primary ideal]]s, which are the appropriate generalizations of [[prime power]]s.<ref>{{cite book | last1=Eisenbud | first1=David | author1-link= David Eisenbud | title=Commutative Algebra | publisher=Springer-Verlag | location=Berlin; New York | series=Graduate Texts in Mathematics | isbn=978-0-387-94268-1| mr=1322960 | year=1995 | volume=150 | at=Section 3.3| doi=10.1007/978-1-4612-5350-1 }}</ref>

The [[spectrum of a ring]] is a geometric space whose points are the prime ideals of the ring.<ref>{{cite book | last = Shafarevich | first = Igor R. | author-link = Igor Shafarevich | doi = 10.1007/978-3-642-38010-5 | edition = 3rd | isbn = 978-3-642-38009-9 | mr = 3100288 | publisher = Springer, Heidelberg | title = Basic Algebraic Geometry 2: Schemes and Complex Manifolds | year = 2013 | contribution = Definition of <math>\operatorname{Spec} A</math> | page = 5 | contribution-url = https://books.google.com/books?id=zDW8BAAAQBAJ&pg=PA5}}</ref> [[Arithmetic geometry]] also benefits from this notion, and many concepts exist in both geometry and number theory. For example, factorization or [[Splitting of prime ideals in Galois extensions|ramification]] of prime ideals when lifted to an [[field extension|extension field]], a basic problem of algebraic number theory, bears some resemblance with [[ramified cover|ramification in geometry]]. These concepts can even assist with in number-theoretic questions solely concerned with integers. For example, prime ideals in the [[ring of integers]] of [[quadratic number field]]s can be used in proving [[quadratic reciprocity]], a statement that concerns the existence of square roots modulo integer prime numbers.<ref>{{cite book | last = Neukirch | first = Jürgen | author-link = Jürgen Neukirch | doi = 10.1007/978-3-662-03983-0 | isbn = 978-3-540-65399-8 | location = Berlin | mr = 1697859 | publisher = Springer-Verlag | series = Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] | title = Algebraic Number Theory | volume = 322 | year = 1999 | at = Section I.8, p. 50}}</ref> Early attempts to prove [[Fermat's Last Theorem]] led to [[Ernst Kummer|Kummer]]'s introduction of [[regular prime]]s, integer prime numbers connected with the failure of unique factorization in the [[cyclotomic field|cyclotomic integers]].<ref>{{harvnb|Neukirch|1999}}, Section I.7, p. 38</ref> The question of how many integer prime numbers factor into a product of multiple prime ideals in an algebraic number field is addressed by [[Chebotarev's density theorem]], which (when applied to the cyclotomic integers) has Dirichlet's theorem on primes in arithmetic progressions as a special case.<ref>{{cite journal | last1 = Stevenhagen | first1 = P. | last2 = Lenstra | first2 = H.W. Jr. | author2-link = Hendrik Lenstra | doi = 10.1007/BF03027290 | issue = 2 | journal = [[The Mathematical Intelligencer]] | mr = 1395088 | pages = 26–37 | title = Chebotarëv and his density theorem | volume = 18 | year = 1996| citeseerx = 10.1.1.116.9409 | s2cid = 14089091 }}</ref>

=== Group theory ===
In the theory of [[finite group]]s the [[Sylow theorems]] imply that, if a power of a prime number <math>p^n</math> divides the [[order of a group]], then the group has a subgroup of order {{tmath|p^n}}. By [[Lagrange's theorem (group theory)|Lagrange's theorem]], any group of prime order is a [[cyclic group]],
and by [[Burnside's theorem]] any group whose order is divisible by only two primes is [[solvable group|solvable]].<ref>{{cite book|title=The Theory of Groups|series=Dover Books on Mathematics|first=Marshall|last=Hall|author-link=Marshall Hall (mathematician)|publisher=Courier Dover Publications|year=2018|isbn=978-0-486-81690-6|url=https://books.google.com/books?id=K8hEDwAAQBAJ}} For the Sylow theorems see p. 43; for Lagrange's theorem, see p. 12; for Burnside's theorem see p. 143.</ref>