Quadratic Integers¶

This module allows to work with quadratic integers.

To compute operations with quadratic integers within the same quadratic ring, all operands must be created as QuadraticInteger objects. To do so:

Create the quadratic integer ring \(\mathcal{O}_{\mathbb{Q}[\sqrt{d}]}\) with the function QuadraticIntegerRing.
>>> Zi = QuadraticIntegerRing(-1)
Use the returned factory to create quadratic integers of the form \(a + b \sqrt{d}\).
>>> alpha = Zi("1 + I")
>>> beta = Zi("1 - I")
Then, compute the desired operations with the available operators and methods.
>>> alpha / beta
I
>>> (alpha / beta).is_unit()
True

Note that this module, quadratic_integer, need to be imported to use its classes and functions. There are basically two ways to import it:

Import all functions and classes of QiPy:
>>> from qipy import *
>>> Zi = QuadraticIntegerRing(-1)
Import only the package, and use the package’s identifier to access the classes and functions:
>>> import qipy
>>> Zi = qipy.QuadraticIntegerRing(-1)

QuadraticIntegerRing(d)¶

Return the class of quadratic integers of the form \(a + b \sqrt{d}\).

The returned class is used as a factory, that is, to create quadratic integer.

>>> Zi = QuadraticIntegerRing(-1)
>>> Zi(sqrt(-1))
I

Parameters:	d – a square-free integer.
Returns:	The factory of quadratic integers.

class QuadraticInteger(value=None, coeff_e=None, coeff_d=None)¶

Represent a quadratic integer.

>>> Zi = QuadraticIntegerRing(-1)
>>> alpha = Zi(1 - sqrt(-1))
>>> beta = Zi(sqrt(-1))
>>> alpha
1 - I
>>> beta
I
>>> alpha + beta
1
>>> alpha * beta
1 + I
>>> beta ** (2)
-1

This class supports the operators +, -, *, / y ** with their natural meaning.

There are four ways to create a quadratic integer:

With a python expression.

>>> O = QuadraticIntegerRing(-3)
>>> alpha = O(Rational(1,2) * (-1 + sqrt(-3)))
>>> alpha
-1/2 + sqrt(3)*I/2

With a SymPy expression surrounded by ".

>>> O = QuadraticIntegerRing(-3)
>>> alpha = O("1/2 * (-1 + I * sqrt(3))")
>>> alpha
-1/2 + sqrt(3)*I/2

With a pair of integers that represents the coefficients respect the integral basis \(\{1, e\}\) (see below).
```
>>> O = QuadraticIntegerRing(-3)
>>> alpha = O(coeff_e=(-1, 1))
>>> alpha
-1/2 + sqrt(3)*I/2
```

With a pair of rationals that represents the coefficients respect the basis \(\{1, \sqrt{d}\}\) (see below).

>>> O = QuadraticIntegerRing(-3)
>>> alpha = O(coeff_d=(Rational(-1, 2), Rational(1, 2)))
>>> alpha
-1/2 + sqrt(3)*I/2

Warning

If the input contains fractions, each fraction must be written as a Rational object or the input must be surround by ".

More info at SymPy’s documentation.

Note

The element \(e\) of the integral basis is defined as follows:

\[ \begin{align}\begin{aligned}\sqrt{d}, \quad \mathrm{if} \ d \ \ne 1 \mod 4\\(1 + \sqrt{d})/2, \quad \mathrm{if} \ d = 1 \mod 4\end{aligned}\end{align} \]

Notice that in the first case, the basis \(\{1, e\}\) and \(\{1, \sqrt{d}\}\) are the same and so the coefficients.

d¶: the non-square free integer that defines the ring of quadratic integers (class attribute).

e¶: the element of the integral basis (class attribute, see below).

norm¶: the norm of the quadratic integer.

trace¶: the trace of the quadratic integer.

conjugate¶: the algebraic conjugate of the quadratic integer.

Note

Given \(a + b \sqrt{d}\), its conjugate is \(a - b \sqrt{d}\), which is not the complex conjugate when \(d > 0\).

>>> Zi = QuadraticIntegerRing(-1)
>>> alpha = Zi(1 + sqrt(-1))
>>> alpha
1 + I
>>> alpha.conjugate
1 - I
>>> O = QuadraticIntegerRing(5)
>>> beta = O(1 + sqrt(5))
>>> beta
1 + sqrt(5)
>>> beta.conjugate
-sqrt(5) + 1

coeff_d¶

Tuple – the rational (half-integer) coefficients with respect to the basis \(\{1, \sqrt{d}\}\).

>>> O = QuadraticIntegerRing(-3)
>>> alpha = O(Rational(1,2) * (-1 + sqrt(-3)))
>>> alpha
-1/2 + sqrt(3)*I/2
>>> alpha.coeff_d
(-1/2, 1/2)

coeff_e¶

Tuple – the integer coefficients with respect to the integral basis \(\{1, e\}\).

>>> O = QuadraticIntegerRing(-3)
>>> alpha = O(Rational(1,2) * (-1 + sqrt(-3)))
>>> alpha
-1/2 + sqrt(3)*I/2
>>> alpha.coeff_e
(-1, 1)

classmethod elements_with_norm(n)¶

Return the quadratic integers of norm \(n\).

If \(d\) is negative, it returns all of them. Otherwise, it returns a list of generators (see Structure of solutions to \(x^2 − Dy^2 = N\) in Solving the general Pell equation by J.P. Robertson).

>>> Zi = QuadraticIntegerRing(-1)
>>> Zi.elements_with_norm(1)
[1, -1, I, -I]
>>> O = QuadraticIntegerRing(5)
>>> O.elements_with_norm(1)
[sqrt(5)/2 + 3/2, 3*sqrt(5)/2 + 7/2, 4*sqrt(5) + 9]

Returns:	the quadratic integers of norm \(n\).
Return type:	List[QuadraticInteger]

euclidean_function()¶

The value of the Euclidean function (the absolute value of the norm).

>>> Zi = QuadraticIntegerRing(-1)
>>> alpha = Zi(1 + sqrt(-1))
>>> alpha
1 + I
>>> alpha.norm
2
>>> alpha.euclidean_function()
2
>>> O = QuadraticIntegerRing(5)
>>> beta = O(1 + sqrt(5))
>>> beta
1 + sqrt(5)
>>> beta.norm
-4
>>> beta.euclidean_function()
4

Warning

The ring of quadratic integers must be an Euclidean domain with the norm as a Euclidean function, that is, \(d\) (seq. A048981) must be one of the following:

-11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73

factor()¶

Factor the quadratic integer as a product of irreducible ones.

>>> Zi = QuadraticIntegerRing(-1)
>>> alpha = Zi(2)
>>> alpha
2
>>> alpha.factor()
[1 + I, 1 - I]

Returns:	the irreducible factors.
Return type:	List[QuadraticInteger]

Warning

The ring of quadratic integers must be a unique factorization domain. Examples of \(d\) (seq. A048981) that makes the ring of quadratic integers an UFD are the following:

-163, -67, -43, -19, -11, -7, -3, -2, -1, 1, 2, 3, 5, 6, 7, 11, 13, 14, 17, 19, 21, 22, 23, 29, 31, 33, 37, 38, 41, 43, 46, 47, 53, 57, 59, 61, 62, 67, 69, 71, 73, 77, 83, 86, 89, 93, 94, 97, 101, 103, 107, 109, 113, 118, 127, 129, 131, 133, 134, 137, 139, 141, 149, …

Otherwise, this method may not work.

is_irreducible()¶

Test whether the quadratic integer is irreducible.

>>> O = QuadraticIntegerRing(-5)
>>> alpha = O(3)
>>> alpha.is_irreducible()
True

is_unit()¶

Test whether the quadratic integer is a unit.

>>> Zi = QuadraticIntegerRing(-1)
>>> alpha = Zi(sqrt(-1))
>>> alpha
I
>>> alpha.is_unit()
True
>>> beta = Zi(1 + sqrt(-1))
>>> beta
1 + I
>>> beta.is_unit()
False