section_path: Abstract algebra/Modular arithmetic and finite fields
section_name: Modular arithmetic and finite fields
paragraph_text: Modular arithmetic and finite fields
  
  Modular arithmetic modifies usual arithmetic by only using the numbers { 0, 1, 2, …, n − 1 } {\displaystyle \{0,1,2,\dots,n-1\}}, for a natural number n {\displaystyle n} called the modulus.Any other natural number can be mapped into this system by replacing it by its remainder after division by n {\displaystyle n}. Modular sums, differences and products are calculated by performing the same replacement by the remainderon the result of the usual sum, difference, or product of integers. Equality of integers corresponds to congruence in modular arithmetic: x {\displaystyle x} and y {\displaystyle y} are congruent (written x ≡ y {\displaystyle x\equiv y} mod n {\displaystyle n}) when they have the same remainder after division by n {\displaystyle n}. However, in this system of numbers, division by all nonzero numbers is possible if and only if the modulus is prime. For instance, with the prime number 7 {\displaystyle 7} as modulus, division by 3 {\displaystyle 3} is possible: 2 / 3 ≡ 3 mod 7 {\displaystyle 2/3\equiv 3{\bmod {7}}}, because clearing denominators by multiplying both sides by 3 {\displaystyle 3} gives the valid formula 2 ≡ 9 mod 7 {\displaystyle 2\equiv 9{\bmod {7}}}. However, with the composite modulus 6 {\displaystyle 6}, division by 3 {\displaystyle 3} is impossible. There is no valid solution to 2 / 3 ≡ x mod 6 {\displaystyle 2/3\equiv x{\bmod {6}}}: clearing denominators by multiplying by 3 {\displaystyle 3} causes the left-hand side to become 2 {\displaystyle 2} while the right-hand side becomes either 0 {\displaystyle 0} or 3 {\displaystyle 3}.In the terminology of abstract algebra, the ability to perform division means that modular arithmetic modulo a prime number forms a field or, more specifically, a finite field, while other moduli only give a ring but not a field.
  
  Several theorems about primes can be formulated using modular arithmetic. For instance, Fermat's little theorem states that if a ≢ 0 {\displaystyle a\not \equiv 0} (mod p {\displaystyle p}), then a p − 1 ≡ 1 {\displaystyle a^{p-1}\equiv 1} (mod p {\displaystyle p}). Summing this over all choices of a {\displaystyle a} gives the equation
  
  valid whenever p {\displaystyle p} is prime. Giuga's conjecture says that this equation is also a sufficient condition for p {\displaystyle p} to be prime. Wilson's theorem says that an integer p > 1 {\displaystyle p>1} is prime if and only if the factorial (p − 1) ! {\displaystyle (p-1)!} is congruent to − 1 {\displaystyle -1} mod p {\displaystyle p}. For a composite number n = r ⋅ s {\displaystyle \;n=r\cdot s\;} this cannot hold, since one of its factors divides both n and (n − 1) ! {\displaystyle (n-1)!}, and so (n − 1) ! ≡ − 1 (mod n) {\displaystyle (n-1)!\equiv -1{\pmod {n}}} is impossible.