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: $\mathbb {Z} [i]$ is a Euclidean domain, and hence a PID, and hence a UFD.

Consider the norm function $\nu (a+bi)=a^{2}+b^{2}$. We write the standard norm on the complex plane as $||a+bi||_{\mathbb {C} }={\sqrt {a^{2}+b^{2}}}$. We show that for all $x\neq 0$ and $y$ we have, $y=qx+r$ where $\nu (r)=0$ or $\nu (r)<\nu (x)$. Consider $x$ and $y$ as points on the complex plane. Since $x\neq 0$ we have that $y/x$ is another point in the complex plane. Consider $\mathbb {Z} [i]$ as the points with integer coordinates in $\mathbb {C}$. For any point $\zeta \in \mathbb {C}$ we can find a $\zeta '\in \mathbb {Z} [i]$ such that $||\zeta -\zeta '||_{\mathbb {C} }\leq {\sqrt {2}}/2$ by taking the $\zeta '$ to be the nearest lattice point to $\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 $z$ to be the nearest lattice point to $y/x$. We then have $y=zx+(y-zx)$. We compute the norm of $\nu (y-zx)$. We have: ${\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 $\nu (y-zy)<\nu (x)$. We obtain that $\mathbb {Z} [i]$ is a Euclidean domain. Thus $\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);