---
title: "Special Element Operations"
canonical: "https://docs.magma-maths.org/v2.30-1/GlobalFields/QuadraticFields/elements.html"
source: "https://docs.magma-maths.org/v2.30-1/GlobalFields/QuadraticFields/elements.md"
part: "Global Fields"
chapter: "Quadratic Fields"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Global Fields", "source": "https://docs.magma-maths.org/v2.30-1/GlobalFields/index-global-fields.md"}
  - {"title": "Quadratic Fields", "source": "https://docs.magma-maths.org/v2.30-1/GlobalFields/QuadraticFields/index-quadratic-fields.md"}
prev: {"title": "Operations on Structures", "source": "https://docs.magma-maths.org/v2.30-1/GlobalFields/QuadraticFields/structure_ops.md"}
next: {"title": "Special Functions for Ideals", "source": "https://docs.magma-maths.org/v2.30-1/GlobalFields/QuadraticFields/special-ideals.md"}
intrinsics:
  - {"name": "div", "signature": "a div b: RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "mod", "signature": "a mod b: RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "GreatestCommonDivisor", "signature": "GreatestCommonDivisor(a, b): RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "Gcd", "signature": "Gcd(a, b): RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "GCD", "signature": "GCD(a, b): RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "LeastCommonMultiple", "signature": "LeastCommonMultiple(a, b): RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "Lcm", "signature": "Lcm(a, b): RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "LCM", "signature": "LCM(a, b): RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "Modexp", "signature": "Modexp(a, e, n): RngQuadElt, RngInt, RngQuadElt -> RngQuadElt"}
  - {"name": "Factorization", "signature": "Factorization(n): RngQuadElt -> SeqEnum, Tup"}
  - {"name": "Factorisation", "signature": "Factorisation(n): RngQuadElt -> SeqEnum, Tup"}
  - {"name": "TrialDivision", "signature": "TrialDivision(n, B): RngQuadElt, RngIntElt -> SeqEnum, SeqEnum, Tup"}
  - {"name": "ComplexConjugate", "signature": "ComplexConjugate(a): FldQuadElt -> FldQuadElt"}
  - {"name": "ComplexConjugate", "signature": "ComplexConjugate(a): RngQuadElt -> RngQuadElt"}
  - {"name": "Conjugate", "signature": "Conjugate(a): FldQuadElt -> FldQuadElt"}
  - {"name": "Conjugate", "signature": "Conjugate(a): RngQuadElt -> RngQuadElt"}
  - {"name": "BiquadraticResidueSymbol", "signature": "BiquadraticResidueSymbol(a, b): RngQuadElt, RngQuadElt -> RngQuadElt"}
  - {"name": "Primary", "signature": "Primary(a): RngQuadElt -> RngQuadElt"}
examples:
  - "ex-c87bf6"
---

# 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 id="operation-operation-div-rngquadelt-rngquadelt-rngquadelt"></a>
### `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 id="operation-operation-mod-rngquadelt-rngquadelt-rngquadelt"></a>
### `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$.

<a id="function-greatestcommondivisor-rngquadelt-rngquadelt"></a>
### `GreatestCommonDivisor(a, b): RngQuadElt, RngQuadElt -> RngQuadElt`

<a id="function-gcd-rngquadelt-rngquadelt"></a>
### `Gcd(a, b): RngQuadElt, RngQuadElt -> RngQuadElt`

<a id="function-gcd-rngquadelt-rngquadelt-2"></a>
### `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.

<a id="function-leastcommonmultiple-rngquadelt-rngquadelt"></a>
### `LeastCommonMultiple(a, b): RngQuadElt, RngQuadElt -> RngQuadElt`

<a id="function-lcm-rngquadelt-rngquadelt"></a>
### `Lcm(a, b): RngQuadElt, RngQuadElt -> RngQuadElt`

<a id="function-lcm-rngquadelt-rngquadelt-2"></a>
### `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.

<a id="function-modexp-rngquadelt-rngint-rngquadelt"></a>
### `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$).

<a id="function-factorization-rngquadelt"></a>
### `Factorization(n): RngQuadElt -> SeqEnum, Tup`

<a id="function-factorisation-rngquadelt"></a>
### `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$).

<a id="function-trialdivision-rngquadelt-rngintelt"></a>
### `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

<a id="function-complexconjugate-fldquadelt"></a>
### `ComplexConjugate(a): FldQuadElt -> FldQuadElt`

<a id="function-complexconjugate-rngquadelt"></a>
### `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})$.

<a id="function-conjugate-fldquadelt"></a>
### `Conjugate(a): FldQuadElt -> FldQuadElt`

<a id="function-conjugate-rngquadelt"></a>
### `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.

<a id="function-biquadraticresiduesymbol-rngquadelt-rngquadelt"></a>
### `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.

<a id="function-primary-rngquadelt"></a>
### `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}}$.

<a id="example-ex-c87bf6"></a>
### `Example: Primes with 2 as a Biquadratic Residue (ex-c87bf6)`

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$).

```magma
> 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$.

```magma
> 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 }
```
