# 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: Represent (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; > 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 } ```