Extended GCD of Quadratic Integers
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
Consider the quadratic field 
and the associated ring of integers 
, where 
if 
and 
if 
. We assume is principal but not necessarily Euclidean. We compute the GCD of two elements 
, 
of modulo a unit of . The computation also gives explicit coefficients 
, 
for the Bézout identity 
. This is done by reducing binary quadratic forms and considering the sum of ideals 
as the ideal 
, with 
.
Contributed by: Abdelwaheb Miled and Ahmed Ouertani (March 2011)
Open content licensed under CC BY-NC-SA
Snapshots
Details
This algorithm computes the GCD of two quadratic integers; it does this by combining the following operations:
1) compute the sum of two ideals of 
and put the ideal result 
into canonical form: 
, 
, so that the norm 
of this ideal is then 
.
2) find a generator of an ideal (an element 
such that 
is equal to the norm of the ideal, that is, 
). Recall that the norm of an element 
is 
, where 
if and 
if .
3) represent the integer 1 by a binary quadratic form.
This method is quite efficient for small quadratic integers, but could be lengthy for large numbers.
References:
[1] D. A. Buell, Binary Quadratic Forms, New York: Springer–Verlag, 1989.
[2] A. Miled and A. Ouertani, "Extended GCD of Quadratic Integers," arXiv, 2010.
Permanent Citation
Factoring Gaussian Integers
Izidor Hafner
Eisenstein Integer
Daniel de Souza Carvalho
Positive Integer Explorer
Chris Boucher
Integer Value Spatial Distance
Michael Schreiber
Encrypted Secret Sharing
Jim Wiggins
Direct Sum of Rings
Aaron Dunigan AtLee
Equivalence Classes Modulo m
Pablo Alberca Bjerregaard (University of Malaga, Spain)
The Action of the Modular Group on the Fundamental Domain
Andrzej Kozlowski
Modular Arithmetic
Christopher Moretti
Connect the Dots
Ken Levasseur (UMass Lowell)
