# Computing GCDs over the Gaussian Integers

I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness. One can sketchily argue something like this however:

Claim: ${\displaystyle \mathbb {Z} [i]}$ is a Euclidean domain, and hence a PID, and hence a UFD.

Consider the norm function ${\displaystyle \nu (a+bi)=a^{2}+b^{2}}$. We write the standard norm on the complex plane as ${\displaystyle ||a+bi||_{\mathbb {C} }={\sqrt {a^{2}+b^{2}}}}$. We show that for all ${\displaystyle x\neq 0}$ and ${\displaystyle y}$ we have, ${\displaystyle y=qx+r}$ where ${\displaystyle \nu (r)=0}$ or ${\displaystyle \nu (r)<\nu (x)}$. Consider ${\displaystyle x}$ and ${\displaystyle y}$ as points on the complex plane. Since ${\displaystyle x\neq 0}$ we have that ${\displaystyle y/x}$ is another point in the complex plane. Consider ${\displaystyle \mathbb {Z} [i]}$ as the points with integer coordinates in ${\displaystyle \mathbb {C} }$. For any point ${\displaystyle \zeta \in \mathbb {C} }$ we can find a ${\displaystyle \zeta '\in \mathbb {Z} [i]}$ such that ${\displaystyle ||\zeta -\zeta '||_{\mathbb {C} }\leq {\sqrt {2}}/2}$ by taking the ${\displaystyle \zeta '}$ to be the nearest lattice point to ${\displaystyle \zeta }$. Since any point on the plane is contained in a square whose vertices are lattice points and whose side lengths are one, there must be a lattice point nearer than half the diagonal of the square. We then take ${\displaystyle z}$ to be the nearest lattice point to ${\displaystyle y/x}$. We then have ${\displaystyle y=zx+(y-zx)}$. We compute the norm of ${\displaystyle \nu (y-zx)}$. We have: ${\displaystyle {\sqrt {\nu (y-zx)}}=||y-zx||_{\mathbb {C} }=||x||_{\mathbb {C} }\cdot ||y/x-z||_{\mathbb {C} }\leq ||x||_{\mathbb {C} }{\frac {\sqrt {2}}{2}}<||x||_{\mathbb {C} }={\sqrt {\nu (x)}}}$ It follows that ${\displaystyle \nu (y-zy)<\nu (x)}$. We obtain that ${\displaystyle \mathbb {Z} [i]}$ is a Euclidean domain. Thus ${\displaystyle \mathbb {Z} [i]}$ is a PID and hence a UFD by results given in class.

#!/usr/bin/perl
use Math::Complex;

## A Quick hack for computing GCDs of Gaussian integers.

$z2 = 857 + i;$z1 = 255;

sub gcd {
# the Euclidean algorithm

my $x =$_[0];
my $y =$_[1];

if ($x *$y == 0) {
print "Done!\n";
} else {
$q = &approx($x/$y);$r = $x -$q*$y; print "($x) = ($q)($y) + ($r)\n"; &gcd($y,$r); } } sub approx { # find the nearest Gaussian integer to a point on the complex plane my$z = $_[0]; my$x = int(Re($z)); my$y = int(Im($z)); if (abs($z - (($x+1) + i*$y) ) < 1/sqrt(2)) {
return ($x+1) + i*$y;
} elsif (abs($z - (($x) + i*($y+1)) ) < 1/sqrt(2)) { return$x + i*($y+1); } elsif (abs($z - (($x+1) + i*($y+1)) ) < 1/sqrt(2)) {
return ($x+1) + i*($y+1);
} else {
return $x + i*$y;
}

}

&gcd($z1,$z2);