Английская Википедия:Gaussian integer

Материал из Онлайн справочника
Версия от 17:23, 11 марта 2024; EducationBot (обсуждение | вклад) (Новая страница: «{{Английская Википедия/Панель перехода}} {{Short description|Complex number whose real and imaginary parts are both integers}} {{distinguish|text=Gaussian integral}} In number theory, a '''Gaussian integer''' is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

Шаблон:Short description Шаблон:Distinguish In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as <math>\mathbf{Z}[i]</math> or <math>\Z[i].</math>[1]

Gaussian integers share many properties with integers: they form a Euclidean domain, and have thus a Euclidean division and a Euclidean algorithm; this implies unique factorization and many related properties. However, Gaussian integers do not have a total ordering that respects arithmetic.

Gaussian integers are algebraic integers and form the simplest ring of quadratic integers.

Gaussian integers are named after the German mathematician Carl Friedrich Gauss.

Файл:Gaussian integer lattice.svg
Gaussian integers as lattice points in the complex plane

Basic definitions

The Gaussian integers are the set[1]

<math>\mathbf{Z}[i]=\{a+bi \mid a,b\in \mathbf{Z} \}, \qquad \text{ where } i^2 = -1.</math>

In other words, a Gaussian integer is a complex number such that its real and imaginary parts are both integers. Since the Gaussian integers are closed under addition and multiplication, they form a commutative ring, which is a subring of the field of complex numbers. It is thus an integral domain.

When considered within the complex plane, the Gaussian integers constitute the Шаблон:Math-dimensional integer lattice.

The conjugate of a Gaussian integer Шаблон:Math is the Gaussian integer Шаблон:Math.

The norm of a Gaussian integer is its product with its conjugate.

<math>N(a+bi) = (a+bi)(a-bi) = a^2+b^2.</math>

The norm of a Gaussian integer is thus the square of its absolute value as a complex number. The norm of a Gaussian integer is a nonnegative integer, which is a sum of two squares. Thus a norm [[Sum of two squares theorem|cannot be of the form Шаблон:Math, with Шаблон:Math integer]].

The norm is multiplicative, that is, one has[2]

<math>N(zw) = N(z)N(w),</math>

for every pair of Gaussian integers Шаблон:Math. This can be shown directly, or by using the multiplicative property of the modulus of complex numbers.

The units of the ring of Gaussian integers (that is the Gaussian integers whose multiplicative inverse is also a Gaussian integer) are precisely the Gaussian integers with norm 1, that is, 1, –1, Шаблон:Math and Шаблон:Math.[3]

Euclidean division

Файл:Gauss-euklid.svg
Visualization of maximal distance to some Gaussian integer

Gaussian integers have a Euclidean division (division with remainder) similar to that of integers and polynomials. This makes the Gaussian integers a Euclidean domain, and implies that Gaussian integers share with integers and polynomials many important properties such as the existence of a Euclidean algorithm for computing greatest common divisors, Bézout's identity, the principal ideal property, Euclid's lemma, the unique factorization theorem, and the Chinese remainder theorem, all of which can be proved using only Euclidean division.

A Euclidean division algorithm takes, in the ring of Gaussian integers, a dividend Шаблон:Math and divisor Шаблон:Math, and produces a quotient Шаблон:Math and remainder Шаблон:Math such that

<math>a=bq+r\quad \text{and} \quad N(r)<N(b).</math>

In fact, one may make the remainder smaller:

<math>a=bq+r\quad \text{and} \quad N(r)\le \frac{N(b)}{2}.</math>

Шаблон:AnchorEven with this better inequality, the quotient and the remainder are not necessarily unique, but one may refine the choice to ensure uniqueness.

To prove this, one may consider the complex number quotient Шаблон:Math. There are unique integers Шаблон:Math and Шаблон:Math such that Шаблон:Math and Шаблон:Math, and thus Шаблон:Math. Taking Шаблон:Math, one has

<math>a = bq + r,</math>

with

<math>r=b\bigl(x-m+ i(y-n)\bigr), </math>

and

<math>N(r)\le \frac{N(b)}{2}.</math>

The choice of Шаблон:Math and Шаблон:Math in a semi-open interval is required for uniqueness. This definition of Euclidean division may be interpreted geometrically in the complex plane (see the figure), by remarking that the distance from a complex number Шаблон:Mvar to the closest Gaussian integer is at most Шаблон:Math.[4]

Principal ideals

Since the ring Шаблон:Math of Gaussian integers is a Euclidean domain, Шаблон:Math is a principal ideal domain, which means that every ideal of Шаблон:Mvar is principal. Explicitly, an ideal Шаблон:Mvar is a subset of a ring Шаблон:Mvar such that every sum of elements of Шаблон:Mvar and every product of an element of Шаблон:Mvar by an element of Шаблон:Mvar belong to Шаблон:Mvar. An ideal is principal if it consists of all multiples of a single element Шаблон:Math, that is, it has the form

<math>\{gx\mid x\in G\}.</math>

In this case, one says that the ideal is generated by Шаблон:Math or that Шаблон:Math is a generator of the ideal.

Every ideal Шаблон:Math in the ring of the Gaussian integers is principal, because, if one chooses in Шаблон:Math a nonzero element Шаблон:Math of minimal norm, for every element Шаблон:Math of Шаблон:Math, the remainder of Euclidean division of Шаблон:Math by Шаблон:Math belongs also to Шаблон:Math and has a norm that is smaller than that of Шаблон:Math; because of the choice of Шаблон:Math, this norm is zero, and thus the remainder is also zero. That is, one has Шаблон:Math, where Шаблон:Math is the quotient.

For any Шаблон:Math, the ideal generated by Шаблон:Math is also generated by any associate of Шаблон:Math, that is, Шаблон:Math; no other element generates the same ideal. As all the generators of an ideal have the same norm, the norm of an ideal is the norm of any of its generators.

Шаблон:AnchorIn some circumstances, it is useful to choose, once for all, a generator for each ideal. There are two classical ways for doing that, both considering first the ideals of odd norm. If the Шаблон:Math has an odd norm Шаблон:Math, then one of Шаблон:Math and Шаблон:Math is odd, and the other is even. Thus Шаблон:Math has exactly one associate with a real part Шаблон:Math that is odd and positive. In his original paper, Gauss made another choice, by choosing the unique associate such that the remainder of its division by Шаблон:Math is one. In fact, as Шаблон:Math, the norm of the remainder is not greater than 4. As this norm is odd, and 3 is not the norm of a Gaussian integer, the norm of the remainder is one, that is, the remainder is a unit. Multiplying Шаблон:Math by the inverse of this unit, one finds an associate that has one as a remainder, when divided by Шаблон:Math.

If the norm of Шаблон:Math is even, then either Шаблон:Math or Шаблон:Math, where Шаблон:Math is a positive integer, and Шаблон:Math is odd. Thus, one chooses the associate of Шаблон:Math for getting a Шаблон:Math which fits the choice of the associates for elements of odd norm.

Gaussian primes

As the Gaussian integers form a principal ideal domain they form also a unique factorization domain. This implies that a Gaussian integer is irreducible (that is, it is not the product of two non-units) if and only if it is prime (that is, it generates a prime ideal).

The prime elements of Шаблон:Math are also known as Gaussian primes. An associate of a Gaussian prime is also a Gaussian prime. The conjugate of a Gaussian prime is also a Gaussian prime (this implies that Gaussian primes are symmetric about the real and imaginary axes).

A positive integer is a Gaussian prime if and only if it is a prime number that is congruent to 3 modulo 4 (that is, it may be written Шаблон:Math, with Шаблон:Math a nonnegative integer) Шаблон:OEIS. The other prime numbers are not Gaussian primes, but each is the product of two conjugate Gaussian primes.

A Gaussian integer Шаблон:Math is a Gaussian prime if and only if either:

In other words, a Gaussian integer is a Gaussian prime if and only if either its norm is a prime number, or it is the product of a unit (Шаблон:Math) and a prime number of the form Шаблон:Math.

It follows that there are three cases for the factorization of a prime number Шаблон:Math in the Gaussian integers:

Unique factorization

As for every unique factorization domain, every Gaussian integer may be factored as a product of a unit and Gaussian primes, and this factorization is unique up to the order of the factors, and the replacement of any prime by any of its associates (together with a corresponding change of the unit factor).

If one chooses, once for all, a fixed Gaussian prime for each equivalence class of associated primes, and if one takes only these selected primes in the factorization, then one obtains a prime factorization which is unique up to the order of the factors. With the choices described above, the resulting unique factorization has the form

<math>u(1+i)^{e_0}{p_1}^{e_1}\cdots {p_k}^{e_k},</math>

where Шаблон:Math is a unit (that is, Шаблон:Math), Шаблон:Math and Шаблон:Math are nonnegative integers, Шаблон:Math are positive integers, and Шаблон:Math are distinct Gaussian primes such that, depending on the choice of selected associates,

An advantage of the second choice is that the selected associates behave well under products for Gaussian integers of odd norm. On the other hand, the selected associate for the real Gaussian primes are negative integers. For example, the factorization of 231 in the integers, and with the first choice of associates is Шаблон:Nowrap, while it is Шаблон:Nowrap with the second choice.

Gaussian rationals

The field of Gaussian rationals is the field of fractions of the ring of Gaussian integers. It consists of the complex numbers whose real and imaginary part are both rational.

The ring of Gaussian integers is the integral closure of the integers in the Gaussian rationals.

This implies that Gaussian integers are quadratic integers and that a Gaussian rational is a Gaussian integer, if and only if it is a solution of an equation

<math>x^2 +cx+d=0,</math>

with Шаблон:Math and Шаблон:Math integers. In fact Шаблон:Math is solution of the equation

<math>x^2-2ax+a^2+b^2,</math>

and this equation has integer coefficients if and only if Шаблон:Math and Шаблон:Math are both integers.

Шаблон:AnchorGreatest common divisor

As for any unique factorization domain, a greatest common divisor (gcd) of two Gaussian integers Шаблон:Math is a Gaussian integer Шаблон:Math that is a common divisor of Шаблон:Math and Шаблон:Math, which has all common divisors of Шаблон:Math and Шаблон:Math as divisor. That is (where Шаблон:Math denotes the divisibility relation),

Thus, greatest is meant relatively to the divisibility relation, and not for an ordering of the ring (for integers, both meanings of greatest coincide).

More technically, a greatest common divisor of Шаблон:Math and Шаблон:Math is a generator of the ideal generated by Шаблон:Math and Шаблон:Math (this characterization is valid for principal ideal domains, but not, in general, for unique factorization domains).

The greatest common divisor of two Gaussian integers is not unique, but is defined up to the multiplication by a unit. That is, given a greatest common divisor Шаблон:Math of Шаблон:Math and Шаблон:Math, the greatest common divisors of Шаблон:Math and Шаблон:Math are Шаблон:Math, and Шаблон:Math.

There are several ways for computing a greatest common divisor of two Gaussian integers Шаблон:Math and Шаблон:Math. When one knows the prime factorizations of Шаблон:Math and Шаблон:Math,

<math>a = i^k\prod_m {p_m}^{\nu_m}, \quad b = i^n\prod_m {p_m}^{\mu_m},</math>

where the primes Шаблон:Math are pairwise non associated, and the exponents Шаблон:Math non-associated, a greatest common divisor is

<math>\prod_m {p_m}^{\lambda_m},</math>

with

<math>\lambda_m = \min(\nu_m, \mu_m).</math>

Unfortunately, except in simple cases, the prime factorization is difficult to compute, and Euclidean algorithm leads to a much easier (and faster) computation. This algorithm consists of replacing of the input Шаблон:Math by Шаблон:Math, where Шаблон:Math is the remainder of the Euclidean division of Шаблон:Math by Шаблон:Math, and repeating this operation until getting a zero remainder, that is a pair Шаблон:Math. This process terminates, because, at each step, the norm of the second Gaussian integer decreases. The resulting Шаблон:Math is a greatest common divisor, because (at each step) Шаблон:Math and Шаблон:Math have the same divisors as Шаблон:Math and Шаблон:Math, and thus the same greatest common divisor.

This method of computation works always, but is not as simple as for integers because Euclidean division is more complicated. Therefore, a third method is often preferred for hand-written computations. It consists in remarking that the norm Шаблон:Math of the greatest common divisor of Шаблон:Math and Шаблон:Math is a common divisor of Шаблон:Math, Шаблон:Math, and Шаблон:Math. When the greatest common divisor Шаблон:Math of these three integers has few factors, then it is easy to test, for common divisor, all Gaussian integers with a norm dividing Шаблон:Math.

For example, if Шаблон:Math, and Шаблон:Math, one has Шаблон:Math, Шаблон:Math, and Шаблон:Math. As the greatest common divisor of the three norms is 2, the greatest common divisor of Шаблон:Math and Шаблон:Math has 1 or 2 as a norm. As a gaussian integer of norm 2 is necessary associated to Шаблон:Math, and as Шаблон:Math divides Шаблон:Math and Шаблон:Math, then the greatest common divisor is Шаблон:Math.

If Шаблон:Math is replaced by its conjugate Шаблон:Math, then the greatest common divisor of the three norms is 34, the norm of Шаблон:Math, thus one may guess that the greatest common divisor is Шаблон:Math, that is, that Шаблон:Math. In fact, one has Шаблон:Math.

Шаблон:AnchorCongruences and residue classes

Given a Gaussian integer Шаблон:Math, called a modulus, two Gaussian integers Шаблон:Math are congruent modulo Шаблон:Math, if their difference is a multiple of Шаблон:Math, that is if there exists a Gaussian integer Шаблон:Math such that Шаблон:Math. In other words, two Gaussian integers are congruent modulo Шаблон:Math, if their difference belongs to the ideal generated by Шаблон:Math. This is denoted as Шаблон:Math.

The congruence modulo Шаблон:Math is an equivalence relation (also called a congruence relation), which defines a partition of the Gaussian integers into equivalence classes, called here congruence classes or residue classes. The set of the residue classes is usually denoted Шаблон:Math, or Шаблон:Math, or simply Шаблон:Math.

The residue class of a Gaussian integer Шаблон:Math is the set

<math> \bar a := \left\{ z \in \mathbf{Z}[i] \mid z \equiv a \pmod{z_0} \right\}</math>

of all Gaussian integers that are congruent to Шаблон:Math. It follows that Шаблон:Math if and only if Шаблон:Math.

Addition and multiplication are compatible with congruences. This means that Шаблон:Math and Шаблон:Math imply Шаблон:Math and Шаблон:Math. This defines well-defined operations (that is independent of the choice of representatives) on the residue classes:

<math>\bar a + \bar b := \overline{a+b}\quad \text{and}\quad \bar a \cdot\bar b := \overline{ab}.</math>

With these operations, the residue classes form a commutative ring, the quotient ring of the Gaussian integers by the ideal generated by Шаблон:Math, which is also traditionally called the residue class ring modulo Шаблон:Math (for more details, see Quotient ring).

Examples

  • There are exactly two residue classes for the modulus Шаблон:Math, namely Шаблон:Math (all multiples of Шаблон:Math), and Шаблон:Math, which form a checkerboard pattern in the complex plane. These two classes form thus a ring with two elements, which is, in fact, a field, the unique (up to an isomorphism) field with two elements, and may thus be identified with the integers modulo 2. These two classes may be considered as a generalization of the partition of integers into even and odd integers. Thus one may speak of even and odd Gaussian integers (Gauss divided further even Gaussian integers into even, that is divisible by 2, and half-even).
  • For the modulus 2 there are four residue classes, namely Шаблон:Math. These form a ring with four elements, in which Шаблон:Math for every Шаблон:Math. Thus this ring is not isomorphic with the ring of integers modulo 4, another ring with four elements. One has Шаблон:Math, and thus this ring is not the finite field with four elements, nor the direct product of two copies of the ring of integers modulo 2.
  • For the modulus Шаблон:Math there are eight residue classes, namely Шаблон:Math, whereof four contain only even Gaussian integers and four contain only odd Gaussian integers.

Describing residue classes

Файл:Gauss-Restklassen-wiki.png
All 13 residue classes with their minimal residues (blue dots) in the square Шаблон:Math (light green background) for the modulus Шаблон:Math. One residue class with Шаблон:Math is highlighted with yellow/orange dots.

Given a modulus Шаблон:Math, all elements of a residue class have the same remainder for the Euclidean division by Шаблон:Math, provided one uses the division with unique quotient and remainder, which is described above. Thus enumerating the residue classes is equivalent with enumerating the possible remainders. This can be done geometrically in the following way.

In the complex plane, one may consider a square grid, whose squares are delimited by the two lines

<math>\begin{align}

V_s&=\left\{ \left. z_0\left(s-\tfrac12 +ix\right) \right\vert x\in \mathbf R\right\} \quad \text{and} \\ H_t&=\left\{ \left. z_0\left(x+i\left(t-\tfrac12\right)\right) \right\vert x\in \mathbf R\right\}, \end{align}</math>

with Шаблон:Math and Шаблон:Math integers (blue lines in the figure). These divide the plane in semi-open squares (where Шаблон:Math and Шаблон:Math are integers)

<math>Q_{mn}=\left\{(s+it)z_0 \left\vert s \in \left [m - \tfrac12, m + \tfrac12\right), t \in \left[n - \tfrac12, n + \tfrac12 \right)\right.\right\}.</math>

The semi-open intervals that occur in the definition of Шаблон:Math have been chosen in order that every complex number belong to exactly one square; that is, the squares Шаблон:Math form a partition of the complex plane. One has

<math>Q_{mn} = (m+in)z_0+Q_{00}=\left\{(m+in)z_0+z\mid z\in Q_{00}\right\}.</math>

This implies that every Gaussian integer is congruent modulo Шаблон:Math to a unique Gaussian integer in Шаблон:Math (the green square in the figure), which its remainder for the division by Шаблон:Math. In other words, every residue class contains exactly one element in Шаблон:Math.

The Gaussian integers in Шаблон:Math (or in its boundary) are sometimes called minimal residues because their norm are not greater than the norm of any other Gaussian integer in the same residue class (Gauss called them absolutely smallest residues).

From this one can deduce by geometrical considerations, that the number of residue classes modulo a Gaussian integer Шаблон:Math equals its norm Шаблон:Math (see below for a proof; similarly, for integers, the number of residue classes modulo Шаблон:Math is its absolute value Шаблон:Math).

Шаблон:Math proof

Residue class fields

The residue class ring modulo a Gaussian integer Шаблон:Math is a field if and only if <math>z_0</math> is a Gaussian prime.

If Шаблон:Math is a decomposed prime or the ramified prime Шаблон:Math (that is, if its norm Шаблон:Math is a prime number, which is either 2 or a prime congruent to 1 modulo 4), then the residue class field has a prime number of elements (that is, Шаблон:Math). It is thus isomorphic to the field of the integers modulo Шаблон:Math.

If, on the other hand, Шаблон:Math is an inert prime (that is, Шаблон:Math is the square of a prime number, which is congruent to 3 modulo 4), then the residue class field has Шаблон:Math elements, and it is an extension of degree 2 (unique, up to an isomorphism) of the prime field with Шаблон:Math elements (the integers modulo Шаблон:Math).

Primitive residue class group and Euler's totient function

Many theorems (and their proofs) for moduli of integers can be directly transferred to moduli of Gaussian integers, if one replaces the absolute value of the modulus by the norm. This holds especially for the primitive residue class group (also called [[multiplicative group of integers modulo n|multiplicative group of integers modulo Шаблон:Math]]) and Euler's totient function. The primitive residue class group of a modulus Шаблон:Math is defined as the subset of its residue classes, which contains all residue classes Шаблон:Math that are coprime to Шаблон:Math, i.e. Шаблон:Math. Obviously, this system builds a multiplicative group. The number of its elements shall be denoted by Шаблон:Math (analogously to Euler's totient function Шаблон:Math for integers Шаблон:Math).

For Gaussian primes it immediately follows that Шаблон:Math and for arbitrary composite Gaussian integers

<math>z = i^k\prod_m {p_m}^{\nu_m}</math>

Euler's product formula can be derived as

<math>\phi(z) =\prod_{m\, (\nu_m > 0)} \bigl|{p_m}^{\nu_m}\bigr|^2 \left( 1 - \frac 1{|p_m|{}^2} \right) = |z|^2\prod_{p_m|z}\left( 1 - \frac 1{|p_m|{}^2} \right)</math>

where the product is to build over all prime divisors Шаблон:Math of Шаблон:Math (with Шаблон:Math). Also the important theorem of Euler can be directly transferred:

For all Шаблон:Math with Шаблон:Math, it holds that Шаблон:Math.

Historical background

The ring of Gaussian integers was introduced by Carl Friedrich Gauss in his second monograph on quartic reciprocity (1832).[6] The theorem of quadratic reciprocity (which he had first succeeded in proving in 1796) relates the solvability of the congruence Шаблон:Math to that of Шаблон:Math. Similarly, cubic reciprocity relates the solvability of Шаблон:Math to that of Шаблон:Math, and biquadratic (or quartic) reciprocity is a relation between Шаблон:Math and Шаблон:Math. Gauss discovered that the law of biquadratic reciprocity and its supplements were more easily stated and proved as statements about "whole complex numbers" (i.e. the Gaussian integers) than they are as statements about ordinary whole numbers (i.e. the integers).

In a footnote he notes that the Eisenstein integers are the natural domain for stating and proving results on cubic reciprocity and indicates that similar extensions of the integers are the appropriate domains for studying higher reciprocity laws.

This paper not only introduced the Gaussian integers and proved they are a unique factorization domain, it also introduced the terms norm, unit, primary, and associate, which are now standard in algebraic number theory.

Unsolved problems

Файл:Gauss-primes-768x768.png
The distribution of the small Gaussian primes in the complex plane

Most of the unsolved problems are related to distribution of Gaussian primes in the plane.

  • Gauss's circle problem does not deal with the Gaussian integers per se, but instead asks for the number of lattice points inside a circle of a given radius centered at the origin. This is equivalent to determining the number of Gaussian integers with norm less than a given value.

There are also conjectures and unsolved problems about the Gaussian primes. Two of them are:

  • The real and imaginary axes have the infinite set of Gaussian primes 3, 7, 11, 19, ... and their associates. Are there any other lines that have infinitely many Gaussian primes on them? In particular, are there infinitely many Gaussian primes of the form Шаблон:Math?[7]
  • Is it possible to walk to infinity using the Gaussian primes as stepping stones and taking steps of a uniformly bounded length? This is known as the Gaussian moat problem; it was posed in 1962 by Basil Gordon and remains unsolved.[8][9]

See also

Notes

Шаблон:Reflist

References

External links

Шаблон:Algebraic numbers Шаблон:Prime number classes

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Шаблон:Harvtxt
  2. ↑ Шаблон:Harvtxt
  3. ↑ Шаблон:Harvtxt
  4. ↑ Шаблон:Harvtxt
  5. ↑ Шаблон:Harvtxt
  6. ↑ Шаблон:Harvtxt
  7. ↑ Ribenboim, Ch.III.4.D Ch. 6.II, Ch. 6.IV (Hardy & Littlewood's conjecture E and F)
  8. ↑ Шаблон:Cite journal
  9. ↑ Шаблон:Cite book
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:Gaussian_integer&oldid=14865671