NumberTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Numbers : NumberTheory/FactorNormEuclidean

NumberTheory

 FactorNormEuclidean
 factorization of integers in quadratic norm-Euclidean fields

 Calling Sequence FactorNormEuclidean(z, d, output_opt)

Parameters

 z - integral element of $Q\left(\sqrt{d}\right)$ d - rational integer such that $Q\left(\sqrt{d}\right)$ is a norm-Euclidean field output_opt - (optional) equation of the form output = product or output = list; the default is output = product

Returns

 • If output_opt is set to output = product, then the return value is of the form $±{u}^{a}{p}_{1}^{{b}_{1}}\cdots {p}_{n}^{{b}_{n}}$ where the ${p}_{i}$ are distinct prime factors and the ${b}_{i}$ are positive integers.
 – If $d>0$, then $u$ is either $w$ or $\stackrel{&conjugate0;}{w}$ where $w$ is the fundamental unit in $Z\left(\sqrt{d}\right)$ and $a$ is a non-negative integer.
 – If $d<0$, then $u$ is a unit in $Z\left(\sqrt{d}\right)$ and $a=1$.
 • If output_opt is set to output = list, then the return value is of the form $\left[\left[s,x,y,a\right],\left[{f}_{1},\dots ,{f}_{n}\right]\right]$ where $s=±1$ and each ${f}_{i}$ is a three element list of the form $\left[p,q,k\right]$. Each $p+q\sqrt{d}$ is a distinct prime and $k$ is a positive integer.
 – If $d>0$, then $u=x+y\sqrt{d}$ where $u$ is as previously described and $a$ is a non-negative integer.
 – If $d<0$, then $x+y\sqrt{d}$ is a unit in $Z\left(\sqrt{d}\right)$. Let $t=x+y\sqrt{d}$. If $t=±1$ then $t=s$ and $x,y,a=1,0,0$. Otherwise, $s,a=1,1$.

Description

 • The FactorNormEuclidean function computes the integer factorization of z in the ring of integers $Z\left(\sqrt{d}\right)$ of the quadratic field $Q\left(\sqrt{d}\right)$.
 • Consider the absolute value of the field norm of $Q\left(\sqrt{d}\right)$ as a field extension of $Q$, denoted by $N$. If d is one of $-11,-7,-3,-2,-1,2,3,5,6,7,11,13,17,19,21,29,33,37,41,57,73$, then $N$ satisfies the following property. If $a$ and $b$ are in $Q\left(\sqrt{d}\right)$ and $b\ne 0$, then there exists $q$ and $r$ in $Q\left(\sqrt{d}\right)$ such that $a=bq+r$ and $N\left(r\right). In this case, $N$ is said to be a Euclidean function on $Q\left(\sqrt{d}\right)$ and $Q\left(\sqrt{d}\right)$ is said to be a norm-Euclidean field.
 • When $d=2,3\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}4$, integers in $Z\left(\sqrt{d}\right)$ have the form $a+b\sqrt{d}$ and when $d=1\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}4$ they have the form $a+b\left(\frac{1}{2}+\frac{1}{2}\sqrt{d}\right)$, where $a$ and $b$ are rational integers. Alternatively for when $d=1\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}4$, integers have the form $\frac{a}{2}+\frac{b}{2}\sqrt{d}$ where $a$ and $b$ are rational integers of the same parity.

Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{FactorNormEuclidean}\left(38477343,11\right)$
 $\left({3}\right){}\left({85}{-}{16}{}\sqrt{{11}}\right){}\left({85}{+}{16}{}\sqrt{{11}}\right){}\left({125}{-}{34}{}\sqrt{{11}}\right){}\left({125}{+}{34}{}\sqrt{{11}}\right)$ (1)

expand may be used to multiply together the terms.

 > $\mathrm{expand}\left(\right)$
 ${38477343}$ (2)

If output_opt option is explicitly set to output = product, the return value will be in product form.

 > $\mathrm{FactorNormEuclidean}\left(38434\mathrm{sqrt}\left(33\right),33,\mathrm{output}=\mathrm{product}\right)$
 ${-}\left({23}{-}{4}{}\sqrt{{33}}\right){}\left(\sqrt{{33}}\right){}{\left({11}{+}{2}{}\sqrt{{33}}\right)}^{{2}}{}\left({58}{-}{7}{}\sqrt{{33}}\right){}\left({58}{+}{7}{}\sqrt{{33}}\right){}\left(\frac{{5}}{{2}}{-}\frac{\sqrt{{33}}}{{2}}\right){}\left(\frac{{5}}{{2}}{+}\frac{\sqrt{{33}}}{{2}}\right)$ (3)
 > $\mathrm{expand}\left(\right)$
 ${38434}{}\sqrt{{33}}$ (4)

If the output_opt is set to output = list, the return value will be in list form.

 > $\mathrm{FactorNormEuclidean}\left(408294234124-4242\mathrm{sqrt}\left(29\right),29,\mathrm{output}=\mathrm{list}\right)$
 $\left[\left[{-1}{,}\frac{{5}}{{2}}{,}{-}\frac{{1}}{{2}}{,}{4}\right]{,}\left[\left[{2}{,}{0}{,}{1}\right]{,}\left[{4}{,}{-1}{,}{0}\right]{,}\left[{4}{,}{1}{,}{1}\right]{,}\left[{11}{,}{-2}{,}{0}\right]{,}\left[{11}{,}{2}{,}{1}\right]{,}\left[{38}{,}{-7}{,}{0}\right]{,}\left[{38}{,}{7}{,}{1}\right]{,}\left[\frac{{1}}{{2}}{,}{-}\frac{{1}}{{2}}{,}{1}\right]{,}\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}{,}{1}\right]{,}\left[\frac{{955872689}}{{2}}{,}{-}\frac{{331629325}}{{2}}{,}{0}\right]{,}\left[\frac{{955872689}}{{2}}{,}\frac{{331629325}}{{2}}{,}{1}\right]\right]\right]$ (5)

FactorNormEuclidean(z, d) displays an error message if z is not an integer in $Q\left(\sqrt{d}\right)$.

 > $\mathrm{FactorNormEuclidean}\left(\frac{3}{2},2\right)$

Compatibility

 • The NumberTheory[FactorNormEuclidean] command was introduced in Maple 2016.