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: [math]\displaystyle{ \ZZ[i] }[/math] is a Euclidean domain, and hence a PID, and hence a UFD.

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