# 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*: is a Euclidean domain, and hence a PID, and hence a UFD.

Consider the norm function . We write the standard norm on the complex plane as . We show that for all and we have, where or . Consider and as points on the complex plane. Since we have that is another point in the complex plane. Consider as the points with integer coordinates in . For any point we can find a such that by taking the to be the nearest lattice point to . 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 to be the nearest lattice point to . We then have . We compute the norm of . We have: It follows that . We obtain that is a Euclidean domain. Thus 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);