Constructive cyclotomic factorization and real unit squares

For $x=a+b\sqrt{2}\in \mathbb{Q}(\sqrt{2})$ put $N_R(x)=\mathrm{\mid }{a}^2-2b^2\mathrm{\mid }$. For $z=A+B\omega$ with $A,B\in \mathbb{Q}(i)$ put $N_O(z)=\mathrm{\mid }{A}^2-i{B}^2{\mathrm{\mid }}^2=\mathrm{\mid }z{\mathrm{\mid }}^2\mathrm{\mid }{z}^{\bullet }{\mathrm{\mid }}^2$. These functions are multiplicative, positive on nonzero elements, and take positive integer values on nonzero elements of their respective rings: $A,B\in \mathbb{Z}[i]$ for $z\in O$, and $z{z}^{\bullet }=A^2-i{B}^2\in \mathbb{Z}[i]$. Integer norm one is equivalent to being a unit: the converse follows by multiplicativity, and the forward implication follows by taking the product of the other conjugates divided by the norm (with a sign in $R$). All coordinates of that inverse remain in the ring.

The real elements of $O$ are exactly $R$. Indeed, for $z=a_0+a_1\omega +a_{2}i+a_3{\omega }^3$, its imaginary part is $a_2+(a_1+a_3)\mathrm{/}\sqrt{2}$; irrationality of $\sqrt{2}$ makes this zero exactly when $a_2=0$ and $a_3=-a_1$. The real part is then $a_0+a_1\sqrt{2}$. A real unit of $O$ consequently is a unit of $R$, since its inverse is real too. Also ${\lambda }^{-1}=\sqrt{2}-1\in R$ and ${\lambda }^{\bullet }=-{\lambda }^{-1}$.

To divide in $R$, round the rational coefficients of a quotient to nearest integers. Its error $e=a+b\sqrt{2}$ has $\mathrm{\mid }a\mathrm{\mid },\mathrm{\mid }b\mathrm{\mid }\le 1\mathrm{/}2$, so $N_R(e)=\mathrm{\mid }{a}^2-2b^2\mathrm{\mid }\le 1\mathrm{/}2<1$. To divide in $O$, express a quotient as $A+B\omega$ and round $A,B$ to Gaussian integers. For the errors $C,D$, $\mathrm{\mid }C{\mathrm{\mid }}^2,\mathrm{\mid }D{\mathrm{\mid }}^2\le 1\mathrm{/}2$, whence $N_O(C+D\omega )=\mathrm{\mid }{C}^2-i{D}^2{\mathrm{\mid }}^2\le (\mathrm{\mid }C{\mathrm{\mid }}^2+\mathrm{\mid }D{\mathrm{\mid }}^2{)}^2\le 1$. If the last upper bound equals one, all four real coordinates of $C,D$ are $\pm 1\mathrm{/}2$. Then $C^2,D^2$ are purely imaginary of magnitude $1\mathrm{/}2$, so $C^2$ and $-i{D}^2$ are perpendicular and the actual norm is $1\mathrm{/}2$. Otherwise the displayed bound is already strict. Multiplicativity therefore gives a remainder of norm strictly below that of the divisor in both rings. This proves the Euclidean assertions, including ties in rounding.

If $u\in R$ is a unit, choose a sign and an integer power of $\lambda$ to make $v=\pm {\lambda }^{j}u$ lie in $[1,\lambda )$. Such a power exists because $\lambda >1$. Write $v=a+b\sqrt{2}$. Its signed field norm is $\pm 1$, so $v^{\bullet }=\pm 1\mathrm{/}v$. For norm $+1$, $a=(v+1\mathrm{/}v)\mathrm{/}2\in [1,\sqrt{2})$, hence $a=1$; the equation $a^2-2b^2=1$ forces $b=0$ and $v=1$. For norm $-1$, $a=(v-1\mathrm{/}v)\mathrm{/}2\in [0,1)$, hence $a=0$, incompatible with $-2b^2=-1$. This proves $u=\pm {\lambda }^m$. Its two embeddings are positive exactly when the sign is positive and $m$ is even. In this case ${\lambda }^{m\mathrm{/}2}$ is the required real unit square root. Enumerating integer powers until the exact coefficients agree recovers $m$ in finite time. Signs and comparisons of $a+b\sqrt{2}$ are decided by signs of the rational coefficients and, when necessary, comparing $a^2$ and $2b^2$.

Repeated division terminates because nonzero remainder norms strictly decrease through positive integers. Back substitution expresses the gcd as a linear combination. If an irreducible $p$ does not divide $a$, the gcd of $p,a$ is a unit, so multiplying a Bezout identity by $b$ shows that $p\mid ab$ implies $p\mid b$. Thus irreducibles are prime. A nonunit has a factorization into irreducibles by induction on its norm: a proper factorization has two factors of norm at least two, each of smaller norm. The prime-divisor property and cancellation give uniqueness up to ordering and units. Divisibility is decidable by computing the quotient in the field and checking its integral coordinates; two elements are associates exactly when their quotient has integral coordinates and norm one.

Here is an explicit finite factor search, which makes the existence proof algorithmic without a primality oracle for $O$. For a nonunit $\alpha \in O$ put $M=N_O(\alpha )\ge 2$ and enumerate all power-basis integer tuples with coefficients between $-(M+3)$ and $M+3$. Test whether such an element $d$ divides $\alpha$ and $1<N_O(d)<M$; any successful $d$ splits $\alpha$ into smaller-norm factors. If $\alpha$ is reducible, choose a nonunit proper divisor and multiply it by a power of the unit $\lambda$ so $1\le \mathrm{\mid }d\mathrm{\mid }<\lambda$. Its norm is unchanged and less than $M$, and $\mathrm{\mid }{d}^{\bullet }\mathrm{\mid }=\sqrt{N_O(d)}\mathrm{/}\mathrm{\mid }d\mathrm{\mid }\le \sqrt{M}$. Recovering power-basis coefficients from the two complex embeddings gives $\mathrm{\mid }{a}_0\mathrm{\mid },\mathrm{\mid }{a}_2\mathrm{\mid }\le (\mathrm{\mid }d\mathrm{\mid }+\mathrm{\mid }{d}^{\bullet }\mathrm{\mid })\mathrm{/}2$ and $\mathrm{\mid }{a}_1\mathrm{\mid },\mathrm{\mid }{a}_3\mathrm{\mid }\le (\mathrm{\mid }d\mathrm{\mid }+\mathrm{\mid }{d}^{\bullet }\mathrm{\mid })\mathrm{/}\sqrt{2}$. They are all below $\lambda +\sqrt{M}<M+3$, so the list contains this normalized proper divisor. Failure of the finite search therefore certifies irreducibility. Recursing on successful factors terminates by strict norm descent, and the residual norm-one elements supply the unit.