Editing Prime number (section)

=== 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>