Modular arithmetic and finite fields Modular arithmetic modifies usual arithmetic by only using the numbers {{tmath|\{0,1,2,\dots,n-1\} }}, for a natural number called the modulus. Any other natural number can be mapped into this system by replacing it by its remainder after division by . 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. Equality of integers corresponds to
congruence in modular arithmetic: and are congruent (written x\equiv y mod ) when they have the same remainder after division by . 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 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 2/3\equiv x\bmod{6}: 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 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\not\equiv 0 (mod ), then a^{p-1}\equiv 1 (mod ). Summing this over all choices of gives the equation :\sum_{a=1}^{p-1} a^{p-1} \equiv (p-1) \cdot 1 \equiv -1 \pmod p, valid whenever is prime.
Giuga's conjecture says that this equation is also a sufficient condition for to be prime.
Wilson's theorem says that an integer p>1 is prime if and only if the
factorial (p-1)! is congruent to -1 mod . For a composite number this cannot hold, since one of its factors divides both and , and so (n-1)!\equiv -1 \pmod{n} is impossible.
p-adic numbers The
-adic order \nu_p(n) of an integer is the number of copies of in the prime factorization of . The same concept can be extended from integers to rational numbers by defining the -adic order of a fraction m/n to be . The -adic absolute value |q|_p of any rational number is then defined as {{tmath|1= \vert q \vert_p=p^{-\nu_p(q)} }}. Multiplying an integer by its -adic absolute value cancels out the factors of 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 -adic distance, the -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 . 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 -adic distance can be extended to a different complete field, the
-adic numbers. This picture of an order, absolute value, and complete field derived from them can be generalized to
algebraic number fields and their
valuations (certain mappings from the
multiplicative group of the field to a
totally ordered additive group, also called orders),
absolute values (certain multiplicative mappings from the field to the real numbers, also called
norms), and places (extensions to
complete fields in which the given field is a
dense set, also called completions). The extension from the rational numbers to the
real numbers, 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 -adic numbers, with their orders and absolute values, are the only valuations, absolute values, and places on the rational numbers.
Prime elements of a ring 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 of a ring is called prime if it is nonzero, has no
multiplicative inverse (that is, it is not a
unit), and satisfies the following requirement: whenever divides the product xy of two elements of , it also divides at least one of or . 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, : \{ \dots, -11, -7, -5, -3, -2, 2, 3, 5, 7, 11, \dots \}\, . In an arbitrary ring, all prime elements are irreducible. The converse does not hold in general, but does hold for
unique factorization domains. The fundamental theorem of arithmetic continues to hold (by definition) in unique factorization domains. An example of such a domain is the
Gaussian integers {{tmath|\mathbb{Z}[i]}}, the ring of
complex numbers of the form a+bi where denotes the
imaginary unit and and are arbitrary integers. Its prime elements are known as
Gaussian primes. 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 1+i and . 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. This is a consequence of
Fermat's theorem on sums of two squares, which states that an odd prime is expressible as the sum of two squares, , and therefore factorable as , exactly when is 1 mod 4.
Prime ideals Not every ring is a unique factorization domain. For instance, in the ring of numbers a+b\sqrt{-5} (for integers and ) the number 21 has two factorizations {{tmath|1= 21=3\cdot7=(1+2\sqrt{-5})(1-2\sqrt{-5}) }}, where none 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, 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,
algebraic number theory and
algebraic geometry. The prime ideals of the ring of integers are the ideals , , , , , , ... The fundamental theorem of arithmetic generalizes to the
Lasker–Noether theorem, which expresses every ideal in a
Noetherian commutative ring as an intersection of
primary ideals, which are the appropriate generalizations of
prime powers. The
spectrum of a ring is a geometric space whose points are the prime ideals of the ring.
Arithmetic geometry also benefits from this notion, and many concepts exist in both geometry and number theory. For example, factorization or
ramification of prime ideals when lifted to an
extension field, a basic problem of algebraic number theory, bears some resemblance with
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 fields can be used in proving
quadratic reciprocity, a statement that concerns the existence of square roots modulo integer prime numbers. Early attempts to prove
Fermat's Last Theorem led to
Kummer's introduction of
regular primes, integer prime numbers connected with the failure of unique factorization in the
cyclotomic integers. 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.
Group theory In the theory of
finite groups the
Sylow theorems imply that, if a power of a prime number p^n divides the
order of a group, then the group has a subgroup of order . By
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. == Computational methods ==