Special Element Operations

Several functions are available only for elements of certain maximal orders.

The maximal orders of QuadraticField(d) for \(d = -1, -2, -3, -7, -11, 2, 3, 5\) and \(13\) are Euclidean with respect to the Norm. The division algorithm, Euclidean algorithm, GCD, and LCM are available for these orders only. Below, we will refer to these orders as the “special Euclidean orders”.

Division Algorithm

a div b: RngQuadElt, RngQuadElt -> RngQuadElt

This operation is available for all orders, but its behaviour depends on whether the order \(R\) containing \(a\) and \(b\) is one of the special Euclidean orders listed above.

When \(R\) is not a special Euclidean order, this returns the exact quotient of \(a\) and \(b\). An error results if \(a\) is not exactly divisible by \(b\) in \(R\).

When \(R\) is a special Euclidean order, this performs the division algorithm in \(R\). It finds uniquely determined elements \(q\) and \(r\) in \(R\) such that \(a = q b + r\) and Norm\((r) < \ \)Norm\((b)\), and returns \(q\).

a mod b: RngQuadElt, RngQuadElt -> RngQuadElt

This operation requires \(a\) and \(b\) to belong to one of the special Euclidean orders listed above. It performs the same calculation as div, and returns the remainder \(r\).

GreatestCommonDivisor(a, b): RngQuadElt, RngQuadElt -> RngQuadElt

Gcd(a, b): RngQuadElt, RngQuadElt -> RngQuadElt

GCD(a, b): RngQuadElt, RngQuadElt -> RngQuadElt

The greatest common divisor of \(a\) and \(b\), which must be elements of one of the special Euclidean orders listed above.

LeastCommonMultiple(a, b): RngQuadElt, RngQuadElt -> RngQuadElt

Lcm(a, b): RngQuadElt, RngQuadElt -> RngQuadElt

LCM(a, b): RngQuadElt, RngQuadElt -> RngQuadElt

The least common multiple of \(a\) and \(b\), which must be elements of one of the special Euclidean orders listed above.

Modexp(a, e, n): RngQuadElt, RngInt, RngQuadElt -> RngQuadElt

This returns \(a^e \bmod n\), where \(a\) and \(n\) must be elements of one of the special Euclidean orders listed above.

Factorization

Magma’s factorization in maximal orders of quadratic number fields is based upon factoring the norm in the integers. Thus, the comments that are made about the Factorization command in the integers also apply here. Moreover, since the factorization may be off by a unit power, that power is also returned (the unit being -1, \(\sqrt{-1}\), or \((1 + \sqrt{-3})/2\)).

Factorization(n): RngQuadElt -> SeqEnum, Tup

Factorisation(n): RngQuadElt -> SeqEnum, Tup

The factorization of \(n\) in the maximal order of the quadratic number field \(Q(\sqrt{d})\), where \(d\) is one of: -1, -2, -3, -7, or -11. Returns the factorization along with the appropriate power of a unit (the unit being -1, \(\sqrt{-1}\), or \((1 + \sqrt{-3})/2\)).

TrialDivision(n, B): RngQuadElt, RngIntElt -> SeqEnum, SeqEnum, Tup

Trial division of \(n\) by primes of relative norm \(\leq\) B in the maximal order of \(Q(\sqrt{d})\), where \(d\) is one of: -1, -2, -3, -7, or -11. Returns the factored part, the unfactored part, and the power of the unit that the factorization is off by (the unit being -1, \(\sqrt{-1}\), or \((1 + \sqrt{-3})/2\)).

Conjugates

ComplexConjugate(a): FldQuadElt -> FldQuadElt

ComplexConjugate(a): RngQuadElt -> RngQuadElt

The complex conjugate of quadratic field element \(a\); returns \(a\) in a real quadratic field and \(\bar a=x-y\sqrt{d}\) if \(a=x+y\sqrt{d}\) in an imaginary quadratic field \({\mathbb{Q}}(\sqrt{d})\).

Conjugate(a): FldQuadElt -> FldQuadElt

Conjugate(a): RngQuadElt -> RngQuadElt

The conjugate \(x-y\sqrt{d}\) of \(a=x+y\sqrt{d}\) in the quadratic field \({\mathbb{Q}}(\sqrt{d})\).

Other Element Functions

For the ring of integers of \({\mathbb{Q}}({\mathrm{i}})\) the biquadratic residue symbol (generalizing the Legendre symbol) is available.

BiquadraticResidueSymbol(a, b): RngQuadElt, RngQuadElt -> RngQuadElt

Given a Gaussian integer \(a\) and a primary, non-unit Gaussian integer \(b\), where \(a\) and \(b\) are coprime, return the value of the biquadratic character \(\left( {a\over b}\right)_4\). The value of this character is equal to \({\mathrm{i}}^k\), for some \(k\in\{0,1,2,3\}\). If \(a\) and \(b\) have a factor in common, the function returns \(0\), if \(b\) is not primary or \(b\) is a unit an error results.

Primary(a): RngQuadElt -> RngQuadElt

Return the unique associate \(\bar a\) of the Gaussian integer \(a\) that satisfies

\[\bar a \equiv 1\bmod(1+{\mathrm{i}})^3,\]

or 0 in case \(a\) is divisible by \(1+{\mathrm{i}}\).

Example: Primes with 2 as a Biquadratic Residue (ex-c87bf6)

Run in calculator (opens in a new tab)Copy input

The following example checks for primes \(p\) with \(65\leq p\leq 1000\) and \(p\equiv1\bmod 4\) a result that was conjectured by Euler and proved by Gauss, namely that

\[z^4\equiv 2\bmod p\quad\hbox{\rm has a solution}\iff p=x^2+64y^2\quad\text{\rm for some }x, y.\]

We use the function NormEquation to find the prime above \(p\) in the Gaussian integers, and we build the set of such primes for which \(2\) is a biquadratic residue (which means that \(z^4\equiv 2\bmod p\) for some \(z\)).

> s := { };
> Q := QuadraticField(-1);
> M := RingOfIntegers(Q);
> for p := 65 to 1000 by 4 do
>    if IsPrime(p) then
>       _, x := NormEquation(Q, p);
>       if BiquadraticResidueSymbol(2, Primary(M!x[1])) eq 1 then
>          Include(~s, p);
>       end if;
>    end if;
> end for;
> s;
{ 73, 89, 113, 233, 257, 281, 337, 353, 577, 593, 601, 617, 881, 937 }

Next we create the set of all primes as above that are of the form \(x^2+64y^2\). Note that we have to use NormEquation on a suborder of \(Q\) now, because we want to solve \(x^2+64y^2=p\), while QuadraticField(-64) returns just \({\mathbb{Q}}({\mathrm{i}})\) in which we can only solve \(x^2+y^2=p\).

> S := sub<MaximalOrder(Q) | 8>;
> t := { };
> for p := 65 to 1000 by 4 do
>    if IsPrime(p) then
>       if NormEquation(S, p) then
>           Include(~t, p);
>       end if;
>    end if;
> end for;
> t;
{ 73, 89, 113, 233, 257, 281, 337, 353, 577, 593, 601, 617, 881, 937 }

Run in calculator (opens in a new tab)Copy input